কনটেন্টে যান

একাধিক ধারণা মিলিয়ে problem সমাধান

অধ্যায়ের সূচি · মূল প্রশ্ন ও সব নোট · কঠিন pattern

এই অধ্যায়ে নতুন data structure মুখস্থ করার চেয়ে পরিচিত structure কেন একসঙ্গে লাগছে তা ব্যাখ্যা করবেন। একটি component যে প্রশ্নের উত্তর দ্রুত দিতে পারে না, অন্য component সেটি সামলায়।

পড়া ও অনুশীলনের ক্রম

  1. Master tracker থেকে পরিচিত একটি medium problem নিন। Source হলো মূল প্রশ্ন, Note file হলো এই সাইটের সমাধান।
  2. নিজের ভাষায় input, output, constraints এবং একটি ছোট উদাহরণ লিখুন।
  3. সরল সমাধানের কোন operation বারবার ধীর হচ্ছে তা চিহ্নিত করুন।
  4. সেই operation-এর জন্য structure বাছুন; প্রতিটির দায়িত্ব এক বাক্যে লিখুন।
  5. Code-এর আগে পূর্ণ ছোট trace, পরে edge case এবং complexity লিখুন।

Google-style, Amazon-style ও Microsoft-style পৃষ্ঠাগুলো আলাদা practice emphasis হিসেবে পড়ুন। কোনো company-তে নির্দিষ্ট প্রশ্ন আসার নিশ্চয়তা হিসেবে নয়।

একটি প্রোগ্রাম: LRU cache

Capacity 2। Key দিয়ে দ্রুত value পেতে hash map লাগে। শেষ কবে ব্যবহার হয়েছে সেই order বদলাতে এবং সবচেয়ে পুরোনো entry বাদ দিতে doubly linked list লাগে। শুধু map এই order update-এর কাজ করে না; শুধু list দিয়ে key খুঁজতে scan লাগে।

flowchart LR
  head["HEAD"] <--> a["key 2 / value 20"]
  a <--> b["key 1 / value 10"]
  b <--> tail["TAIL"]
  map2["map[2]"] --> a
  map1["map[1]"] --> b

HEAD-এর কাছে সবচেয়ে সম্প্রতি ব্যবহৃত entry। HEAD ও TAIL হলো dummy node; capacity-তে গোনা হয় না।

Operation Recent → old Hash map Return
শুরু খালি {} —
put(1,10) [1] {1: node1} —
put(2,20) [2,1] {1: node1, 2: node2} —
get(1) [1,2] একই দুই key 10
put(3,30) [3,1] {1: node1, 3: node3} 2 বাদ
get(2) [3,1] অপরিবর্তিত -1
put(1,11) [1,3] একই key, value বদলেছে —

প্রতিটি operation-এ গড় O(1) hash lookup এবং O(1) pointer update। Map ও list-এ একই জীবিত key থাকতে হবে—eviction-এর সময় দুই জায়গা থেকেই মুছতে হবে। সম্পূর্ণ LRU নোট ও মূল প্রশ্ন।

আরও চারটি সমন্বয়

Problem প্রথম ধারণার কাজ দ্বিতীয় ধারণার কাজ স্থানীয় নোট
Word Ladder BFS কম transformation খোঁজে Wildcard bucket neighbor খোঁজে নোট
Merge k Lists প্রতিটি list-এর head পরের candidate Heap সব head-এর minimum দেয় নোট
Count Smaller After Self Compression value-কে rank দেয় Fenwick ছোট rank-এর count দেয় নোট
Longest Increasing Path বড় neighbor-এর দিকে edge; cycle নেই Memo প্রতিটি cell-এর উত্তর একবার হিসাব করে নোট

৪৫ মিনিটের একটি অনুশীলন

সময় লিখিত ফল
0–5 মিনিট Input/output, শর্ত, একটি উদাহরণ
5–12 মিনিট Brute force এবং কোন operation ধীর
12–20 মিনিট State/structure, invariant, পুরো ছোট trace
20–35 মিনিট Implementation
35–42 মিনিট Empty/minimum, duplicate, boundary এবং সাধারণ case
42–45 মিনিট Time/space এবং কোন constraint বদলালে পদ্ধতি বদলাবে

সমাধান দেখে বুঝতে পারা আর নিজে লিখতে পারা আলাদা অর্জন। নোট পড়ার পরে বন্ধ করে ছোট input-এ আবার trace করুন; tracker-এর ব্যক্তিগত status তখনই নিজের অগ্রগতি অনুযায়ী বদলান।