ডেটা স্ট্রাকচার

অ্যালগরিদমের মূল ভিত্তি আয়ত্ত করতে ইন্টারেক্টিভ গাইড।

অ্যারে ও স্ট্রিং
ডেটা স্ট্রাকচার কেন শিখবেন?
সঠিক পাত্র সবকিছু বদলে দেয় — গতি, মেমরি এবং কোডের সৌন্দর্য
→
স্ট্যাটিক অ্যারে
নম্বর দেওয়া খোপের সারি — সাথে সাথে জিনিস নেওয়া যায়, কিন্তু সাইজ বদলানো যায় না
→
ডায়নামিক অ্যারে (Dynamic Array)
এমন একটা অ্যারে, যার জায়গা ফুরিয়ে গেলে নিজে নিজেই বড় হয়ে যায়
→
টু পয়েন্টার (Two Pointers)
অ্যারের উপর দিয়ে দুই আঙুল চালিয়ে এক চান্সেই সমস্যার সমাধান করা
→
স্লাইডিং উইন্ডো (Sliding Window)
অ্যারের উপর দিয়ে একটা ছবির ফ্রেম বা জানালা সরিয়ে নিমেষেই সাব-অ্যারে (Sub-array) সমস্যার সমাধান করা
→
প্রিফিক্স সাম (Prefix Sums)
আগে থেকেই যোগফল হিসাব করে রাখা, যাতে যেকোনো সাব-অ্যারের যোগফল চোখের পলকে O(1) স্পিডে বের করা যায়
→
লিংকড লিস্ট
সিঙ্গলি লিংকড লিস্ট
বাক্সের শেকল — প্রতিটা বাক্স শুধু চেনে তার ঠিক পরের জনকে
→
ডাবলি লিংকড লিস্ট (Doubly Linked List)
টু-ওয়ে শেকল — প্রতিটা বাক্স তার সামনের জন এবং পেছনের জন, দুই জনকেই চেনে
→
সার্কুলার লিংকড লিস্ট (Circular Linked List)
যে শেকলের কোনো শেষ নেই — শেষের কড়াটা আবার প্রথম কড়ার সাথে জোড়া লাগানো
→
ফ্লয়েডস সাইকেল ডিটেকশন (Floyd's Cycle Detection)
লিংকড লিস্টের ভেতরে কোনো লুকানো চক্কর বা লুপ আছে কি না — বাড়তি কোনো মেমোরি ছাড়াই ধরে ফেলা
→
রিভার্সিং লিংকড লিস্ট (Reversing a Linked List)
পুরো শেকলটাকে ধরে উল্টে দেওয়া — যাতে শেষের কড়া হয়ে যায় প্রথম কড়া
→
স্ট্যাক ও কিউ
স্ট্যাক (Stack)
প্লেটের স্তূপ — যে প্লেটটা সবার শেষে রাখবেন, সেটাই সবার আগে তুলবেন
→
কিউ (Queue)
লাইনে দাঁড়িয়ে অপেক্ষা — যে আগে আসবে, সে আগে পাবে
→
ডেক (Deque)
এমন একটা সারিবদ্ধ লাইন যেখানে সামনে বা পেছনে — যেকোনো দিক দিয়েই ঢোকা বা বের হওয়া যায়
→
মনোটোনিক স্ট্যাক (Monotonic Stack)
এমন একটা স্ট্যাক যেটা সবসময় ছোট থেকে বড় সাজানেন থাকে — পরের বড় বা ছোট সংখ্যাটা ম্যাজিকের মতো খুঁজে দেয়
→
মনোটোনিক কিউ (Monotonic Queue)
স্লাইডিং উইন্ডোর সবচেয়ে বড় বা ছোট সংখ্যাটা চোখের পলকে বের করার জাদুকরী কিউ
→
হ্যাশ টেবিল
হ্যাশ ফাংশন (Hash Functions)
যেকোনো নাম বা ডেটাকে মুহূর্তের মধ্যে একটা নির্দিষ্ট নম্বরে বদলে ফেলা
→
চেইনিং (Chaining)
লকারে জায়গা নেই? কোনো ব্যাপার না, একটার পেছনে আরেকটা ঝুলিয়ে দিন
→
সেট এবং ম্যাপ (Sets & Maps)
চোখের পলকে মেম্বারশিপ চেক আর নাম ধরে ভ্যালু খোঁজা — সবার প্রিয় হ্যাশ টেবিল
→
ফ্রিকোয়েন্সি প্যাটার্ন (Frequency Patterns)
একবার গোনো, বারবার উত্তর দিন — হ্যাশ ম্যাপের জাদুকরী সুপারপাওয়ার
→
ট্রি
বাইনারি ট্রি (Binary Trees)
এমন একটা ফ্যামিলি ট্রি, যেখানে বাবা-মায়ের সর্বোচ্চ দুজন করেই সন্তান থাকতে পারে
→
বাইনারি সার্চ ট্রি (Binary Search Tree)
সাজানেন-গোছানো গাছ — বাঁয়ে ছোটরা, ডানে বড়রা
→
বিএসটি ব্যালান্সিং (BST Balancing)
আনব্যালান্সড বিএসটি (BST) আসলে একটা বাঁশের মতো লম্বা লিংকড লিস্ট ছাড়া আর কিছুই না!
→
এভিএল ট্রি (AVL Tree)
নিজে থেকেই ব্যালান্স ঠিক রাখা ট্রি — যতই কাটাকাটি করুন, ও ঠিকই সোজা হয়ে দাঁড়াবে
→
রেড-ব্ল্যাক ট্রি (Red-Black Tree)
নিজে নিজে ব্যালান্স হওয়া জাদুকরী ট্রি — জাভার (Java) ট্রি-ম্যাপ বা সি++ (C++)-এর ম্যাপের পেছনের হিরো
→
সেগমেন্ট ট্রি (Segment Tree)
অ্যারের মাঝখানের যেকোনো রেঞ্জের যোগফল বের করা বা আপডেট করা — শুধু চোখের পলকে (O(log n)-এ)
→
ফেনউইক ট্রি (Fenwick Tree / BIT)
সেগমেন্ট ট্রির চেয়েও সহজে এবং বিটের জাদুতে শুরু থেকে শেষ পর্যন্ত যেকোনো যোগফল বের করা — মাত্র O(log n) স্পিডে
→
ট্রাই (Trie বা Prefix Tree)
শব্দের প্রথম কয়েকটা অক্ষর দিয়ে পুরো শব্দ খোঁজা — চোখের পলকে অটোকারেক্ট বা সাজেশন
→
এন-অ্যারি ট্রি (N-ary Trees)
যখন একটা নোডের বাপের যেকোনো সংখ্যক বাচ্চা থাকতে পারে — ফাইল সিস্টেম, ডম (DOM), বা অর্গানোগ্রাম
→
হিপ ও প্রায়োরিটি কিউ
হিপ (Heaps)
সবচেয়ে বড় বা ছোটটা সবসময় চোখের সামনে মেলা থাকে — O(1) স্পিডে উত্তর আর O(log n) স্পিডে আপডেট
→
হিপ সর্ট (Heap Sort)
অতিরিক্ত মেমোরি ছাড়াই O(n log n) স্পিডে সর্ট করার গ্যারান্টি
→
প্রায়োরিটি কিউয়ের প্যাটার্ন (Priority Queue Patterns)
K-তম বড়, K-টা লিস্ট জোড়া লাগানো, টপ-K জনপ্রিয় — সবকিছু একটা ছোট্ট হিপের খেল
→
টু-হিপ প্যাটার্ন (Two-Heap Pattern)
সংখ্যার পাহাড়কে মাঝখান থেকে দুই ভাগ করা — সবসময় চোখের পলকে মিডিয়ান বা মাঝের সংখ্যা বের করা
→
গ্রাফ
গ্রাফ কীভাবে মেমোরিতে থাকে (Graph Representation)
শহর আর রাস্তার ম্যাপ কীভাবে কম্পিউটারের মাথায় ঢোকানো যায়
→
ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search - BFS)
শহরের ম্যাপে লেভেল বা রিং ধরে খোঁজা — কাছের বন্ধুরা আগে
→
ডেপথ-ফার্স্ট সার্চ (Depth-First Search - DFS)
পেছনে ফেরার আগে একটা রাস্তা ধরে যত দূর যানয়া যায় তত দূর যান
→
টপোলজিক্যাল সর্ট (Topological Sort)
শহরগুলোকে এমনভাবে সাজান যেন সব ওয়ান-ওয়ে রাস্তা শুধু সামনের দিকেই যায়, পেছনের দিকে নয়
→
ইউনিয়ন-ফাইন্ড (Union-Find বা DSU)
কে কার বন্ধু সেটুকুই শুধু মনে রাখা — আর চোখের পলকে তাদের এক গ্রুপে মিলিয়ে দেওয়া
→
মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree)
সবচেয়ে কম খরচে রাস্তা বানিয়ে সবগুলো শহরকে এক সুতোয় গাঁথা
→
ডাইকস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm)
গ্রাফের জিপিএস (GPS) — এক জায়গা থেকে বাকি সব জায়গায় যানয়ার সবচেয়ে সস্তা বা ছোট রাস্তা বের করা
→
বেলম্যান-ফোর্ড অ্যালগরিদম (Bellman-Ford Algorithm)
নেগেটিভ রাস্তার শর্টেস্ট পাথ বের করা — এবং ভুল বা নেগেটিভ সাইকেল ধরে ফেলা
→
ফ্লয়েড-ওয়ার্শল অ্যালগরিদম (Floyd-Warshall Algorithm)
সবার থেকে সবার কাছে যানয়ার সবচেয়ে ছোট রাস্তা — জাস্ট একটা ট্রিপল লুপের ম্যাজিক
→
অ্যাডভান্সড / স্পেশাল
স্কিপ লিস্ট (Skip List)
ভিআইপি পাসওয়ালা লিংকড লিস্ট — যেখানে খোঁজার স্পিড O(log n)
→
ব্লুম ফিল্টার (Bloom Filter)
জিনিসটা কি আছে? — উত্তর: 'হতে পারে আছে', কিন্তু 'না' বললে ১০০% গ্যারান্টি নেই
→
LRU ক্যাশ (LRU Cache)
যেটা বেশি দরকার সেটা হাতের কাছে রাখুন, আর যেটা ভুলে গেছ সেটা ফেলে দিন
→
স্পার্স টেবিল (Sparse Table)
একবার O(n log n) সময় খরচ করে টেবিল সাজিয়ে নিলে, যেকোনো রেঞ্জের সবচেয়ে ছোট সংখ্যা বের করা যায় চোখের পলকে — O(1) স্পিডে
→
সাফিক্স অ্যারে এবং এলসিপি অ্যারে (Suffix Array & LCP Array)
কোনো শব্দের সবগুলো সাফিক্স বা শেষাংশকে সাজিয়ে রাখা — স্ট্রিং খোঁজার দুনিয়ার এক জাদুকরী হাতিয়ার
→