DSA MCQ — ডেটা স্ট্রাকচার ও অ্যালগরিদম প্রশ্নব্যাংক | পর্ব ৬৯

Q: heap আর BST দুটোই tree, দুটোতেই log n — তাহলে heap-এ search কেন Θ(n)? কোন কাজে কোনটি বাছবেন?

দুটির পার্থক্য তাদের ক্রমের নিয়মে । BST-তে নিয়মটি অনুভূমিক: বাঁ subtree-র সব key ছোট, ডানের সব বড়। তাই যেকোনো key খুঁজতে প্রতিটি node-এ একটি তুলনাই বলে দেয় কোন দিকে নামবেন — পথের দৈর্ঘ্য উচ্চতার সমান। heap-এর নিয়মটি উল্লম্ব: parent সন্তানের চেয়ে বড় (max-heap). বাঁ আর ডান সন্তানের মধ্যে কোনো সম্পর্ক নেই। ফলে root-এ সবচেয়ে বড় key নিশ্চিত, কিন্তু 5 কোথায় আছে বলার উপায় নেই — বাঁয়ে বা ডানে, যেকোনো জায়গায়। worst case-এ সব node দেখতে হয়: Θ(n). heap-এর log n আসে শুধু দুটি কাজে: insert (শেষে বসিয়ে sift-up) আর extract-max (root সরিয়ে sift-down). এই দুটি কাজ পথ ধরে চলে, আর heap সবসময় complete binary tree বলে উচ্চতা ⌊log₂ n⌋। BST-র log n-এর নিশ্চয়তা আরও দুর্বল: সাধারণ BST-তে সাজানো ক্রমে insert করলে tree শিকল হয়ে যায়, উচ্চতা n − 1. log n নিশ্চিত শুধু balanced BST-তে — AVL (Adelson-Velsky আর Landis, ১৯৬২) বা red-black tree-তে।

Q: “O(1)” তিন রকম হতে পারে — worst case, amortized আর expected. vector-এর push_back আর hash table-এর insert দুটিই “O(1)” — তফাত কোথায়?

তিনটি “O(1)” তিনটি আলাদা প্রতিশ্রুতি। worst case O(1) মানে প্রতিটি কাজ, প্রতিবার, ধ্রুবক সময়ে — যেমন array-র A[i] পড়া বা stack-এর push (আগে থেকে জায়গা থাকলে)। amortized O(1) মানে কোনো একটি কাজ ব্যয়বহুল হতে পারে, কিন্তু যেকোনো m টি কাজের ক্রমের মোট খরচ O(m) — এটি একটি নিশ্চিত গ্যারান্টি, এতে কোনো সম্ভাবনা নেই। expected (বা average) O(1) মানে খরচ একটি random variable, আর তার প্রত্যাশিত মান ধ্রুবক — কোনো দুর্ভাগা মুহূর্তে বা খারাপ ইনপুটে বেশি হতে পারে। vector-এর push_back হলো amortized: capacity দ্বিগুণ করার মুহূর্তে একটি push_back পুরো array কপি করে, Θ(n). কিন্তু n টি push_back-এ কপির মোট খরচ 1 + 2 + 4 + … < 2n — তাই গড়ে প্রতিটি O(1), যেকোনো ইনপুটে, নিশ্চিতভাবে। accounting method-এ ভাবলে: প্রতিটি push_back ৩ একক “টাকা” দেয় — একটি নিজের লেখায়, দুটি জমা থাকে ভবিষ্যতের কপির জন্য। binary counter-এর increment আর দুই stack-এর queue একই শ্রেণির উদাহরণ।

এক নজরে · এই পাতা কীভাবে ব্যবহার করবেন

১০০টি প্রশ্ন, কোর্সের ক্রমে: প্রথমে উত্তর বাছাইয়ের কৌশল আর প্রচলিত ফাঁদের তালিকা, তারপর মডিউল ১ থেকে ৮ — প্রতিটি মডিউলের জন্য একটি অংশ। প্রতিটি অংশের শুরুতে “যা ঝালিয়ে নেবেন” তালিকায় সংশ্লিষ্ট পর্বের লিংক।
আগে খাতায় উত্তর, তারপর চাপুন: যে অপশনই চাপুন, ব্যাখ্যা দেখাবে — সঠিকটি কেন সঠিক, আর ভুলটি কোন ভুল ধারণা থেকে বানানো। ভুল অপশনের ব্যাখ্যা থেকেই সবচেয়ে বেশি শেখা হয়।
কঠিনতার মাত্রা দেওয়া আছে: প্রতিটি প্রশ্নের শুরুতে (সহজ), (মাঝারি) বা (কঠিন)। নতুন হলে আগে সহজগুলো; চাকরির লিখিত পরীক্ষা, ইন্টারভিউ বা কনটেস্টের প্রস্তুতিতে মাঝারি আর কঠিনগুলোতে বেশি সময় দিন।
হিসাবের প্রতিটি উত্তর কোড চালিয়ে যাচাই করা: trace, output, “pass 2-এর পর array”, Huffman-এর bit, MST-এর weight — সবগুলো প্রোগ্রাম চালিয়ে মিলিয়ে দেখা। দুটি প্রশ্নের C++ কোড পাতাতেই আছে, নিজে চালিয়ে দেখুন।
শেষে মোট স্কোর: পাতার নিচে দেখাবে প্রথম চেষ্টায় কয়টি ঠিক হলো। যে অংশে তিনটির বেশি ভুল, সেই অংশের পর্বগুলো আবার পড়ুন।

এই পর্বে যা করবেন

DSA-র MCQ কোন কোন ছাঁচে আসে তা চেনা, আর বাদ দেওয়ার পদ্ধতি, সময় ভাগ ও ভুলে নম্বর কাটার হিসাব শেখা
log-এর ভিত্তি, O বনাম Θ, worst বনাম average, stable sort, heap বনাম BST, BFS বনাম Dijkstra — ছয়টি বড় ফাঁদ এড়ানো
পুরো কোর্সের ১০০টি প্রশ্নে নিজের দুর্বল মডিউল খুঁজে বের করা, আর সেই পর্বে ফিরে যাওয়া
ছোট ইনপুটে হাতে trace করে (array, heap, tree, দূরত্বের টেবিল) নির্ভুল উত্তর দেওয়ার অভ্যাস
AI দিয়ে আরও MCQ বানানো, আর সেগুলোর “সঠিক উত্তর” কোড চালিয়ে আর পর্বের সাথে মিলিয়ে যাচাই করা

১ · DSA-র MCQ কীভাবে সামলাবেন — প্রশ্নের ধরন, বাদ দেওয়ার কৌশল আর প্রচলিত ফাঁদ

ধরুন রাজশাহীর নুসরাত CSE শেষ করে একটি ব্যাংকের IT officer পদের লিখিত পরীক্ষায় বসেছেন। প্রথম অংশে ডেটা স্ট্রাকচার আর অ্যালগরিদমের ৩০টি MCQ, সময় ২৫ মিনিট। তিনি ভেবেছিলেন সহজ হবে — quick sort, heap, Dijkstra সবই তো পড়া। কিন্তু প্রশ্নগুলো এমন: “quick sort-এর time complexity কত?” — অপশনে O(n log n) আর O(n²) দুটোই। “heap-এ একটি key খুঁজতে কত সময়?” — অপশনে O(log n) আছে, আর সেটি দেখতে খুব ঠিক মনে হয়। ফল এল ৩০-এ ১৯. ভুলগুলোর বেশিরভাগই জ্ঞানের অভাব নয় — প্রশ্নের ভাষা পড়ার ভুল।

DSA-র MCQ-তে প্রশ্নকর্তা জেনেশুনে এমন ভুল অপশন রাখেন, যা কোনো আধা-সত্য নিয়ম থেকে আসে। এমন বিভ্রান্তিকর অপশনকে বলে distractor. “heap মানে log n”, “দুই লুপ মানে n²”, “Dijkstra সব shortest path পারে” — এগুলো একেকটি distractor-এর জন্মস্থান। ভালো খবর হলো, distractor-গুলো ঘুরেফিরে একই কয়েকটি ভুল ধারণা থেকে আসে। সেগুলো চিনে ফেললে প্রশ্ন অর্ধেক সহজ হয়ে যায়।

প্রশ্নের আট ছাঁচ

বিশ্ববিদ্যালয়ের পরীক্ষা, চাকরির লিখিত পরীক্ষা (IT officer, ব্যাংকের IT, সফটওয়্যার ইঞ্জিনিয়ার screening) আর অনলাইন অ্যাসেসমেন্টে DSA-র MCQ মোটামুটি আটটি ছাঁচে পড়ে। কোন ছাঁচের প্রশ্ন, সেটা চিনতে পারলেই ঠিক করতে পারবেন কোন কৌশল লাগবে:

ধরন	উদাহরণ	কৌশল
সংজ্ঞা	“stable sort কী?”, “NP-complete মানে?”	সংজ্ঞার প্রতিটি শব্দ মেলান
Complexity	“build-heap-এর সময়?”, “এই লুপ কত?”	কোন case আর কোন মডেল, আগে ঠিক করুন
কোন ডেটা স্ট্রাকচার?	“range add আর range min — কোনটি?”	কোন কোন কাজ লাগবে, তালিকা করুন
কোডের output	stack-queue, রিকার্শন, ছোট লুপ	খাতায় চলকের টেবিল বানিয়ে চালান
কোন অ্যালগরিদম?	“0/1 weight-এ shortest path?”	ইনপুটের শর্ত (weight, ঋণাত্মক, DAG) দেখুন
সত্য বৈশিষ্ট্য	“red-black tree সম্পর্কে কোনটি সত্য?”	প্রতিটি অপশন আলাদা করে সত্য/মিথ্যা
Trace-এর ফল	“pass 2-এর পর array”, “BFS-এর ক্রম”	ধাপ গুনে লিখুন, এক ধাপও লাফাবেন না
প্রমাণের ধারণা	“lower bound কেন n log n?”, “invariant কী?”	কারণটি মেলান, শুধু সংখ্যা নয়

কৌশল ১ · বাদ দেওয়ার পদ্ধতি

সঠিক উত্তর সরাসরি খোঁজার চেয়ে ভুলগুলো বাদ দেওয়া প্রায়ই সহজ। একে বলে elimination method. প্রতিটি অপশনকে আলাদা করে জিজ্ঞেস করুন: “এটি সত্য হলে কোন নিয়মটি সত্য হতে হবে?” তারপর হয় একটি নিয়ম দিয়ে, নয়তো একটি ছোট counterexample দিয়ে অপশনটি কেটে দিন। নিচের ডায়াগ্রামে এমন একটি কঠিন প্রশ্ন ধাপে ধাপে সমাধান করা হয়েছে — চারটি অপশনের তিনটি তিনটি আলাদা ফাঁদ।

প্রশ্ন পড়া“সত্য”চারটি আলাদা দাবি
heap ≠ BSTΘ(n)খ বাদ
counterexample−2গ বাদ
কোন case?n²ক বাদ
যাচাই∑ h·n/2ʰউত্তর ঘ

প্রশ্ন (কঠিন)নিচের কোন উক্তিটি সত্য?

ক) quick sort-এর time complexity O(n log n)
খ) n উপাদানের binary heap-এ যেকোনো key
   খুঁজতে O(log n)
গ) negative cycle না থাকলে Dijkstra
   ঋণাত্মক edge-এও সঠিক উত্তর দেয়
ঘ) n টি উপাদান থেকে bottom-up build-heap Θ(n)

ধাপ ২heap-এর নিয়ম কী নিশ্চিত করে?

max-heap: শুধু  parent ≥ child
বাঁ আর ডান সন্তানের মধ্যে কোনো ক্রম নেই

        9
      /   \
     7     8      ← 5 খুঁজতে কোন দিকে যাবেন?
    / \   /       জানার উপায় নেই → সব node দেখুন
   3   5 6

খ) heap-এ search O(log n)   আসলে Θ(n)

ধাপ ৩চার vertex-এর counterexample

A → B  (2)
A → C  (3)
C → B  (−2)          ← negative cycle নেই
B → D  (1)

Dijkstra:  B settle হয় 2-এ, তার থেকে D = 3
           তারপর C = 3, C→B দিয়ে B = 1
           কিন্তু B আর D আগেই “চূড়ান্ত” → D = 3
আসল দূরত্ব: A→C→B→D = 2

গ) ঋণাত্মক edge-এ Dijkstra সঠিক

ধাপ ৪case বলা নেই — কী ধরবেন?

quick sort (সাধারণ pivot):
  best / average   Θ(n log n)
  worst            Θ(n²)     ← সাজানো ইনপুট, শেষ pivot

case না বললে প্রচলিত রীতি: worst case
O(n log n) worst case-এর ওপরের সীমা নয়

ক) O(n log n)   (শুধু গড়ে সত্য)

ধাপ ৫বাকি অপশনটি নিজেও যাচাই

উচ্চতা h-এ প্রায় n / 2^(h+1) টি node
প্রতিটির sift-down খরচ ≤ h

মোট ≤ ∑ h · n / 2^(h+1)  =  n · ∑ h / 2^(h+1)  ≤  n

উত্তর: ঘ) build-heap Θ(n)
(n বার insert করলে Θ(n log n) — সেটি আলাদা পদ্ধতি)

