Code Book

Programming contest লাইফে এখন পর্যন্ত যত Data structure এবং Algorithm শিখেছি তার সকল কালেকশন এই PDF এ পাওয়া যাবে।

 

 

                   ~ Happy coding ~

Queue

Queue data structure দুইটি বেসিক property মেনে কাজ করে।

• যদি list এ কোন element add হয় তাহলে তা last এর দিক দিয়ে এ্যাড হবে।
• যদি list থেকে কোন element বের করতে হয়, তাহলে তা সামনে থেকে বের হবে।

জিনিসটা অনেকটা বাসে উঠার জন্য যাত্রীদের লাইনের মত চিন্তা করা যেতে পারে। নতুন কেউ আসলে লাইনের পিছনে দাঁড়াবে এবং যে সামনে আছে সে সবার আগে বাসে উঠবে।

Stack

Stack হল এমন একটি ডাটাস্ট্রাকচার যা, দুইটি নীতি মেনে চলে।

• Stack এ কোন element insert হলে শেষে দিয়ে insert হবে।
• কোন element ফেলে/বের করে দিতে হলে last থেকে বের করে দিতে হবে। এই জন্য এইটাকে বলা হয় LIFO. Last in First Out. যে সবার শেষে insert হবে, সে সবার আগে বের হবে।

Stack এর স্ট্রাকচার নিচের ফিগারগুলা দেখে সহজে বুঝা যায়,

Stack

Linked list

Data structure এর একদম বেসিক একটা জিনিস হল Linked list.
Linked list এবং Array প্রায় একই রকম কাজ করে। তবে তাদের operation, memory এর উপর ভিত্তি করে কিছু সুবিধা অসুবিধা আছে।

• Array ব্যবহার এর শুরুতে কতগুলো ব্লক নিয়ে কাজ করব তা ডিক্লেয়ার করে দিতে হয়। এবং পুরো প্রোগ্রাম জুড়ে সেই সাইজ একই থাকে, পরিবর্তন করা যায় না। Linked list এ যখন প্রয়োজন শুধু তখনেই ব্লক এ্যাড করা হয়, তাতে মেমরি অপচয় হয় না।
• Array তে যেখানে index access করা যায়, Linked list এ তা করা যায় না।
• Array তে যেকোন পজিশনে এলিমেন্ট insert/delete করা অনেক কষ্টসাধ্য ও complexity বেশি, কিন্তু Linked list দিয়ে তা সহজে করে ফেলা যায়।

Basic Structure:

Linked list এ প্রতিটা ব্লক দুইটি অংশে বিভক্ত। এক অংশে থাকে ডাটা, আরেক অংশে থাকে পরর্বতী ব্লকের address. এইভাবে ব্লক পরর্বতী ব্লকের address সেভ রেখে একটি list এর মত কাঠামো গঠন করে। একটি Linked list দেখতে নিচের fig এর মত হবে।

Sparse Table

Sparse Table RMQ (range minimum/maximum query) টাইপ প্রবলেম সল্ভ করতে কাজে লাগে। একটি Array ‘A’ তে কিছু নাম্বার দেয়া আছে। এখন বলা হল কুয়েরি i to j রেঞ্জ দেয়া হবে, বলতে হবে এই রেঞ্জে এর মধ্যে মিনিমাম নাম্বার কত। এখন Brute force way তে করলে worst case complexity যাবে O(Q*N)। কিন্তু Sparse Table দিয়ে O(N log N) এ pre calculation করে O(1) এ প্রতি কুয়েরির answer দেয়া যায়।

Sparse Table:

Sparse Table এ Array প্রতিপজিশন থেকে তার 2 এর power এর length পর্যন্ত result সেভ করে রাখা হয়।এর ফলে, “যেকোন নাম্বারকে 2 এর power এর যোগফল হিসেবে লিখা যায়।” এই property use করে sparse table থেকে সহজে result calculation করা যায়।

Array A[]={10, 1, 3, 20, 25, -5, 6, -10, 11, 8} এর minimum range query জন্য sparse table ST হবে এমন,