প্রশ্নটি পড়ুন, “সত্য” শব্দে দাগ দিন। এটি “সত্য বৈশিষ্ট্য” ছাঁচ — চারটি স্বাধীন দাবি, যার ঠিক একটি সত্য। প্রতিটি দাবি একটি করে পরিচিত ফাঁদ থেকে এসেছে কি না, খুঁজুন। খাতায় চারটি অক্ষর লিখে প্রতিটির পাশে “স” বা “মি” বসাতে বসাতে এগোন।
খ — heap আর BST গুলিয়ে ফেলার ফাঁদ। heap-এর একমাত্র নিয়ম parent ≥ child (max-heap-এ)। বাঁ আর ডানের মধ্যে কোনো ক্রম নেই, তাই 5 খুঁজতে কোন দিকে নামবেন তা বলা যায় না — সব node দেখতে হয়, Θ(n). log n লাগে শুধু root-এর কাজে (extract-max) আর insert-এ। খ বাদ।
গ — একটি ছোট counterexample-ই যথেষ্ট। চারটি vertex: A→B (2), A→C (3), C→B (−2), B→D (1). Dijkstra প্রথমে B-কে 2 দূরত্বে settle করে (সেটি সবচেয়ে ছোট), আর B থেকে D পায় 3. পরে C (3) থেকে B-তে 1 পাওয়া যায়, কিন্তু B আগেই settled — তার থেকে D আর হালনাগাদ হয় না। D-র উত্তর 3, অথচ আসল দূরত্ব 2. cycle নেই, তবু উত্তর ভুল। গ বাদ — ঋণাত্মক edge-এ Bellman–Ford লাগে।
ক — “কোন case?” প্রশ্নটি করুন। case না বললে MCQ-তে প্রচলিত রীতি হলো worst case ধরা। quick sort-এর worst case Θ(n²) (সাজানো ইনপুটে শেষ উপাদান pivot হলে), তাই “time complexity O(n log n)” worst case-এর জন্য মিথ্যা — যদিও গড়ে সত্য। এই অপশনটিই সবচেয়ে বেশি পরীক্ষার্থীকে টানে। ক বাদ।
ঘ — বাকিটি নিজেও যাচাই করুন। শুধু বাদ দিয়ে থামবেন না; শেষ অপশনটির পক্ষে যুক্তি থাকলে তবেই নিশ্চিত হোন। bottom-up build-heap-এ বেশিরভাগ node নিচের দিকে, তাদের sift-down ছোট: ∑ h · n/2^h+1 ≤ n. তাই Θ(n). উত্তর ঘ।

কৌশল ২ · complexity-র প্রশ্নে আগে “কোন case, কোন মডেল” ঠিক করুন

“X-এর complexity কত?” প্রশ্নে চারটি জিনিস লুকিয়ে থাকে: কোন case (best, worst, average), কোন ধরনের সীমা (O, Ω, Θ), প্রতি কাজের খরচ না মোট খরচ (amortized), আর কোন মডেল (তুলনা-ভিত্তিক কি না)। প্রশ্নে কিছু বলা না থাকলে প্রচলিত রীতি: worst case, আর সবচেয়ে আঁটসাঁট সীমা। কিন্তু অপশনে যদি একই অ্যালগরিদমের দুটি সময় থাকে — যেমন “গড়ে Θ(n log n), worst Θ(n²)” — তাহলে যে অপশন দুটি case আলাদা করে ঠিকভাবে বলে, সেটিই সাধারণত উত্তর।

কৌশল ৩ · trace প্রশ্নে খাতায় টেবিল, মাথায় নয়

“pass 2-এর পর array কী?”, “Dijkstra কোন ক্রমে settle করে?”, “prefix function কী?” — এমন প্রশ্নে বেশিরভাগ ভুল হয় এক ধাপ লাফিয়ে যাওয়ায়। প্রতিটি ধাপে পুরো অবস্থাটি এক লাইনে লিখুন: array-র সব উপাদান, stack-এর ভেতরের সব কিছু, দূরত্বের পুরো টেবিল। প্রশ্নকর্তা প্রায় সবসময় একটি অপশন রাখেন “এক ধাপ আগের” অবস্থা আর একটি “এক ধাপ পরের” — আপনার টেবিল থাকলে সেগুলো চোখে পড়বে। আর প্রশ্নে 0-based না 1-based, উচ্চতা edge-এ না node-এ গোনা — এই সংজ্ঞাগুলো আগে মিলিয়ে নিন।

কৌশল ৪ · সময় ভাগ আর ভুলে নম্বর কাটার হিসাব

৩০টি প্রশ্ন ২৫ মিনিটে মানে প্রতিটিতে গড়ে ৫০ সেকেন্ড। একটি Dijkstra trace-এই দুই মিনিট লাগতে পারে। তাই দুই দফায় চলুন: প্রথম দফায় সংজ্ঞা আর সরাসরি complexity, দ্বিতীয় দফায় trace আর হিসাব। যেসব পরীক্ষায় ভুল উত্তরে নম্বর কাটে (negative marking), সেখানে আন্দাজ একটি হিসাবের প্রশ্ন: (ঠিক হওয়ার সম্ভাবনা × ১) − (ভুল হওয়ার সম্ভাবনা × কাটা নম্বর)। দুটি অপশন নিশ্চিতভাবে বাদ দিতে পেরেছেন আর ভুলে ০.২৫ কাটে: ০.৫ − ০.৫ × ০.২৫ = +০.৩৭৫ — লাভ। কিছুই না জেনে চারটি থেকে আন্দাজ আর ভুলে ০.৫ কাটে: ০.২৫ − ০.৭৫ × ০.৫ = −০.১২৫ — ক্ষতি। কত কাটে, পরীক্ষাভেদে আলাদা — নিজের পরীক্ষার নিয়ম আগে জেনে নিন।

ছয়টি বড় ফাঁদ — আর আরও কয়েকটি

নিচের টেবিলের প্রতিটি সারি এই পাতার একাধিক প্রশ্নে distractor হয়ে ফিরে আসবে। প্রশ্ন শুরুর আগে একবার চোখ বুলিয়ে নিন, আর প্রশ্ন শেষে ভুলগুলো কোন সারিতে পড়ল, মিলিয়ে দেখুন।

ফাঁদ	ভুল ধারণা	সঠিক কথা
log-এর ভিত্তি	“log₂ n আর log₁₀ n আলাদা শ্রেণি”; “log(n²) = log² n”	ভিত্তি শুধু ধ্রুবক গুণক — একই Θ; log(n²) = 2 log n, কিন্তু log² n = (log n)² বড়। তবে ঘাতে বসলে ভিত্তি গুরুত্বপূর্ণ: n^{log₂ 3} ≠ n^{log₄ 3}
Θ বনাম O	“O মানেই আঁটসাঁট সীমা”, “O মানেই worst case”	O শুধু ওপরের সীমা — n = O(n²) সত্য; Θ দুই দিকের সীমা। case আলাদা প্রশ্ন: worst case-এরও O, Ω, Θ আছে
stable sort	“সব O(n log n) sort stable”	merge, insertion, counting, Timsort stable; quick, heap, (swap-ভিত্তিক) selection unstable
worst বনাম average	“quick sort O(n log n)”, “hash table O(1)”	দুটিই গড়ের কথা; worst case যথাক্রমে Θ(n²) আর Θ(n)
heap বনাম BST	“heap-এ search log n”, “BST-তে সবসময় log n”	heap-এ search Θ(n); ভারসাম্যহীন BST-তে worst case Θ(n) — log n শুধু balanced BST-তে
BFS বনাম Dijkstra	“BFS যেকোনো graph-এ shortest path দেয়”, “Dijkstra সব জায়গায় চলে”	BFS শুধু weight-হীন (বা সমান weight); Dijkstra অঋণাত্মক weight; ঋণাত্মক edge-এ Bellman–Ford
amortized বনাম average	“push_back গড়ে O(1) — মানে ভাগ্য ভালো হলে”	amortized হলো পুরো কাজের ক্রমের নিশ্চিত গড় (সম্ভাবনা নেই); average/expected সম্ভাবনার ওপর নির্ভর
সংজ্ঞার রীতি	উচ্চতা, B-tree-র order, index — “সবাই একই রকম গোনে”	উচ্চতা edge না node-এ, 0 না 1-based, B-tree-র t না m — প্রশ্নে যা বলা, সেটিই ধরুন

এই পাতার প্রশ্নগুলো সম্পর্কে: প্রশ্নগুলো এই কোর্সের জন্য নতুন করে লেখা — বিশ্ববিদ্যালয়, চাকরির লিখিত পরীক্ষা আর ইন্টারভিউতে এ ধরনের প্রশ্ন প্রায়ই আসে, এমন ধারণা থেকে বানানো; কোনোটিই কোনো নির্দিষ্ট পরীক্ষার আসল প্রশ্ন নয়। প্রতিটি হিসাব আর trace-এর উত্তর প্রোগ্রাম চালিয়ে মিলিয়ে দেখা। অন্যভাবে বলা না থাকলে ধরে নিন: array 0-based, log মানে log₂, আর complexity মানে worst case.

২ · মডিউল ১ — শুরু ও বিশ্লেষণের ভিত্তি (১২টি প্রশ্ন)

এই অংশ পুরো কোর্সের ভাষা: Big-O, Ω আর Θ-এর সংজ্ঞা, লুপ গুনে সময় বের করা, best-worst-average case, loop invariant দিয়ে শুদ্ধতার প্রমাণ, রিকার্শনের call stack আর recurrence. চাকরির পরীক্ষায় সবচেয়ে বেশি আসে লুপের complexity আর Master theorem — আর ঠিক এখানেই “দুই লুপ মানে n²” ধরনের চেহারা দেখে উত্তরের ভুল সবচেয়ে বেশি।

যা ঝালিয়ে নেবেন

পর্ব ০২ · অ্যালগরিদম কী — অ্যালগরিদমের পাঁচ বৈশিষ্ট্য, RAM model
পর্ব ০৩ · loop invariant আর induction — initialization, maintenance, termination
পর্ব ০৪ · Big-O, Ω, Θ — c আর n₀ দিয়ে প্রমাণ, লুপ গোনা, log-এর ভিত্তি
পর্ব ০৫ · best, worst আর average case — গড় তুলনার হিসাব, space complexity
পর্ব ০৬ · DSA-র গণিত — জ্যামিতিক আর harmonic ধারা
পর্ব ০৭ · রিকার্শন আর পর্ব ০৮ · recurrence সমাধান — call stack-এর গভীরতা, recursion tree
পর্ব ০৯ · Master theorem — তিন case, regularity শর্ত আর gap

(সহজ) অ্যালগরিদমের প্রচলিত বৈশিষ্ট্যগুলোর (Knuth-এর তালিকা) মধ্যে কোনটি পড়ে না?

অ্যালগরিদমকে অবশ্যই রিকার্শন ব্যবহার করতে হবে
সসীমতা — সসীম সংখ্যক ধাপের পর অবশ্যই থামবে
সুনির্দিষ্টতা — প্রতিটি ধাপের অর্থ দ্ব্যর্থহীন
কার্যকারিতা — প্রতিটি ধাপ বাস্তবে, সীমিত সময়ে করা যায়

(সহজ) f(n) = 5n³ + 100n² log n + 7 — সবচেয়ে আঁটসাঁট Θ সীমা কোনটি?

Θ(n² log n)
Θ(n³ log n)
Θ(n⁵)
Θ(n³)

(মাঝারি) নিচের কোডের time complexity কত? for (i = n; i > 0; i /= 2) for (j = 0; j < i; j++) cnt++;

Θ(n log n)
Θ(log n)
Θ(n)
Θ(n²)

(কঠিন) নিচের কোডের time complexity কত? for (i = 1; i * i <= n; i++) for (j = i; j <= n; j += i) cnt++;

Θ(n√n)
Θ(n log n)
Θ(n)
Θ(√n log n)

(মাঝারি) Master theorem দিয়ে T(n) = 4T(n/2) + n² সমাধান করুন।

Θ(n²)
Θ(n³)
Θ(n² log n)
Θ(n log n)

(কঠিন) T(n) = 3T(n/4) + n log n — সমাধান কোনটি?

Θ(n log n)
Θ(n^0.79)
Θ(n log² n)
Master theorem প্রযোজ্য নয়, recursion tree লাগবেই

(কঠিন) T(n) = 2T(n/2) + n / log n সম্পর্কে কোনটি সঠিক?

Θ(n log n), case 2
Θ(n log log n); সাধারণ Master theorem-এর তিন case-এর কোনোটিই খাটে না
Θ(n), case 1
Θ(n / log n), case 3

(সহজ) T(n) = T(n − 1) + n, T(1) = 1 — সমাধান কোনটি?

Θ(n log n)
Θ(n)
Θ(2ⁿ)
Θ(n²)

(মাঝারি) insertion sort-এর বাইরের লুপের (i = 1 থেকে n − 1, 0-based) সঠিক loop invariant কোনটি?

A[0..i−1]-এ পুরো array-র সবচেয়ে ছোট i টি উপাদান সাজানো আছে
প্রতিটি ধাপের শুরুতে A[0..i−1]-এ মূল A[0..i−1]-এর উপাদানগুলোই আছে, আর সেগুলো সাজানো
A[i..n−1] অংশটি সাজানো
প্রতিটি ধাপে অন্তত একটি swap হয়

(সহজ) Θ(log(n²)) কোনটির সমান?

Θ(log n)
Θ(log² n)
Θ(n²)
Θ(√(log n))

(মাঝারি) সরল রিকার্সিভ fib(n) = fib(n−1) + fib(n−2) (memoization ছাড়া) — মোট সময় আর call stack-এর সর্বোচ্চ গভীরতা কত?

সময় Θ(2ⁿ), গভীরতা Θ(2ⁿ)
সময় Θ(n), গভীরতা Θ(n)
সময় Θ(n²), গভীরতা Θ(log n)
সময় Θ(φⁿ) (φ ≈ 1.618), গভীরতা Θ(n)

(মাঝারি) n উপাদানের array-তে খোঁজা key নিশ্চিতভাবে আছে, আর প্রতিটি অবস্থানে থাকার সম্ভাবনা সমান। linear search-এ গড়ে কতটি তুলনা লাগে?

n
log₂ n
(n + 1)/2
n/4

কঠিন প্রশ্নের ভেতরে — Master theorem যেখানে থেমে যায়

T(n) = 2T(n/2) + n / log n প্রশ্নটিতে সবচেয়ে বেশি ভুল হয়, কারণ তিনটি case-এর কোনো একটিতে জোর করে ফেলার ঝোঁক থাকে। নিচের ডায়াগ্রামে n = 256 নিয়ে recursion tree-র প্রতিটি স্তরের কাজ হিসাব করা হয়েছে — সংখ্যাগুলো দেখলেই বোঝা যায় কেন কোনো case খাটে না।

প্রস্তুতিa = 2, b = 2, f(n) = n / log₂ n

n = 256  →  k = log₂ n = 8 টি স্তর (0 থেকে 7), তারপর পাতা

n^{log_b a} = n¹ = n
f(n) = n / log n   →   n-এর চেয়ে ছোট,
কিন্তু শুধু log গুণকে ছোট — polynomially ছোট নয়

স্তর i-এর কাজnode সংখ্যা × প্রতিটির কাজ

স্তর i:  2^i টি node, প্রতিটির আকার n / 2^i

কাজ = 2^i × (n / 2^i) / log₂(n / 2^i)
     = n / (k − i)

i = 0:  256 / 8 = 32
i = 7:  256 / 1 = 256

আট স্তরের কাজসমানও নয়, জ্যামিতিকও নয়

স্তর   0     1     2     3     4     5     6     7
কাজ   32  36.6  42.7  51.2   64  85.3  128   256

case 2 হলে সব স্তর সমান হতো       ✗
case 1 / 3 হলে জ্যামিতিক হারে বদলাত ✗
এখানে কাজ = n × (1/8, 1/7, …, 1/1)

যোগফলharmonic ধারা লুকিয়ে আছে

মোট = n (1/1 + 1/2 + … + 1/k) = n · H_k
     = 256 × 2.718 ≈ 695.8
     (+ 256টি পাতার Θ(n) কাজ — শ্রেণি বদলায় না)

H_k ≈ ln k  এবং  k = log n
=>  T(n) = Θ(n log log n)

অপশন বাদn = 256-এ সংখ্যা মিলিয়ে দেখা

Θ(n)        → 256           (খুব ছোট)
Θ(n log n)  → 256 × 8 = 2048 (খুব বড়)
স্তরগুলোর যোগ ≈ 696  — দুটির মাঝে

উত্তর: Θ(n log log n), Master theorem-এর gap

a, b, f(n) চিনুন। a = 2, b = 2, তাই critical অংশ n^{log₂ 2} = n. f(n) = n / log n — n-এর চেয়ে ছোট, কিন্তু শুধু একটি log গুণকে। case 1 চায় f(n) = O(n^1−ε) কোনো ε > 0-এর জন্য, অর্থাৎ polynomially ছোট। log n যেকোনো n^ε-এর চেয়ে ধীরে বাড়ে, তাই এই শর্ত পূরণ হয় না। n = 256 নিলে স্তর 8টি।
প্রতিটি স্তরের কাজ লিখুন। স্তর i-এ 2ⁱটি উপ-সমস্যা, প্রতিটির আকার n/2ⁱ, আর প্রতিটির নিজের কাজ (n/2ⁱ) / log(n/2ⁱ). গুণ করলে 2ⁱ কেটে যায়: স্তরের মোট কাজ n / (k − i). প্রথম স্তরে 256/8 = 32, শেষ স্তরে 256/1 = 256.
স্তরগুলোর ধাঁচ দেখুন। 32, 36.6, 42.7, 51.2, 64, 85.3, 128, 256 — সমান নয় (case 2-এ হতো), আবার স্থির অনুপাতে জ্যামিতিক হারেও বাড়ছে না (case 1-এ পাতার দিকে জ্যামিতিক বৃদ্ধি হতো)। এই “মাঝামাঝি” অবস্থাটিই Master theorem-এর gap.
যোগফলে harmonic ধারা। মোট = n(1/8 + 1/7 + … + 1/1) = n · H₈ ≈ 256 × 2.718 ≈ 695.8; সাথে 256টি পাতার ধ্রুবক কাজ, যা Θ(n) — শ্রেণি বদলায় না। সাধারণভাবে H_k ≈ ln k, আর k = log n, তাই T(n) = Θ(n log log n).
সংখ্যা দিয়ে অপশন বাদ। n = 256-এ Θ(n) মানে প্রায় 256, Θ(n log n) মানে প্রায় 2048 — স্তরগুলোর যোগফল 696 দুটির মাঝে। একটি সংখ্যা প্রমাণ নয়, কিন্তু ভুল case বাছাই সাথে সাথে ধরা পড়ে। এ ধরনের gap-এর প্রশ্নে উত্তর প্রায়ই “Master theorem প্রযোজ্য নয়” আর সাথে recursion tree-র ফল।

৩ · মডিউল ২ — লিনিয়ার ডেটা স্ট্রাকচার (১২টি প্রশ্ন)

array-র ঠিকানার হিসাব, dynamic array-র resize, linked list-এর কোন কাজ কত সময়ে, stack-queue-র output, circular queue-র wrap-around, prefix sum আর difference array-র index, আর sliding window — এই মডিউলের প্রশ্নে off-by-one ভুলই বেশি। প্রতিটি index-প্রশ্নে খাতায় ছোট একটি টেবিল আঁকুন।

যা ঝালিয়ে নেবেন

পর্ব ১০ · Array আর dynamic array — ঠিকানার সূত্র, capacity দ্বিগুণের amortized হিসাব
পর্ব ১১ · String — জোড়া লাগানোর লুকানো খরচ
পর্ব ১২ · Linked list — singly বনাম doubly, tail pointer
পর্ব ১৩ · Stack আর পর্ব ১৪ · Queue আর deque — LIFO, FIFO, circular buffer
পর্ব ১৫ · C++ STL আর Python-এর কালেকশন — map বনাম unordered_map
পর্ব ১৬ · Two pointer আর sliding window — কখন একমুখী pointer চলে
পর্ব ১৭ · Prefix sum আর difference array — P[r + 1] − P[l]

(সহজ) capacity শেষ হলে প্রতিবার দ্বিগুণ করে বাড়ানো dynamic array-তে (যেমন std::vector) খালি অবস্থা থেকে n বার push_back করলে মোট খরচ কত?

Θ(n²)
Θ(n) — অর্থাৎ প্রতি push_back-এর amortized খরচ O(1)
Θ(n log n)
প্রতিটি push_back worst case-এও O(1), তাই মোট Θ(n)

(মাঝারি) একটি dynamic array-র capacity দ্বিগুণ না করে প্রতিবার মাত্র 10 ঘর বাড়ানো হয়। n বার push_back-এর মোট খরচ কত?

Θ(n)
Θ(n log n)
Θ(10n) = Θ(n), কারণ 10 একটি ধ্রুবক
Θ(n²)

(সহজ) একটি expression-এ (), {}, [] বন্ধনী ঠিকমতো জোড়া মেলানো কি না যাচাই করতে কোন ডেটা স্ট্রাকচার সবচেয়ে উপযুক্ত?

Stack
Queue
Min-heap
Hash table

(মাঝারি) নিচের C++ কোডের output কী? stack<int> s; queue<int> q; for (x = 1..6) { if (x % 3 == 0) { q.push(s.top()); s.pop(); } else s.push(x); } — তারপর queue-র সব উপাদান সামনে থেকে ছাপা হয়, শেষে “| ” আর s.top().

3 6 | 5
1 4 | 1
2 5 | 4
2 5 | 1

(মাঝারি) একটি singly linked list-এ head আর tail দুটি pointer-ই রাখা আছে। কোন কাজটি O(1)-এ করা যায় না?

শেষ node মুছে ফেলা
শেষে নতুন node যোগ করা
প্রথম node মুছে ফেলা
শুরুতে নতুন node যোগ করা

(সহজ) int A[100]-এর শুরুর ঠিকানা (base address) 1000, প্রতিটি int 4 byte. A[25]-এর ঠিকানা কত?

1025
1104
1100
1096

(মাঝারি) A = [3, 1, 4, 1, 5, 9, 2, 6], prefix array P[0] = 0 আর P[i] = A[0] + … + A[i−1]. 0-based A[2..5]-এর (দুই প্রান্তসহ) যোগফল কোনটি?

P[5] − P[2] = 10
P[6] − P[1] = 20
P[5] − P[1] = 11
P[6] − P[2] = 19

(মাঝারি) ছয় ঘরের শূন্য array-তে difference array দিয়ে দুটি কাজ: 0-based [1, 3]-এ 5 যোগ, তারপর [2, 5]-এ 2 যোগ। শেষে prefix sum নিলে array কী হবে?

[0, 5, 7, 7, 7, 2]
[0, 5, 7, 7, 2, 2]
[0, 5, 2, 0, −5, 0]
[0, 7, 7, 7, 2, 2]

(কঠিন) ধনাত্মক পূর্ণসংখ্যার array-তে যোগফল ≥ S এমন সবচেয়ে ছোট দৈর্ঘ্যের contiguous subarray খুঁজতে সবচেয়ে দক্ষ পদ্ধতি কোনটি?

sliding window: ডান pointer বাড়িয়ে যোগ করা, যোগফল ≥ S হলেই বাঁ pointer যতটা পারা যায় সরানো — Θ(n)
সব subarray যাচাই — Θ(n²)
array sort করে বড় থেকে নেওয়া — Θ(n log n)
Kadane-এর অ্যালগরিদম — Θ(n)

(কঠিন) C++-এর std::map আর std::unordered_map সম্পর্কে কোনটি সত্য?

দুটিই hash table, শুধু map key সাজিয়ে রাখে
map-এ key সাজানো ক্রমে থাকে আর প্রতি কাজ O(log n); unordered_map গড়ে O(1), কিন্তু worst case-এ O(n)
unordered_map-এর প্রতিটি কাজ worst case-এও O(1)
map গড়ে O(1), কারণ ভেতরে বড় array থাকে

(মাঝারি) C++-এ খালি string থেকে শুরু করে n বার একটি অক্ষর যোগ করা হলো — একবার s = s + c; দিয়ে, আরেকবার s += c; দিয়ে। মোট সময়?

দুটিই Θ(n)
দুটিই Θ(n²)
s += c-এ Θ(n log n)
s = s + c-এ Θ(n²), s += c-এ মোট Θ(n)

(সহজ) array দিয়ে বানানো circular queue-র capacity 8, front index 6, আর এখন 4টি উপাদান আছে। পরের enqueue কোন index-এ বসবে?

stack আর queue-র output প্রশ্নটি নিচে চালিয়ে দেখুন। প্রতিটি তৃতীয় মানে stack-এর top সরে যায় queue-তে:

#include <iostream>
#include <queue>
#include <stack>

int main() {
    std::stack<int> s;
    std::queue<int> q;
    for (int x = 1; x <= 6; x++) {
        if (x % 3 == 0) {          // every third value: move the stack top
            q.push(s.top());
            s.pop();
        } else {
            s.push(x);
        }
    }
    while (!q.empty()) {
        std::cout << q.front() << ' ';
        q.pop();
    }
    std::cout << "| " << s.top() << '\n';
}

output: 2 5 | 4. x = 1, 2-এ stack হয় [1, 2]; x = 3-এ top 2 যায় queue-তে, stack [1]. x = 4, 5-এ stack [1, 4, 5]; x = 6-এ top 5 যায় queue-তে, stack [1, 4]. queue সামনে থেকে ছাপে 2, 5; stack-এর top 4. চেষ্টা করুন: x % 3-কে x % 2 করে আগে খাতায় উত্তর লিখুন, তারপর চালিয়ে মেলান।

৪ · মডিউল ৩ — সার্চিং ও সর্টিং (১২টি প্রশ্ন)

সব পরীক্ষার প্রিয় মডিউল। binary search-এর ধাপ আর lower_bound, “pass k-এর পর array”, কোন sort stable, quick sort-এর worst case, heap-এর insert trace, counting sort আর radix sort-এর সময়, তুলনা-ভিত্তিক sort-এর Ω(n log n) নিম্নসীমা আর উত্তরের ওপর binary search-এর শর্ত। এখানে worst বনাম average-এর ফাঁদ সবচেয়ে বেশি।

যা ঝালিয়ে নেবেন

পর্ব ১৮ · Linear আর binary search — ⌊log₂ n⌋ + 1, lower_bound/upper_bound
পর্ব ১৯ · উত্তরের ওপর binary search — monotonic feasible(x)
পর্ব ২০ · bubble, selection আর insertion — প্রতিটি pass-এর অবস্থা, stability
পর্ব ২১ · Merge sort আর পর্ব ২২ · Quick sort ও quickselect — partition, pivot, Θ(n) selection
পর্ব ২৩ · Heap আর priority queue — sift-up, build-heap Θ(n)
পর্ব ২৪ · Counting, radix, bucket sort — Θ(n + k), decision tree-র নিম্নসীমা
পর্ব ২৫ · বাস্তবে সর্টিং — stable sort, Timsort, introsort

(সহজ) 1000টি সাজানো উপাদানে binary search — প্রতি ধাপে মাঝের একটি উপাদান দেখা হয়। সবচেয়ে খারাপ ক্ষেত্রে সর্বোচ্চ কতটি উপাদান দেখতে হবে?

(মাঝারি) v = {1, 3, 3, 3, 5, 8}. lower_bound(v.begin(), v.end(), 3) − v.begin() আর upper_bound(…, 3) − v.begin() কত?

1 আর 4
1 আর 3
0 আর 4
2 আর 4

(মাঝারি) [5, 1, 4, 2, 8, 3]-এ bubble sort (প্রতি pass-এ বাঁ থেকে ডানে পাশাপাশি জোড়া তুলনা, বড়টি ডানে) — দ্বিতীয় pass শেষে array কী?

[1, 2, 3, 4, 5, 8]
[1, 4, 2, 5, 3, 8]
[1, 2, 4, 3, 5, 8]
[1, 2, 4, 5, 3, 8]

(মাঝারি) প্রচলিত বাস্তবায়নে কোন তিনটি সর্টিং অ্যালগরিদমই stable?

quick sort, heap sort, merge sort
selection sort, insertion sort, heap sort
heap sort, counting sort, bubble sort
insertion sort, merge sort, counting sort

(কঠিন) decision tree যুক্তি অনুযায়ী n টি ভিন্ন উপাদান সাজাতে যেকোনো তুলনা-ভিত্তিক sort-এর worst case-এ কতটি তুলনা অন্তত লাগে, আর কেন?

⌈log₂(n!)⌉ = Ω(n log n) — কারণ decision tree-তে অন্তত n! টি পাতা লাগে
n − 1 — কারণ প্রতিটি উপাদানকে অন্তত একবার তুলনা করতে হয়
n(n − 1)/2 — কারণ সব জোড়া তুলনা করতে হয়
log₂ n — কারণ binary search-এর মতো অর্ধেক করা যায়

(মাঝারি) Lomuto partition, প্রতিবার শেষ উপাদানকে pivot — আগে থেকেই সাজানো n উপাদানের array-তে quick sort-এর সময় কত?

Θ(n log n)
Θ(n)
Θ(n²)
Θ(log n)

(কঠিন) k-তম ছোট উপাদান খোঁজার পদ্ধতি নিয়ে কোনটি সত্য?

randomized quickselect-এর expected সময় Θ(n log n)
পুরো array sort না করে k-তম উপাদান পাওয়া যায় না, তাই Ω(n log n)
median-of-medians-এর worst case Θ(n log n)
randomized quickselect-এর expected সময় Θ(n), worst case Θ(n²); median-of-medians-এর worst case Θ(n)

(মাঝারি) n টি উপাদান থেকে bottom-up (Floyd-এর) পদ্ধতিতে binary heap বানাতে সময় কত?

Θ(n log n)
Θ(n)
Θ(log n)
Θ(n²)

(মাঝারি) max-heap-এর array রূপ [9, 7, 8, 3, 5, 6] (0-based, parent(i) = (i − 1)/2). 10 insert করার পর array কী হবে?

[10, 9, 7, 8, 3, 5, 6]
[9, 7, 10, 3, 5, 6, 8]
[10, 7, 8, 3, 5, 6, 9]
[10, 7, 9, 3, 5, 6, 8]

(মাঝারি) n টি পূর্ণসংখ্যা, প্রতিটি 0 থেকে k − 1-এর মধ্যে। counting sort-এর সময় আর বাড়তি জায়গা কত?

সময় Θ(n + k), জায়গা Θ(n + k)
সময় Θ(n log n), জায়গা Θ(n)
সময় Θ(nk), জায়গা Θ(k)
সময় Θ(n), জায়গা Θ(1)

(কঠিন) n = 10⁶টি 32-bit unsigned পূর্ণসংখ্যা LSD radix sort দিয়ে সাজানো হবে, প্রতি pass-এ 8 bit (base 256) ধরে। কতটি pass, আর মোট কাজ?

32টি pass, মোট Θ(n log n)
8টি pass, মোট Θ(n)
4টি pass, মোট Θ(4 · (n + 256)) = Θ(n)
1টি pass, মোট Θ(n + 2³²)

(মাঝারি) “উত্তরের ওপর binary search” (binary search on answer) চালাতে কোন শর্তটি অপরিহার্য?

input array আগে থেকে সাজানো থাকতে হবে
feasible(x) monotonic — কোনো x-এ সম্ভব হলে তার চেয়ে বড় সব x-এও সম্ভব (বা উল্টোটা)
উত্তর অবশ্যই পূর্ণসংখ্যা হতে হবে
n একটি 2-এর ঘাত হতে হবে

bubble sort-এর “pass 2-এর পর” প্রশ্নটি নিচের কোড প্রতিটি pass-এর শেষে array ছেপে মিলিয়ে দেয়:

#include <iostream>
#include <utility>
#include <vector>

int main() {
    std::vector<int> a = {5, 1, 4, 2, 8, 3};
    int n = a.size();
    for (int pass = 1; pass < n; pass++) {
        bool swapped = false;
        for (int j = 0; j + pass < n; j++)
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        std::cout << "pass " << pass << ":";
        for (int x : a) std::cout << ' ' << x;
        std::cout << '\n';
        if (!swapped) break;   // no swap: already sorted
    }
}

output-এর চার লাইন: pass 1: 1 4 2 5 3 8, pass 2: 1 2 4 3 5 8, pass 3: 1 2 3 4 5 8, pass 4: 1 2 3 4 5 8. pass 3-এই array সাজানো হয়ে যায়, কিন্তু অ্যালগরিদম তা জানে কেবল pass 4-এ একটিও swap না হলে — তাই সেখানে থামে। প্রতি pass-এ সবচেয়ে বড় বাকি উপাদানটি শেষে পৌঁছায় (8, তারপর 5, তারপর 4), এজন্যই ভেতরের লুপ প্রতিবার এক ঘর কম চলে।

৫ · মডিউল ৪ — ট্রি, হ্যাশ ও DSU (১২টি প্রশ্ন)

tree traversal আর preorder + inorder থেকে tree বানানো, BST-এ insert-delete, AVL-এর rotation আর সর্বনিম্ন node, red-black tree-এর নিয়ম, B-tree-এর key-সীমা, trie, hash table-এর load factor আর linear probing, আর DSU-র inverse Ackermann সীমা। tree-র প্রশ্নে সবসময় আগে ছবিটি আঁকুন — মাথায় traversal করলে বাঁ-ডান গুলিয়ে যায়।

যা ঝালিয়ে নেবেন

পর্ব ২৬ · Tree — preorder, inorder, postorder, দুটি traversal থেকে tree
পর্ব ২৭ · Binary search tree — successor দিয়ে delete, degenerate tree
পর্ব ২৮ · AVL tree — LL/LR/RL/RR, N(h) = N(h−1) + N(h−2) + 1
পর্ব ২৯ · Red-black tree — black-height, উচ্চতা ≤ 2 log₂(n + 1)
পর্ব ৩০ · B-tree আর B+ tree — t − 1 থেকে 2t − 1 টি key
পর্ব ৩১ · Trie — O(L) খোঁজা
পর্ব ৩২ · Hash table — chaining, probing, α = n/m
পর্ব ৩৩ · Disjoint set union — union by rank + path compression

(সহজ) একটি binary tree: root A; A-র বাঁয়ে B, ডানে C; B-র বাঁয়ে D, ডানে E; C-র ডানে F. postorder traversal কী?

A B D E C F
D B E A C F
D E B F C A
D E F B C A

(মাঝারি) একটি binary tree-র preorder A B D E C F G আর inorder D B E A F C G. postorder কী?

D E B F G C A
D E B G F C A
D B E F C G A
E D B F G C A

(মাঝারি) খালি BST-তে 50, 30, 70, 20, 40, 60, 80, 35 ক্রমে insert করা হলো। তারপর 30 মোছা হলো (দুই সন্তান থাকলে inorder successor দিয়ে প্রতিস্থাপন)। এখন preorder কী?

50 20 40 35 70 60 80
50 40 20 35 70 60 80
50 35 40 20 70 60 80
50 35 20 40 70 60 80

(সহজ) 1, 2, 3, …, n ক্রমে একটি সাধারণ (ভারসাম্যহীন) BST-তে insert করলে একটি search-এর worst case কত?

Θ(log n)
Θ(n)
Θ(1)
Θ(n log n)

(মাঝারি) উচ্চতা 4 (edge গুনে; এক node-এর tree-র উচ্চতা 0) এমন AVL tree-তে সর্বনিম্ন কতটি node থাকতে পারে?

(মাঝারি) খালি AVL tree-তে 30, 10, 20 ক্রমে insert করার পর কী করতে হয়, আর root কে হয়?

single right rotation; root 10
কোনো rotation লাগে না; root 30
RL double rotation; root 20
LR ক্ষেত্র — প্রথমে 10-এ left rotation, তারপর 30-এ right rotation; root 20

(মাঝারি) red-black tree সম্পর্কে কোনটি সত্য?

প্রতিটি লাল node-এর অন্তত একটি সন্তান লাল
সব পাতা একই গভীরতায় থাকে
root থেকে যেকোনো NIL পাতা পর্যন্ত প্রতিটি পথে কালো node-এর সংখ্যা সমান, তাই n key-তে উচ্চতা ≤ 2 log₂(n + 1)
red-black tree সবসময় AVL tree-র চেয়ে বেশি ভারসাম্যপূর্ণ

(কঠিন) minimum degree t = 3 (CLRS-এর সংজ্ঞা) এমন B-tree-তে root ছাড়া প্রতিটি node-এ key-র সংখ্যা কোন সীমার মধ্যে থাকে?

3 থেকে 6
2 থেকে 5
1 থেকে 3
3 থেকে 5

(সহজ) n টি শব্দ রাখা একটি trie-তে দৈর্ঘ্য L-এর একটি শব্দ খুঁজতে সময় কত (প্রতি node-এ সন্তান খুঁজে পাওয়া O(1) ধরে)?

O(log n)
O(n · L)
O(n)
O(L) — শব্দের সংখ্যা n-এর ওপর নির্ভর করে না

(মাঝারি) separate chaining-ভিত্তিক hash table-এ m = 100 টি bucket আর n = 300 টি key. simple uniform hashing ধরে একটি ব্যর্থ search-এ গড়ে কতটি key-র সাথে তুলনা হয়?

300
100
3
log₂ 300 ≈ 8

(মাঝারি) আকার 7, h(k) = k mod 7, linear probing. খালি table-এ 10, 17, 24, 3 ক্রমে insert করা হলো। key 3 কোন index-এ বসবে?

(মাঝারি) union by rank আর path compression দুটি একসাথে ব্যবহার করা disjoint set union-এ m টি কাজের (n টি উপাদান) মোট সময় কত?

প্রতি কাজ worst case-এ O(log n), তার চেয়ে ভালো নয়
O(m · α(n)), α = inverse Ackermann — বাস্তবে প্রতি কাজ প্রায় ধ্রুবক
প্রতি কাজ worst case-এও O(1)
প্রতি find O(n)

৬ · মডিউল ৫ — রেঞ্জ কোয়েরি ও উন্নত স্ট্রাকচার (১১টি প্রশ্ন)

চাকরির সাধারণ পরীক্ষায় এই মডিউল কম আসে, কিন্তু সফটওয়্যার ইঞ্জিনিয়ারের screening, বিশ্ববিদ্যালয়ের উন্নত কোর্স আর কনটেস্টে প্রায় নিশ্চিত। মূল প্রশ্ন একটিই: কোন কাজগুলো লাগবে (point না range update, sum না min, online না offline), আর সেই অনুযায়ী segment tree, lazy propagation, Fenwick tree, sparse table, sqrt decomposition, Mo’s algorithm নাকি treap.

যা ঝালিয়ে নেবেন

পর্ব ৩৪ · Segment tree — build Θ(n), query/update Θ(log n), 4n array
পর্ব ৩৫ · Lazy propagation — tag আর দৈর্ঘ্য দিয়ে গুণ
পর্ব ৩৬ · Fenwick tree (BIT) — i & (−i), query আর update-এর পথ
পর্ব ৩৭ · Sparse table, sqrt decomposition আর Mo’s — idempotent কাজ, O((n + q)√n)
পর্ব ৩৮ · Treap আর skip list — এলোমেলো priority, expected log n

(সহজ) n উপাদানের segment tree-তে build, point update আর range query-র সময় কত?

build Θ(n log n), query Θ(1)
build Θ(n), query Θ(n)
update Θ(n), query Θ(log n)
build Θ(n), point update আর range query দুটিই Θ(log n)

(মাঝারি) 1-based array-তে রাখা recursive segment tree-তে (সন্তান 2i আর 2i + 1) n উপাদানের জন্য নিরাপদ array আকার সাধারণত কত নেওয়া হয়?

n
2n
4n
n log n

(কঠিন) range add আর range sum-এর lazy segment tree-তে একটি node [l, r] অংশ ঢাকে। সেই node-এ v যোগের lazy tag বসানোর সময় node-এর sum কতটা বাড়াতে হয়?

v × (r − l + 1)
v
v × log n
v × (r − l)

(মাঝারি) 1-based Fenwick tree (BIT)-তে prefix sum(13) বের করতে কোন index-গুলোর মান পড়া হয়?

13, 14, 16
13, 12, 8
13, 11, 7, 3
1, 2, 4, 8

(মাঝারি) sparse table দিয়ে range minimum O(1)-এ পাওয়া যায়, কিন্তু সাধারণ range sum O(1)-এ নয় — কারণ কী?

sum-এর জন্য বেশি মেমরি লাগে
যোগ associative নয়
sparse table-এ update করা যায় না বলে
min idempotent — দুটি overlapping অংশ একসাথে নিলেও ফল বদলায় না; যোগফলে overlapping অংশ দুবার গোনা হয়

(মাঝারি) n উপাদানের range minimum-এর sparse table সম্পর্কে কোনটি সত্য?

build Θ(n log n) সময় ও জায়গা, query Θ(1), আর point update সমর্থন করে না (পুনর্গঠন লাগে)
build Θ(n), query Θ(log n)
point update Θ(log n)-এ করা যায়
build Θ(n²)

(কঠিন) Mo’s algorithm দিয়ে n দৈর্ঘ্যের array-তে q টি offline range query (প্রতিটি add/remove O(1)), block size ≈ √n — মোট সময় কত?

O(q log n)
O((n + q)√n)
O(n · q)
O(n log n + q)

(মাঝারি) √n আকারের block-এ ভাগ করা sqrt decomposition-এ (প্রতি block-এর যোগফল রাখা) point update আর range sum query-র সময় কত?

query O(log n)
query O(1)
point update O(1), range query O(√n)
query O(n / log n)

(মাঝারি) treap সম্পর্কে কোনটি সত্য?

key অনুযায়ী heap আর priority অনুযায়ী BST
key অনুযায়ী এটি BST আর এলোমেলো priority অনুযায়ী heap — expected উচ্চতা O(log n)
worst case উচ্চতাও সবসময় O(log n) নিশ্চিত
priority ব্যবহারকারী key-র ক্রম অনুযায়ী বেছে দেন

(কঠিন) n = 10⁵ উপাদানের array-তে দুই ধরনের কাজ মিলিয়ে 10⁵ বার: [l, r]-এর সব উপাদানে x যোগ, আর [l, r]-এর সর্বনিম্ন মান। কোন ডেটা স্ট্রাকচার সবচেয়ে উপযুক্ত?

prefix sum array
সাধারণ Fenwick tree
lazy propagation-সহ segment tree
sparse table

(মাঝারি) সাধারণ Fenwick tree (BIT) কোন কাজের জন্য সরাসরি উপযুক্ত নয়?

যেকোনো নতুন মান বসানো point update আর যেকোনো [l, r]-এর সর্বনিম্ন
point update আর prefix sum
range update আর point query
inversion গোনা

৭ · মডিউল ৬ — গ্রাফ অ্যালগরিদম (১৪টি প্রশ্ন)

graph-এর প্রশ্নে প্রথম কাজ ইনপুটের শর্ত পড়া: directed না undirected, weight আছে কি না, ঋণাত্মক weight, DAG কি না। এই চারটি থেকেই ঠিক হয় BFS, 0-1 BFS, Dijkstra, Bellman–Ford না Floyd–Warshall. তারপর আসে trace — DFS-এর ক্রম, Dijkstra-র settle ক্রম, topological order, Kruskal-এর MST — আর তত্ত্ব: cut property, max-flow min-cut, bridge-এর শর্ত, binary lifting.

যা ঝালিয়ে নেবেন

পর্ব ৩৯ · গ্রাফ — adjacency list বনাম matrix
পর্ব ৪০ · BFS আর পর্ব ৪১ · DFS — স্তর ধরে দূরত্ব, 0-1 BFS, DFS-এর ক্রম
পর্ব ৪২ · Topological sort — প্রতিটি edge-এ u আগে
পর্ব ৪৩ · Dijkstra — settle-এর যুক্তি, ঋণাত্মক edge-এ কেন ভাঙে
পর্ব ৪৪ · Bellman–Ford আর Floyd–Warshall — V − 1 রাউন্ড, k বাইরে
পর্ব ৪৫ · MST — Kruskal, Prim, cut আর cycle property
পর্ব ৪৬ · SCC, bridge আর articulation point — low[v] > disc[u]
পর্ব ৪৭ · Network flow — max-flow = min-cut
পর্ব ৪৮ · LCA আর binary lifting — n log n টেবিল, log n query

(সহজ) V = 10⁵ টি vertex আর E = 2 × 10⁵ টি edge-এর একটি sparse graph-এ BFS চালাতে হবে। কোন উপস্থাপন বেছে নেবেন?

adjacency matrix — যেকোনো edge যাচাই O(1)
sorted edge list — শুধু edge-গুলোর একটি তালিকা
incidence matrix (V × E)
adjacency list — মেমরি Θ(V + E), প্রতিটি vertex-এর প্রতিবেশী সরাসরি পাওয়া যায়

(মাঝারি) undirected graph: 1: {2, 3}, 2: {1, 4, 5}, 3: {1, 6}, 4: {2}, 5: {2, 6}, 6: {3, 5}. 1 থেকে recursive DFS (ছোট নম্বরের প্রতিবেশী আগে) — vertex দেখার ক্রম কী?

1 2 3 4 5 6
1 2 4 5 6 3
1 2 4 5 3 6
1 3 6 5 2 4

(সহজ) weight-হীন (unweighted) graph-এ একটি উৎস থেকে সব vertex-এর সবচেয়ে ছোট পথ (edge সংখ্যায়) বের করতে সবচেয়ে উপযুক্ত পদ্ধতি কোনটি?

BFS — Θ(V + E)
heap-সহ Dijkstra — O((V + E) log V)
DFS — Θ(V + E)
Floyd–Warshall — Θ(V³)

(কঠিন) একটি directed graph-এ প্রতিটি edge-এর weight 0 অথবা 1. একটি উৎস থেকে সবচেয়ে ছোট দূরত্ব বের করার সবচেয়ে দক্ষ পদ্ধতি কোনটি?

সাধারণ BFS — শুধু edge সংখ্যা গুনে
Bellman–Ford — কারণ 0 weight-এ Dijkstra চলে না
deque-ভিত্তিক 0-1 BFS — weight 0 হলে সামনে, 1 হলে পেছনে push; Θ(V + E)
DFS-এ সব পথ ঘুরে দেখা

(মাঝারি) কোন অবস্থায় Dijkstra-র অ্যালগরিদম ভুল উত্তর দিতে পারে?

graph directed হলে
সব edge-এর weight সমান হলে
graph-এ cycle থাকলে
কোনো edge-এর weight ঋণাত্মক হলে — negative cycle না থাকলেও

(মাঝারি) directed graph: A→B (4), A→C (1), C→B (2), B→D (1), C→D (5). A থেকে Dijkstra চালালে D-র দূরত্ব আর vertex settle হওয়ার ক্রম কী?

d(D) = 5; ক্রম A, B, C, D
d(D) = 4; ক্রম A, C, B, D
d(D) = 6; ক্রম A, C, D, B
d(D) = 4; ক্রম A, B, C, D

(মাঝারি) DAG-এর edge: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1. কোনটি একটি বৈধ topological order?

4 5 0 2 1 3
5 2 1 4 3 0
2 5 4 3 0 1
5 4 2 3 1 0

(মাঝারি) Bellman–Ford সম্পর্কে কোনটি সত্য?

Θ(V log V) সময়, ঋণাত্মক edge-এ কাজ করে না
Θ(E log V) সময়
Θ(V · E) সময়; V − 1 রাউন্ডের পরেও কোনো edge relax হলে উৎস থেকে পৌঁছানো যায় এমন negative cycle আছে
Θ(V + E) সময়, তবে শুধু DAG-এ

(মাঝারি) Floyd–Warshall-এর তিনটি nested লুপ সম্পর্কে কোনটি সঠিক?

মধ্যবর্তী vertex k-এর লুপ সবার বাইরে; সময় Θ(V³), জায়গা Θ(V²)
i-এর লুপ সবার বাইরে, k সবার ভেতরে
তিনটি লুপের ক্রম যেকোনো রকম হতে পারে
Θ(V³) জায়গা লাগে

(কঠিন) undirected weighted graph-এর edge: (A, B, 1), (B, C, 2), (A, C, 3), (C, D, 4), (B, D, 5), (D, E, 6), (C, E, 7). Minimum spanning tree-র মোট weight কত?

(মাঝারি) minimum spanning tree নিয়ে কোনটি সত্য?

graph-এর সবচেয়ে ভারী edge কখনো MST-তে থাকে না
MST আর একটি উৎসের shortest path tree সবসময় একই
ঋণাত্মক weight থাকলে Kruskal ভুল উত্তর দেয়
যেকোনো cut পার হওয়া edge-গুলোর মধ্যে সবচেয়ে হালকাটি (অনন্য হলে) প্রতিটি MST-তে থাকে

(মাঝারি) একটি flow network-এ সর্বোচ্চ s-t flow-এর মান 15. কোনটি নিশ্চিতভাবে সত্য?

সবচেয়ে ছোট capacity-র s-t cut-এর capacity ঠিক 15
network-এর প্রতিটি edge পূর্ণ (saturated)
s থেকে বের হওয়া edge-গুলোর capacity-র যোগফল 15
ঠিক 15টি augmenting path পাওয়া যাবে

(কঠিন) connected undirected graph-এ DFS tree-র একটি tree edge (u, v), যেখানে v হলো u-এর সন্তান। কখন (u, v) একটি bridge?

low[v] ≥ disc[u]
low[v] < disc[u]
low[v] > disc[u]
disc[v] > disc[u]

(মাঝারি) n node-এর rooted tree-তে binary lifting দিয়ে lowest common ancestor (LCA)-এর preprocessing আর প্রতি query-র সময় কত?

preprocessing Θ(n log n), প্রতি query O(log n)
preprocessing Θ(n), প্রতি query O(1)
preprocessing নেই, প্রতি query Θ(n)
preprocessing Θ(n²), প্রতি query O(1)

trace প্রশ্নের খাতা — Dijkstra-র settle ক্রম

Dijkstra-র trace প্রশ্নে দুটি ভুল সবচেয়ে বেশি: প্রথম পাওয়া দূরত্বকেই চূড়ান্ত ধরা, আর heap থেকে কে আগে বের হবে তা গুলিয়ে ফেলা। নিচে প্রশ্নের graph-টি (A→B 4, A→C 1, C→B 2, B→D 1, C→D 5) টেবিল ধরে চালানো হয়েছে — পরীক্ষার খাতায় ঠিক এভাবেই লিখুন।

শুরুউৎস 0, বাকি সবাই ∞

vertex     A    B    C    D
dist       0    ∞    ∞    ∞
settled    -    -    -    -

heap: (0, A)

A settleA-এর দুটি edge relax

vertex     A    B    C    D
dist       0    4    1    ∞
settled    ✓    -    -    -

relax: A→B = 0 + 4 = 4,  A→C = 0 + 1 = 1
heap: (1, C), (4, B)

C settleসবচেয়ে ছোট অস্থায়ী মান 1

vertex     A    B    C    D
dist       0    3    1    6
settled    ✓    -    ✓    -

relax: C→B = 1 + 2 = 3 < 4  → B হালনাগাদ
       C→D = 1 + 5 = 6 < ∞  → D = 6
heap: (3, B), (4, B — পুরোনো), (6, D)

B settle3-এ — পুরোনো (4, B) পরে উপেক্ষিত

vertex     A    B    C    D
dist       0    3    1    4
settled    ✓    ✓    ✓    -

relax: B→D = 3 + 1 = 4 < 6  → D হালনাগাদ
heap: (4, B — পুরোনো), (4, D), (6, D — পুরোনো)

D settle, শেষউত্তর মেলানো

vertex     A    B    C    D
dist       0    3    1    4
settled    ✓    ✓    ✓    ✓

settle ক্রম: A, C, B, D      d(D) = 4  (A→C→B→D)
পুরোনো entry (4, B), (6, D) বের হলে বাদ: d > dist[v]

টেবিল সাজান। চারটি কলাম — প্রতিটি vertex-এর জন্য একটি — আর দুটি সারি: বর্তমান দূরত্ব আর settled কি না। উৎস A-র দূরত্ব 0, বাকি সবাই ∞. heap-এ শুধু (0, A).
A settle, দুটি relax. A-কে বের করে তার edge relax: B = 4, C = 1. দুটিই অস্থায়ী — B-র 4 চূড়ান্ত নয়, পরে কমতে পারে। অনেকে এখানেই “d(B) = 4” লিখে ফেলেন।
সবচেয়ে ছোটটি — C (1) — settle. C থেকে B-তে 1 + 2 = 3, যা 4-এর চেয়ে ছোট — B হালনাগাদ। D পায় 1 + 5 = 6. heap-এ এখন B-র দুটি entry (3 আর পুরোনো 4).
B (3) settle. B→D দিয়ে 3 + 1 = 4 < 6, তাই D = 4. “d(D) = 6” অপশনটি ঠিক এই ধাপ বাদ দিলে আসে। পুরোনো (4, B) পরে বের হলেও বাদ যায়, কারণ B আগেই 3-এ settled.
D (4) settle — শেষ। settle ক্রম A, C, B, D আর d(D) = 4, পথ A→C→B→D. মোট কাজ: প্রতিটি edge একবার relax, প্রতিটি heap কাজ O(log V) — তাই O((V + E) log V).

৮ · মডিউল ৭ — অ্যালগরিদম ডিজাইন কৌশল (১৪টি প্রশ্ন)

divide and conquer-এর recurrence (Karatsuba), greedy কখন সঠিক আর কখন নয় (activity selection বনাম coin change), Huffman coding-এর bit গোনা, dynamic programming-এর দুই শর্ত আর ক্লাসিক সমস্যা (knapsack, LIS, edit distance, matrix chain, Held–Karp), backtracking আর branch and bound, আর string-এর prefix function আর suffix array. এখানে প্রায় প্রতিটি প্রশ্নই হাতে হিসাব — টেবিল আঁকুন।

যা ঝালিয়ে নেবেন

পর্ব ৪৯ · Divide and conquer — Karatsuba, Strassen, closest pair
পর্ব ৫০ · Greedy আর exchange argument — আগে শেষ হওয়া কাজ, greedy-র counterexample
পর্ব ৫১ · Huffman coding — সবচেয়ে ছোট দুটি জোড়া
পর্ব ৫২ · DP-র ভিত্তি — optimal substructure, overlapping subproblems
পর্ব ৫৩ · knapsack, coin change আর LIS আর পর্ব ৫৪ · LCS, edit distance আর matrix chain
পর্ব ৫৫ · bitmask, digit আর tree DP — Held–Karp-এর n² 2ⁿ
পর্ব ৫৬ · Backtracking আর পর্ব ৫৭ · Branch and bound — N-queens, bound দিয়ে ছাঁটা
পর্ব ৫৮ · Rabin-Karp, KMP আর Z আর পর্ব ৫৯ · Suffix array, LCP

(মাঝারি) Karatsuba গুণ দুটি n-অঙ্কের সংখ্যা গুণ করতে তিনটি n/2-অঙ্কের গুণ আর O(n) বাড়তি কাজ করে। মোট সময় কত?

Θ(n²)
Θ(n log n)
Θ(n^{log₂ 7})
Θ(n^{log₂ 3}) ≈ Θ(n^1.585)

(মাঝারি) কাজগুলো (শুরু, শেষ): (1, 3), (2, 5), (4, 6), (6, 8), (5, 9), (8, 10). একটির শুরু আগেরটির শেষের সমান বা পরে হলে দুটি একসাথে রাখা যায়। সর্বোচ্চ কয়টি কাজ রাখা যায়, আর কোন greedy নিয়ম সব ইনপুটে সর্বোত্তম ফল নিশ্চিত করে?

4টি; সবচেয়ে ছোট দৈর্ঘ্যের কাজ আগে বাছা
4টি; যেটি সবচেয়ে আগে শেষ হয় সেটি আগে বাছা
4টি; সবচেয়ে আগে শুরু হওয়া কাজ আগে বাছা
5টি; সবচেয়ে কম সংঘাতের কাজ আগে বাছা

(মাঝারি) মুদ্রা {1, 3, 4}, লক্ষ্য 6 টাকা। “সবসময় সবচেয়ে বড় মুদ্রা” greedy কয়টি মুদ্রা নেয়, আর সর্বোত্তম কয়টি?

greedy 2টি, সর্বোত্তম 2টি
greedy 3টি, সর্বোত্তম 3টি
greedy 3টি (4 + 1 + 1), সর্বোত্তম 2টি (3 + 3)
greedy 6টি, সর্বোত্তম 2টি

(মাঝারি) পাঁচটি অক্ষরের frequency: A = 10, B = 15, C = 30, D = 16, E = 29 (মোট 100). Huffman code দিয়ে encode করলে মোট কত bit লাগবে?

(সহজ) একটি সমস্যায় dynamic programming কার্যকর হওয়ার জন্য মূল দুটি বৈশিষ্ট্য কোনগুলো?

greedy choice property আর optimal substructure
উপ-সমস্যাগুলো পরস্পর-স্বাধীন আর কখনো পুনরাবৃত্ত নয়
optimal substructure আর overlapping subproblems
ইনপুট সাজানো থাকা আর n ছোট হওয়া

(মাঝারি) 0/1 knapsack: ধারণক্ষমতা 7, বস্তু (weight, value): (1, 1), (3, 4), (4, 5), (5, 7). সর্বোচ্চ value কত?

8
9.67
17
9

(মাঝারি) [3, 1, 8, 2, 5, 9, 4, 6]-এর longest (strictly) increasing subsequence-এর দৈর্ঘ্য কত?

(মাঝারি) “ALGORITHM” থেকে “LOGARITHM” বানাতে edit distance (Levenshtein: insert, delete, substitute — প্রতিটির খরচ 1) কত?

(কঠিন) তিনটি matrix A (10 × 30), B (30 × 5), C (5 × 60). ABC গুণ করতে সর্বনিম্ন কতটি scalar গুণ লাগে?

27000
1500
9000
4500

(মাঝারি) n টি শহরের traveling salesman সমস্যায় bitmask DP (Held–Karp)-এর সময় আর জায়গা কত?

সময় Θ(n² · 2ⁿ), জায়গা Θ(n · 2ⁿ)
সময় Θ(n!), জায়গা Θ(n)
সময় Θ(n³), জায়গা Θ(n²)
সময় Θ(2ⁿ), জায়গা Θ(2ⁿ)

(মাঝারি) 4 × 4 বোর্ডে চারটি queen এমনভাবে বসানো যে কেউ কাউকে আক্রমণ করে না — এমন কয়টি সমাধান আছে?

(মাঝারি) minimization-এর branch and bound-এ একটি node (আংশিক সমাধান) কখন ছেঁটে ফেলা (prune) যায়?

যখন node-টির lower bound এ পর্যন্ত পাওয়া সেরা পূর্ণ সমাধানের (incumbent) খরচের সমান বা বেশি
যখন node-টির lower bound incumbent-এর চেয়ে কম
যখন node-টি গাছের গভীরে থাকে
যখন node-টির আংশিক খরচ অন্য কোনো node-এর আংশিক খরচের চেয়ে বেশি

(মাঝারি) “ababaca” string-এর KMP prefix function (π) কী?

[0, 1, 2, 3, 4, 5, 6]
[0, 0, 1, 2, 3, 0, 1]
[0, 0, 1, 2, 3, 4, 5]
[0, 0, 1, 2, 1, 0, 1]

(মাঝারি) “banana” (0-based) string-এর suffix array কী?

[0, 1, 2, 3, 4, 5]
[5, 4, 3, 2, 1, 0]
[1, 3, 5, 0, 2, 4]
[5, 3, 1, 0, 4, 2]

৯ · মডিউল ৮ — উন্নত বিশ্লেষণ ও তত্ত্ব (১৩টি প্রশ্ন)

শেষ মডিউলের প্রশ্নে সংজ্ঞার সূক্ষ্মতাই আসল: amortized আর average-এর পার্থক্য (binary counter, দুই stack-এর queue), Las Vegas আর Monte Carlo, Miller–Rabin-এর ভুলের সম্ভাবনা, Euclid আর modular inverse, sieve-এর n log log n, cross product-এর চিহ্ন, convex hull-এর নিম্নসীমা, NP-complete আর reduction-এর দিক, আর vertex cover-এর approximation ratio. “reduction কোন দিকে” প্রশ্নে সবচেয়ে বেশি নম্বর হারান পরীক্ষার্থীরা।

যা ঝালিয়ে নেবেন

পর্ব ৬০ · Amortized analysis — aggregate, accounting, potential
পর্ব ৬১ · Randomized অ্যালগরিদম — Las Vegas, Monte Carlo, Miller–Rabin-এর ≤ 1/4
পর্ব ৬২ · Number theory — Euclid, inverse, sieve
পর্ব ৬৩ · Computational geometry — orientation test, convex hull
পর্ব ৬৪ · P বনাম NP আর পর্ব ৬৫ · NP-hard সমস্যা বাস্তবে — reduction-এর দিক
পর্ব ৬৬ · Approximation অ্যালগরিদম — 2-approx vertex cover, Christofides
পর্ব ৬৭ · ক্যাপস্টোন — brute force দিয়ে stress testing

(মাঝারি) 0 থেকে শুরু করা একটি k-bit binary counter-এ n বার increment (n < 2^k) — মোট কতটি bit উল্টায়?

Θ(n · k), কারণ প্রতিটি increment-এ k টি bit উল্টাতে পারে
Θ(n log n)
2n-এর কম — তাই প্রতি increment-এর amortized খরচ O(1), যদিও একটি increment-এ k টি bit-ও উল্টাতে পারে
ঠিক n, কারণ প্রতিবার একটি bit বদলায়

(কঠিন) দুটি stack (in, out) দিয়ে queue: enqueue-তে in-এ push; dequeue-তে out খালি হলে in-এর সব উপাদান pop করে out-এ push, তারপর out থেকে pop. ক্রম: enqueue 1, 2, 3; dequeue; enqueue 4; dequeue; dequeue. বের হওয়া মান আর in থেকে out-এ মোট স্থানান্তর কত?

1 2 3; মোট স্থানান্তর 6
1 2 3; মোট স্থানান্তর 3
3 2 1; মোট স্থানান্তর 3
1 2 4; মোট স্থানান্তর 4

(সহজ) randomized quick sort আর Miller–Rabin primality test — কোনটি কোন শ্রেণির randomized অ্যালগরিদম?

দুটিই Las Vegas
quick sort Monte Carlo, Miller–Rabin Las Vegas
দুটিই deterministic, এলোমেলোতা শুধু গতির জন্য
randomized quick sort Las Vegas (উত্তর সবসময় সঠিক, সময় এলোমেলো); Miller–Rabin Monte Carlo (সময় নির্দিষ্ট, ভুলের ছোট সম্ভাবনা)

(মাঝারি) একটি বিজোড় যৌগিক সংখ্যার ওপর স্বাধীনভাবে এলোমেলো base নিয়ে Miller–Rabin test 20 বার চালানো হলো। সবগুলোতে ভুলভাবে “সম্ভবত মৌলিক” আসার সম্ভাবনা সর্বোচ্চ কত?

4⁻²⁰ (প্রায় 10⁻¹²)
2⁻²⁰
1/20
0 — 20 রাউন্ডে ভুল অসম্ভব

(মাঝারি) Euclid-এর অ্যালগরিদমে gcd(252, 105) — উত্তর কত, আর কতটি mod (ভাগশেষ) ধাপ লাগে?

21; 2টি ধাপ
7; 3টি ধাপ
21; 3টি ধাপ
42; 2টি ধাপ

(মাঝারি) 3-এর modular inverse mod 11 কত, আর সাধারণভাবে a-এর inverse mod m কখন থাকে?

4; শুধু m মৌলিক হলে
4; যখন gcd(a, m) = 1
9; সবসময় থাকে
1/3 ≈ 0.333

(মাঝারি) n পর্যন্ত সব মৌলিক সংখ্যা বের করতে sieve of Eratosthenes-এর সময় কত?

O(n log log n)
O(n √n)
O(n log n)
O(n²)

(মাঝারি) A(0, 0), B(4, 0), C(2, 3). cross product (B − A) × (C − A) কত, আর A → B → C কোন দিকে ঘোরে?

−12; ডানে বাঁক (clockwise)
0; তিনটি বিন্দু এক রেখায়
12; ডানে বাঁক (clockwise)
12; বাঁয়ে বাঁক (counter-clockwise)

(মাঝারি) n টি বিন্দুর convex hull নিয়ে কোনটি সত্য?

gift wrapping (Jarvis march) সবসময় O(n log n)
convex hull O(n)-এ সবসময় করা যায়
Graham scan বা monotone chain O(n log n); তুলনা-ভিত্তিক মডেলে Ω(n log n)-এর চেয়ে ভালো সম্ভব নয়
convex hull NP-hard

(কঠিন) একটি নতুন সমস্যা X-কে NP-hard প্রমাণ করতে কোন reduction দেখাতে হয়?

একটি জানা NP-complete সমস্যা Y থেকে X-এ polynomial-time reduction (Y ≤_p X)
X থেকে একটি জানা NP-complete সমস্যা Y-তে reduction (X ≤_p Y)
X-এর জন্য একটি exponential-time অ্যালগরিদম লেখা
X-এর একটি polynomial-time verifier দেখানো

(মাঝারি) P বনাম NP সম্পর্কে কোনটি সত্য?

NP মানে “non-polynomial” — এসব সমস্যার কোনো polynomial সমাধান নেই
প্রমাণিত হয়েছে যে NP-complete সমস্যার জন্য exponential সময় লাগবেই
সব NP-hard সমস্যা NP-তে থাকে
কোনো একটি NP-complete সমস্যার polynomial-time সমাধান পাওয়া গেলে P = NP হবে

(মাঝারি) একটি maximal matching খুঁজে তার প্রতিটি edge-এর দুই প্রান্ত নিয়ে vertex cover বানালে approximation ratio কত?

1.5
ln n
2
1 — সবসময় সর্বোত্তম

(সহজ) একটি দ্রুত কিন্তু জটিল সমাধানের শুদ্ধতা যাচাইয়ের সবচেয়ে কার্যকর ব্যবহারিক পদ্ধতি কোনটি?

শুধু প্রশ্নের নমুনা ইনপুটে চালানো
সরল brute-force সমাধান লিখে অনেক এলোমেলো ছোট ইনপুটে দুটির উত্তর মেলানো (stress testing)
কোডটি AI-কে দেখিয়ে জিজ্ঞেস করা “ঠিক আছে কি না”
সবচেয়ে বড় ইনপুটে সময় মাপা

১০ · AI-এর যুগে — AI দিয়ে আরও MCQ বানান, কিন্তু উত্তর কোড চালিয়ে যাচাই করুন

এই পাতার ১০০টি প্রশ্ন শেষ হলে আরও অনুশীলন চাইবেন, আর AI চ্যাটবট মুহূর্তে শত শত MCQ বানিয়ে দিতে পারে। কিন্তু মনে রাখুন: DSA-র MCQ-তে AI প্রায়ই ভুল উত্তরকে “সঠিক” বলে চিহ্নিত করে, বা একই প্রশ্নে দুটি সঠিক অপশন রেখে দেয়। কারণটি পরিচিত — AI ধাপ গোনে না, প্রশ্নের চেহারা দেখে উত্তর অনুমান করে। “quick sort O(n log n)” বা “heap-এ search log n”-এর মতো আধা-সত্য ইন্টারনেটে এত বেশি ছড়ানো যে AI-ও সেগুলোকে সত্য ধরে। trace প্রশ্নে (pass 2-এর পর array, Dijkstra-র ক্রম) AI প্রায়ই এক ধাপ লাফিয়ে যায়, আর greedy-র প্রশ্নে প্রমাণ ছাড়াই “greedy সর্বোত্তম” বলে দেয়।

AI-এর প্রচলিত ভুল	উদাহরণ	কীভাবে ধরবেন
ভুল উত্তর-চাবি	trace প্রশ্নে এক ধাপ আগের বা পরের অবস্থাকে উত্তর বলা	ছোট প্রোগ্রাম লিখে চালান, বা খাতায় পুরো টেবিল করুন
case না বলা complexity	“quick sort O(n log n)” — worst case উল্লেখ নেই	প্রতিটি complexity-র পাশে case আর O/Θ লিখতে বলুন
দুটি সঠিক অপশন	অপশনে O(n²) আর O(n³) দুটিই — দুটিই সত্য ওপরের সীমা	প্রশ্নে “সবচেয়ে আঁটসাঁট” বা Θ চাওয়া হয়েছে কি না দেখুন
সংজ্ঞার রীতি গোলমাল	উচ্চতা node-এ গুনে উত্তর, প্রশ্নে edge-এ	প্রশ্নে রীতি স্পষ্ট লিখতে বলুন, নিজে মিলিয়ে নিন
প্রমাণহীন greedy	“সবচেয়ে বড় মুদ্রা আগে — সবসময় সর্বোত্তম”	ছোট counterexample খুঁজুন; DP-র সাথে brute force মেলান
বানানো উৎস	“অমুক পরীক্ষায় এসেছিল”	উৎস দেখাতে না পারলে দাবিটি বাদ দিন

নিচের প্রম্পটটি AI-কে প্রশ্ন বানাতে বলে, কিন্তু সাথে এমন তথ্যও চায়, যা দিয়ে আপনি উত্তর যাচাই করতে পারবেন। হিসাবের প্রতিটি প্রশ্নে চালানো যায় এমন কোড চাওয়াই এখানে আসল কৌশল:

আমি ডেটা স্ট্রাকচার ও অ্যালগরিদমের MCQ পরীক্ষার প্রস্তুতি নিচ্ছি (বিশ্ববিদ্যালয়, চাকরির লিখিত পরীক্ষা আর সফটওয়্যার ইঞ্জিনিয়ার ইন্টারভিউ)। বিষয়: [যেমন: heap আর priority queue] কঠিনতা: [সহজ / মাঝারি / কঠিন] ১০টি MCQ বানাও। প্রতিটির জন্য: ১. প্রশ্ন আর ঠিক ৪টি অপশন; শুধু একটি সঠিক। প্রশ্ন নিজে সম্পূর্ণ হবে — “উপরের কোড” ধরনের উল্লেখ থাকবে না। ২. রীতি স্পষ্ট লেখো: array 0 না 1-based, উচ্চতা edge না node-এ গোনা, complexity কোন case-এর। ৩. সঠিক উত্তর, আর প্রতিটি ভুল অপশন কোন ভুল ধারণা থেকে এসেছে — এক লাইনে। ৪. trace, output বা হিসাবের প্রশ্নে একটি ছোট C++ বা Python প্রোগ্রাম দাও, যা চালালে উত্তরটি ছাপে। ৫. প্রতিটি complexity Θ বা O দিয়ে, সঠিক চলক (n, V, E, k) আর case-সহ লেখো। ৬. কোনো প্রশ্নকে কোনো নির্দিষ্ট পরীক্ষার আসল প্রশ্ন বলে দাবি করবে না।

যাচাইয়ের চেকলিস্ট

trace আর output-এর প্রতিটি প্রশ্নের কোড নিজে চালিয়েছি; ফল AI-এর উত্তর-চাবির সাথে মিলেছে
চারটি অপশনের মধ্যে ঠিক একটি সত্য — দুটি সত্য ওপরের সীমা (যেমন O(n²) আর O(n³)) থাকা প্রশ্ন বাদ দিয়েছি বা ঠিক করেছি
প্রতিটি complexity-র case (best/worst/average/amortized) উল্লেখ আছে, আর এই কোর্সের সংশ্লিষ্ট পর্বের সাথে মিলিয়েছি
greedy-র দাবির জন্য হয় প্রমাণ (exchange argument) পেয়েছি, নয়তো ছোট ইনপুটে brute force দিয়ে মিলিয়েছি
উচ্চতা, index, B-tree-র order — প্রশ্নের রীতি আর উত্তরের রীতি একই
“অমুক পরীক্ষায় এসেছিল” ধরনের দাবি বাদ দিয়েছি

কেন এই উত্তর? — কৌশল আর যে ধারণাগুলোতে সবচেয়ে বেশি ভুল হয়

প্রথমটি এই প্রশ্নব্যাংক দিয়ে কীভাবে রিভিশন করবেন তা নিয়ে; বাকি পাঁচটি ধারণা এত বেশি ভুল বোঝা হয় যে আলাদা ব্যাখ্যা দরকার। আগে নিজে ভাবুন — তারপর খুলে উত্তর দেখুন।

প্র ০১এত প্রশ্ন একবারে পড়ে মনে থাকে না। এই প্রশ্নব্যাংক দিয়ে কীভাবে রিভিশন করলে সবচেয়ে বেশি কাজে লাগে?

প্রশ্নব্যাংকের সবচেয়ে বড় অপব্যবহার হলো একটানা পড়ে যাওয়া — প্রশ্ন দেখা, উত্তর চাপা, “ও আচ্ছা” বলে এগিয়ে যাওয়া। শেখার গবেষণায় বারবার দেখা গেছে, মনে রাখতে সবচেয়ে কার্যকর দুটি অভ্যাস হলো নিজে থেকে মনে করার চেষ্টা (active recall) আর বিরতি দিয়ে ফিরে আসা (spaced repetition). নিচের পদ্ধতিটি দুটিকেই কাজে লাগায়:

এক অংশ, পুরো মনোযোগ: একবারে একটি মডিউলের অংশ নিন। প্রতিটি প্রশ্নে চাপার আগে খাতায় নিজের উত্তর আর এক লাইনের কারণ লিখুন — “build-heap Θ(n), কারণ নিচের node-গুলোর sift-down ছোট”। কারণ লিখতে না পারলে আন্দাজটিকে ভুল হিসেবেই গুনুন, ঠিক হলেও।
ভুলের খাতা: প্রতিটি ভুলের জন্য একটি লাইন — কোন নিয়মটি গুলিয়েছিলাম (“upper_bound মানে প্রথম > x, ≥ নয়”)। প্রশ্ন নয়, নিয়মটি লিখুন; পরীক্ষায় একই নিয়ম অন্য সংখ্যায় আসবে।
পর্বে ফিরে যাওয়া: একটি অংশে তিনটির বেশি ভুল হলে সেই অংশের “যা ঝালিয়ে নেবেন” তালিকার পর্বগুলো আবার পড়ুন — বিশেষ করে সেখানকার ধাপে-ধাপে ডায়াগ্রাম।
trace নিজে বানান: প্রতিটি trace প্রশ্নের সংখ্যা একটু বদলে (array-র একটি মান, graph-এর একটি weight) নতুন প্রশ্ন বানান, খাতায় সমাধান করুন, তারপর ছোট প্রোগ্রাম লিখে মেলান। এটাই সবচেয়ে শক্তিশালী অনুশীলন, কারণ মুখস্থ উত্তর এখানে কাজ করে না।
ফিরে আসার সময়সূচি: ভুলের খাতা দেখে ১ দিন, ৩ দিন আর ৭ দিন পরে শুধু ভুল প্রশ্নগুলো আবার করুন। পাতার প্রশ্নের ক্রম একই থাকে, তাই উত্তরের অবস্থান মুখস্থ হয়ে যাওয়ার ঝুঁকি আছে — অপশন পড়ার আগেই নিজের উত্তর বলুন।
সময় ধরে পূর্ণ মহড়া: পরীক্ষার আগে সব অংশ থেকে মিশিয়ে ৩০টি প্রশ্ন ২৫ মিনিটে করুন। কোর্স হোমের মডিউল টেস্টও একই কাজে লাগে।

মূল উপলব্ধি: প্রশ্ন পড়া নয়, প্রশ্নের পেছনের নিয়ম মনে রাখাই লক্ষ্য — নিজে উত্তর আর কারণ লিখুন, ভুলের নিয়ম খাতায় তুলুন, আর বিরতি দিয়ে ফিরে আসুন।

প্র ০২“quick sort-এর time complexity কত?” — অপশনে O(n log n) আর O(n²) দুটোই থাকলে কোনটি বাছবেন? O, Ω, Θ আর best-worst-average কি একই কথা?

এটি DSA-র MCQ-তে সবচেয়ে বেশি গোলমাল তৈরি করা প্রশ্ন, কারণ এতে দুটি আলাদা মাত্রা মিশে যায়। প্রথম মাত্রা হলো কোন ইনপুট: best case (সবচেয়ে সুবিধাজনক ইনপুট), worst case (সবচেয়ে খারাপ), average case (কোনো সম্ভাবনা-বণ্টন ধরে গড়)। প্রত্যেকটি case থেকে একটি আলাদা ফাংশন আসে — quick sort-এর জন্য worst case T_w(n) = Θ(n²), average T_a(n) = Θ(n log n). দ্বিতীয় মাত্রা হলো কোন ধরনের সীমা: O ওপরের সীমা, Ω নিচের, Θ দুটোই। এই দুটি মাত্রা স্বাধীন — worst case-এরও O, Ω, Θ আছে, best case-এরও।

তাই “O মানে worst case আর Ω মানে best case” — এই জনপ্রিয় কথাটি ভুল। insertion sort-এর worst case Θ(n²), best case Θ(n); দুটিই Θ. আবার “insertion sort-এর running time O(n²)” সব ইনপুটের জন্য সত্য (কারণ worst case-ও n²-এর বেশি নয়), আর “Ω(n)” সব ইনপুটের জন্য সত্য। কিন্তু “insertion sort Θ(n²)” — case না বলে — মিথ্যা, কারণ সাজানো ইনপুটে এটি রৈখিক।

MCQ-তে বাস্তব নিয়ম: প্রশ্ন case না বললে worst case ধরুন, আর সবচেয়ে আঁটসাঁট সঠিক সীমাটি বাছুন। ফলে “quick sort-এর time complexity” প্রশ্নে O(n²) সঠিক, আর O(n log n) worst case-এর জন্য মিথ্যা। তবে প্রশ্নে “average” বা “expected” লেখা থাকলে n log n. randomized quick sort-এর ক্ষেত্রে কথাটি আরও সূক্ষ্ম: worst case তখনো n², কিন্তু যেকোনো ইনপুটে expected সময় Θ(n log n) — এলোমেলোতা আসে অ্যালগরিদমের ভেতর থেকে, ইনপুট থেকে নয়। Tony Hoare ১৯৬১ সালে quick sort প্রকাশ করেন, আর এই worst case-ই পরে introsort-এর জন্ম দেয় (David Musser, ১৯৯৭) — গভীরতা বেশি হলে heap sort-এ চলে যাওয়া, যাতে worst case-ও n log n থাকে।

আরেকটি ফাঁদ: অপশনে O(n²) আর O(n³) দুটোই থাকলে দুটিই সত্য ওপরের সীমা। ভালো প্রশ্নে তখন Θ চাওয়া হয়, বা “সবচেয়ে আঁটসাঁট” লেখা থাকে। না থাকলে সবচেয়ে আঁটসাঁটটি বাছুন — প্রশ্নকর্তা প্রায় সবসময় সেটিই বোঝান।

মূল উপলব্ধি: complexity বলার আগে দুটি প্রশ্নের উত্তর দিন — কোন case, আর কোন সীমা। “worst case Θ(n²), average Θ(n log n)” একটি সম্পূর্ণ উত্তর; “O(n log n)” একা একটি অসম্পূর্ণ দাবি।

প্র ০৩heap আর BST দুটোই tree, দুটোতেই log n — তাহলে heap-এ search কেন Θ(n)? কোন কাজে কোনটি বাছবেন?

দুটির পার্থক্য তাদের ক্রমের নিয়মে। BST-তে নিয়মটি অনুভূমিক: বাঁ subtree-র সব key ছোট, ডানের সব বড়। তাই যেকোনো key খুঁজতে প্রতিটি node-এ একটি তুলনাই বলে দেয় কোন দিকে নামবেন — পথের দৈর্ঘ্য উচ্চতার সমান। heap-এর নিয়মটি উল্লম্ব: parent সন্তানের চেয়ে বড় (max-heap). বাঁ আর ডান সন্তানের মধ্যে কোনো সম্পর্ক নেই। ফলে root-এ সবচেয়ে বড় key নিশ্চিত, কিন্তু 5 কোথায় আছে বলার উপায় নেই — বাঁয়ে বা ডানে, যেকোনো জায়গায়। worst case-এ সব node দেখতে হয়: Θ(n).

heap-এর log n আসে শুধু দুটি কাজে: insert (শেষে বসিয়ে sift-up) আর extract-max (root সরিয়ে sift-down). এই দুটি কাজ পথ ধরে চলে, আর heap সবসময় complete binary tree বলে উচ্চতা ⌊log₂ n⌋। BST-র log n-এর নিশ্চয়তা আরও দুর্বল: সাধারণ BST-তে সাজানো ক্রমে insert করলে tree শিকল হয়ে যায়, উচ্চতা n − 1. log n নিশ্চিত শুধু balanced BST-তে — AVL (Adelson-Velsky আর Landis, ১৯৬২) বা red-black tree-তে।

তাহলে কোনটি কখন? সবচেয়ে বড় বা ছোটটি বারবার লাগলে (Dijkstra, Huffman, job scheduling, top-k) — heap: সরল, array-তে রাখা যায়, cache-বান্ধব, আর build Θ(n). যেকোনো key খোঁজা, সাজানো ক্রমে ঘোরা, “x-এর পরের বড়টি কে” (successor), রেঞ্জের সব key — balanced BST (C++-এর std::map/std::set). শুধু “আছে কি নেই” আর ক্রম লাগে না — hash table, গড়ে O(1). heap-এ “যেকোনো key-র মান কমানো” (decrease-key) লাগলে আলাদা index-map রাখতে হয় — সেটি indexed priority queue.

J. W. J. Williams ১৯৬৪ সালে heapsort-এর সাথে binary heap প্রকাশ করেন, আর একই বছর Robert Floyd Θ(n) build-heap দেখান — দুটিই এখনো সব পাঠ্যবইয়ে।

মূল উপলব্ধি: log n আসে “প্রতিটি ধাপে কোন দিকে যাব জানি” থেকে। heap এটি জানে শুধু root-এর জন্য, BST জানে প্রতিটি key-র জন্য — তবে কেবল ভারসাম্য থাকলে।

প্র ০৪BFS, 0-1 BFS, Dijkstra, Bellman–Ford — shortest path-এর প্রশ্নে কোনটি কখন? Dijkstra ঋণাত্মক edge-এ ঠিক কোথায় ভেঙে পড়ে?

চারটিই একই প্রশ্নের উত্তর দেয় — একটি উৎস থেকে সব vertex-এর সবচেয়ে ছোট দূরত্ব — কিন্তু প্রত্যেকে graph-এর ওপর আলাদা শর্ত চায়, আর শর্ত যত দুর্বল, অ্যালগরিদম তত ধীর। সব edge-এর weight সমান (বা weight নেই) হলে BFS, Θ(V + E): স্তর ধরে এগোনো মানে দূরত্বের ক্রমে এগোনো। weight শুধু 0 বা 1 হলে 0-1 BFS, তাও Θ(V + E): deque-এর সামনে 0-edge, পেছনে 1-edge, ফলে deque-এ দূরত্বগুলো সবসময় সাজানো থাকে। weight অঋণাত্মক যেকোনো সংখ্যা হলে Dijkstra, binary heap-এ O((V + E) log V). ঋণাত্মক weight থাকলে Bellman–Ford, Θ(VE) — আর সাথে negative cycle ধরাও যায়।

Dijkstra-র শুদ্ধতার যুক্তিটি দেখলেই বোঝা যায় ঋণাত্মক edge কোথায় আঘাত করে। heap থেকে u বের করার মুহূর্তে আমরা দাবি করি dist[u] চূড়ান্ত। যুক্তি: অন্য কোনো পথ থাকলে সেটি কোনো অস্থায়ী vertex x দিয়ে বেরোবে, আর dist[x] ≥ dist[u]; তারপর বাকি পথের weight ≥ 0, তাই সেই পথ dist[u]-এর চেয়ে ছোট হতে পারে না। “বাকি পথের weight ≥ 0” — এই একটি ধাপই ঋণাত্মক edge ভাঙে। A→B (2), A→C (3), C→B (−2), B→D (1)-এ B 2-এ settle হয়ে D-কে 3 দেয়; পরে A→C→B = 1 পাওয়া গেলেও B আগেই চূড়ান্ত, তাই D আর হালনাগাদ হয় না — উত্তর 3, অথচ আসল দূরত্ব 2. negative cycle না থাকলেও উত্তর ভুল।

Edsger Dijkstra অ্যালগরিদমটি ১৯৫৬ সালে ভাবেন আর ১৯৫৯ সালে প্রকাশ করেন; Richard Bellman (১৯৫৮) আর Lester Ford (১৯৫৬) আলাদাভাবে ঋণাত্মক weight সামলানোর পদ্ধতি দেন। সব জোড়ার দূরত্ব লাগলে আর V ছোট হলে Floyd–Warshall Θ(V³) সবচেয়ে সরল; V বড় আর sparse graph হলে প্রতিটি উৎস থেকে Dijkstra (ঋণাত্মক edge থাকলে Johnson-এর reweighting দিয়ে)।

MCQ-তে একটি দ্রুত নিয়ম: প্রশ্ন থেকে weight-এর শর্ত বের করুন, তারপর যে সবচেয়ে দ্রুত অ্যালগরিদম সেই শর্তে সঠিক, সেটিই উত্তর। “weight-হীন graph-এ Dijkstra” ভুল নয়, কিন্তু “সবচেয়ে উপযুক্ত” নয়।

মূল উপলব্ধি: শর্ত যত শক্ত, অ্যালগরিদম তত দ্রুত — সমান weight-এ BFS, 0/1-এ deque, অঋণাত্মকে Dijkstra, ঋণাত্মকে Bellman–Ford. Dijkstra-র পুরো যুক্তি দাঁড়িয়ে “পথ লম্বা হলে খরচ কমে না” — এই একটি অনুমানের ওপর।

প্র ০৫stable sort নিয়ে এত প্রশ্ন কেন? সমান key-র ক্রম বজায় রাখা বাস্তবে কোথায় লাগে?

একটি sort stable, যদি সমান key-র দুটি উপাদান sort-এর আগে যে ক্রমে ছিল, পরেও সেই ক্রমে থাকে। শুধু সংখ্যা সাজালে এর কোনো মানে নেই — দুটি 5 একই রকম। কিন্তু বাস্তবে আমরা সাজাই রেকর্ড: ছাত্রের নাম আর নম্বর, লেনদেনের সময় আর টাকা। তখন “একই নম্বরের ছাত্ররা আগের মতো নামের ক্রমে থাকবে কি না” একটি সত্যিকারের প্রশ্ন।

সবচেয়ে বড় ব্যবহার একাধিক key-তে সাজানো। ধরুন bKash লেনদেনের তালিকা তারিখ অনুযায়ী, আর একই তারিখের মধ্যে সময় অনুযায়ী চাই। stable sort থাকলে দুই ধাপে করা যায়: আগে সময় অনুযায়ী, তারপর তারিখ অনুযায়ী — দ্বিতীয় sort একই তারিখের লেনদেনগুলোর সময়-ক্রম ভাঙে না। spreadsheet-এ এক কলামে sort করে তারপর আরেক কলামে sort করলে যে ফল আশা করেন, সেটি stable sort-এর ওপরই নির্ভর করে।

radix sort এই ধারণার সবচেয়ে সুন্দর উদাহরণ। LSD radix sort প্রথমে শেষ অঙ্কে, তারপর তার আগের অঙ্কে… সাজায়। প্রতিটি ধাপের sort stable না হলে আগের ধাপের কাজ নষ্ট হয়ে যেত। Herman Hollerith-এর punched card-এর যন্ত্র (১৮৯০ সালের মার্কিন আদমশুমারি) থেকে শুরু করে পরের দশকগুলোর card sorter ঠিক এভাবে এক কলাম করে কার্ড সাজাত।

কোনগুলো stable? merge sort (সমান হলে বাঁয়েরটি আগে নিলে), insertion sort, bubble sort, counting sort (পেছন থেকে বসালে), আর Python-এর Timsort (Tim Peters, ২০০২) — সবই stable. quick sort, heap sort আর swap-ভিত্তিক selection sort নয়, কারণ তারা দূরের উপাদান লাফিয়ে জায়গা বদলায়। C++-এ std::sort stable নিশ্চিত করে না; লাগলে std::stable_sort. যেকোনো unstable sort-কে stable বানানো যায় key-র সাথে মূল index জুড়ে দিয়ে — খরচ বাড়তি জায়গা।

মূল উপলব্ধি: stability শুধু তত্ত্বের খুঁটিনাটি নয় — একাধিক key-তে সাজানো আর radix sort এর ওপর দাঁড়িয়ে। MCQ-তে “কোনটি stable” প্রশ্নে লাফিয়ে swap করে এমন অ্যালগরিদম (quick, heap, selection) আগে বাদ দিন।

প্র ০৬“O(1)” তিন রকম হতে পারে — worst case, amortized আর expected. vector-এর push_back আর hash table-এর insert দুটিই “O(1)” — তফাত কোথায়?

তিনটি “O(1)” তিনটি আলাদা প্রতিশ্রুতি। worst case O(1) মানে প্রতিটি কাজ, প্রতিবার, ধ্রুবক সময়ে — যেমন array-র A[i] পড়া বা stack-এর push (আগে থেকে জায়গা থাকলে)। amortized O(1) মানে কোনো একটি কাজ ব্যয়বহুল হতে পারে, কিন্তু যেকোনো m টি কাজের ক্রমের মোট খরচ O(m) — এটি একটি নিশ্চিত গ্যারান্টি, এতে কোনো সম্ভাবনা নেই। expected (বা average) O(1) মানে খরচ একটি random variable, আর তার প্রত্যাশিত মান ধ্রুবক — কোনো দুর্ভাগা মুহূর্তে বা খারাপ ইনপুটে বেশি হতে পারে।

vector-এর push_back হলো amortized: capacity দ্বিগুণ করার মুহূর্তে একটি push_back পুরো array কপি করে, Θ(n). কিন্তু n টি push_back-এ কপির মোট খরচ 1 + 2 + 4 + … < 2n — তাই গড়ে প্রতিটি O(1), যেকোনো ইনপুটে, নিশ্চিতভাবে। accounting method-এ ভাবলে: প্রতিটি push_back ৩ একক “টাকা” দেয় — একটি নিজের লেখায়, দুটি জমা থাকে ভবিষ্যতের কপির জন্য। binary counter-এর increment আর দুই stack-এর queue একই শ্রেণির উদাহরণ। Robert Tarjan ১৯৮৫ সালে “Amortized Computational Complexity” প্রবন্ধে এই বিশ্লেষণকে আনুষ্ঠানিক রূপ দেন।

hash table-এর insert হলো expected: ভালো hash function আর সীমিত load factor ধরে গড়ে O(1), কিন্তু কোনো আক্রমণকারী যদি জানেন আপনার hash function, তিনি এমন key পাঠাতে পারেন যা সবই একই bucket-এ পড়ে — তখন প্রতিটি কাজ Θ(n). কনটেস্টে anti-hash টেস্ট আর ওয়েব সার্ভারে hash flooding আক্রমণ ঠিক এটিই করে; তাই অনেক ভাষা এলোমেলো seed-সহ hash (যেমন SipHash) ব্যবহার করে। আর hash table-এর resize অংশটি আবার amortized — দুটি ধারণা একসাথেও থাকে।

MCQ-তে “প্রতিটি push_back worst case-এও O(1)” মিথ্যা, “n টি push_back মোট Θ(n)” সত্য, “unordered_map-এর find worst case O(1)” মিথ্যা।

মূল উপলব্ধি: amortized হলো পুরো ক্রমের নিশ্চিত হিসাব, expected হলো সম্ভাবনার হিসাব। real-time সিস্টেমে (যেখানে প্রতিটি কাজের সময়সীমা আছে) দুটির কোনোটিই যথেষ্ট নয় — সেখানে worst case-ই লাগে।

শেষ ধাপ — ক্রম সাজান আর স্কোর দেখুন

উপরের সব MCQ শেষ করলে নিচে আপনার মোট স্কোর দেখাবে — প্রথম চেষ্টায় কয়টি ঠিক হয়েছে।

ক্রমT(n) = aT(n/b) + f(n) ধরনের recurrence-এ Master theorem প্রয়োগের ধাপগুলো আগে থেকে পরে সাজান (▲▼ চেপে সরান)

a, b আর f(n) চিহ্নিত করা
critical অংশ n^{log_b a} হিসাব করা
f(n)-কে তার সাথে তুলনা — polynomially ছোট, সমান, না বড়
case 3 হলে regularity শর্ত a · f(n/b) ≤ c · f(n) যাচাই
কোনো case না খাটলে recursion tree-তে ফিরে যাওয়া, নইলে উত্তর লেখা

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:

মনে রাখুন

বাদ দিন, তারপর যাচাই করুন: প্রতিটি অপশনের পেছনের দাবি একটি নিয়ম বা ছোট counterexample দিয়ে কাটুন; শেষ অপশনটির পক্ষেও যুক্তি খুঁজুন।
complexity-তে দুই প্রশ্ন: কোন case (best/worst/average/amortized), আর কোন সীমা (O/Ω/Θ)। case না বললে worst case আর সবচেয়ে আঁটসাঁট সীমা।
ছয় ফাঁদ: log-এর ভিত্তি গুণক মাত্র; O ≠ Θ; quick, heap, selection unstable; quick sort আর hash table-এর worst case আলাদা; heap-এ search Θ(n); BFS শুধু weight-হীন, Dijkstra শুধু অঋণাত্মক।
trace-এ টেবিল: প্রতিটি ধাপের পুরো অবস্থা লিখুন — “এক ধাপ আগের” আর “এক ধাপ পরের” অপশন তখন চোখে পড়ে; রীতি (0/1-based, উচ্চতা) আগে মেলান।
AI-এর MCQ যাচাই: প্রতিটি হিসাবের উত্তর কোড চালিয়ে বা brute force দিয়ে মেলান; দুটি সঠিক অপশন বা case-হীন complexity থাকলে প্রশ্নটি ঠিক করুন।

পরের পর্বে: MCQ-তে চারটি অপশন থাকে; লিখিত পরীক্ষা আর ভাইভায় থাকে না। পর্ব ৭০-এ প্রমাণসহ লিখিত প্রশ্ন — loop invariant, exchange argument, cut property, reduction — আর মৌখিক পরীক্ষায় কীভাবে গুছিয়ে উত্তর দেবেন।

MCQ প্রশ্নব্যাংক — ডেটা স্ট্রাকচার আর অ্যালগরিদম

এই পর্বে যা করবেন

১ · DSA-র MCQ কীভাবে সামলাবেন — প্রশ্নের ধরন, বাদ দেওয়ার কৌশল আর প্রচলিত ফাঁদ

প্রশ্নের আট ছাঁচ

কৌশল ১ · বাদ দেওয়ার পদ্ধতি

কৌশল ২ · complexity-র প্রশ্নে আগে “কোন case, কোন মডেল” ঠিক করুন

কৌশল ৩ · trace প্রশ্নে খাতায় টেবিল, মাথায় নয়

কৌশল ৪ · সময় ভাগ আর ভুলে নম্বর কাটার হিসাব

ছয়টি বড় ফাঁদ — আর আরও কয়েকটি

২ · মডিউল ১ — শুরু ও বিশ্লেষণের ভিত্তি (১২টি প্রশ্ন)

কঠিন প্রশ্নের ভেতরে — Master theorem যেখানে থেমে যায়

৩ · মডিউল ২ — লিনিয়ার ডেটা স্ট্রাকচার (১২টি প্রশ্ন)

৪ · মডিউল ৩ — সার্চিং ও সর্টিং (১২টি প্রশ্ন)

৫ · মডিউল ৪ — ট্রি, হ্যাশ ও DSU (১২টি প্রশ্ন)

৬ · মডিউল ৫ — রেঞ্জ কোয়েরি ও উন্নত স্ট্রাকচার (১১টি প্রশ্ন)

৭ · মডিউল ৬ — গ্রাফ অ্যালগরিদম (১৪টি প্রশ্ন)

trace প্রশ্নের খাতা — Dijkstra-র settle ক্রম

৮ · মডিউল ৭ — অ্যালগরিদম ডিজাইন কৌশল (১৪টি প্রশ্ন)

৯ · মডিউল ৮ — উন্নত বিশ্লেষণ ও তত্ত্ব (১৩টি প্রশ্ন)

১০ · AI-এর যুগে — AI দিয়ে আরও MCQ বানান, কিন্তু উত্তর কোড চালিয়ে যাচাই করুন

যাচাইয়ের চেকলিস্ট

কেন এই উত্তর? — কৌশল আর যে ধারণাগুলোতে সবচেয়ে বেশি ভুল হয়

শেষ ধাপ — ক্রম সাজান আর স্কোর দেখুন

শব্দকোষ

মনে রাখুন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