🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

🎯 धडा 12 — योग्य structure निवडणे: प्रश्न ठरवतो

📍 तुम्ही इथे आहात: 12 पैकी धडा 12 · 🎓 शेवटचा

📦 या ब्रँचमध्ये काय आहे

धडे 01–12 — पूर्ण कोर्स. निर्णय तक्ता, complexity cheat sheet, कोणत्याही problem साठी सात पायऱ्यांची पद्धत, आणि कळस-प्रकल्प (capstone).

dsa/demo.py — choose: निर्णय तक्ता
dsa/test_dsa.py — सगळ्यावरचा smoke test

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

आता तुमच्याकडे अकरा जागा आणि चाली आहेत. शेवटचे कौशल्य म्हणजे प्रश्न ऐकून तो कशाची मागणी करतो ते ओळखणे. "जागेनुसार?" — lockers. "नावाने?" — कप्पे. "सर्वात अलीकडचा आधी?" — ट्रेची चळत. "आधी आलेल्याला आधी?" — जेवणाची रांग. "नेहमी सर्वात लहान?" — व्यासपीठ. "Sorted, आणि सतत बदलत राहणारे?" — कॅटलॉगचा खण. "खोल्या आणि कॉरिडॉर?" — नकाशा. "तोच छोटा प्रश्न पुन्हा पुन्हा?" — फळा. प्रश्न मोठ्याने बोला; structure स्वतः उत्तर देतो.

🗺️ आकृती

flowchart TD
  Q{"what does the question ask for?"}
  Q -->|"the i-th thing"| A["array"] ; Q -->|"by name"| H["hash map / set"]
  Q -->|"most recent first"| S["stack"] ; Q -->|"first come first served"| U["queue"]
  Q -->|"smallest / biggest, repeatedly"| P["heap"] ; Q -->|"sorted while changing"| T["balanced tree"]
  Q -->|"rooms and corridors"| G["graph + BFS / DFS / Dijkstra"] ; Q -->|"overlapping sub-problems"| D["DP"]

❓ काय

Cheat sheet

Structure / चाल	खर्च	केव्हा वापरायचा
list index / append	O(1)	जागा (position), batches
list insert front / pop(0)	O(n)	loop मध्ये कधीच नाही — deque वापरा
dict / set	सरासरी O(1)	नावाने, मोजणी, dedupe, caching
deque	दोन्ही टोकांना O(1)	queues, windows
heapq push/pop	O(log n)	पुढचा सर्वात लहान, top-k, Dijkstra
sorted()	O(n log n)	एकदा, मग bisect किंवा sweep
bisect	O(log n)	sorted आणि न बदलणारे
balanced tree / B-tree	O(log n)	sorted आणि बदलणारे, ranges
BFS / DFS	O(V + E)	hops, reachability, क्रम
Dijkstra	O(E log V)	weighted सर्वात लहान path
DP	poly	overlapping sub-problems

पद्धत (मुलाखती आणि design reviews दोन्हींसाठी): 1 प्रश्न उदाहरणासह पुन्हा मांडा · 2 brute force आणि त्याचा O सांगा · 3 pattern ओळखा (two pointers? नावाने? सर्वात लहान path?) · 4 structure निवडा · 5 code लिहा · 6 टोकाच्या cases test करा (रिकामे, एक, duplicates, प्रचंड) · 7 वेळ आणि space सांगा, आणि तुम्ही निवडलेला trade-off.

🤔 का

heap implement करायचे कोणालाच पैसे मिळत नाहीत; nested loop एकच loop असायला हवा होता हे लक्षात घेण्याचे मात्र सगळ्यांना मिळतात. तक्ता आणि पद्धत एका धूसर "जलद करा" चे पाच मिनिटांच्या निर्णयात रूपांतर करतात.

🔧 कसे (या repo मध्ये)

demo.py choose निर्णय तक्ता print करतो; repo मधला प्रत्येक structure आणि कृती तिच्या docstring ने दिलेले वचन पाळते याचा पुरावा म्हणजे test_dsa.py.

🧪 करून पाहा

python3 dsa/demo.py choose
python3 dsa/test_dsa.py
python3 - <<'EOF'
# capstone: the timetable clash finder — which pairs of meetings overlap?
import random, time
random.seed(9); M = [(s, s + random.randint(1, 3)) for s in random.choices(range(0, 200), k=500)]
t = time.perf_counter(); n2 = sum(1 for i in range(len(M)) for j in range(i + 1, len(M)) if M[i][0] < M[j][1] and M[j][0] < M[i][1]); t2 = time.perf_counter() - t
t = time.perf_counter(); ev = sorted([(s, 1, i) for i, (s, e) in enumerate(M)] + [(e, 0, i) for i, (s, e) in enumerate(M)]); open_ = set(); sw = 0
for _, kind, i in ev:                                      # sort + sweep: ends (0) before starts (1) at the same time
    if kind: sw += len(open_); open_.add(i)
    else: open_.discard(i)
t1 = time.perf_counter() - t
print(f"O(n²): {n2} clashes in {t2*1000:.1f} ms · sort+sweep O(n log n): {sw} clashes in {t1*1000:.1f} ms")
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

निर्णय तक्ता; 12 checks सह tests कडून OK; दोन्ही clash counts समान, आणि 500 meetings ला sweep अनेक पटींनी जलद — आणि k वाढवला तर हे अंतर वाढत जाते.

🏁 तुम्ही आत्ताच काय सिद्ध केले

नवीन प्रश्न दिला तर तुम्ही brute force, pattern, structure आणि खर्च सांगू शकता — आणि तुम्ही capstone दोन्ही प्रकारे बनवला आणि फरक मोजला.

⚠️ नेहमीच्या चुका

brute force लिहिण्याआधीच हुशार structure कडे धाव घेणे (त्याच्याशी तुलना करून test करायला तो लागतो).
चुकीचा भाग optimise करणे: आधी मोजा (धडा 01).
टोकाचे cases विसरणे: रिकामा input, एक item, सगळे समान, आधीच sorted, प्रचंड.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: हा तक्ता म्हणजेच performance review ची checklist: प्रत्येक hot path ला ती कोणत्या row वर आहे आणि का, हे सांगता आले पाहिजे.

🏆 कळस-प्रकल्प (Capstone)

clash finder वाढवा: कोणत्या meetings clash होतात ते सांगा (फक्त किती नाही), अनेक खोल्यांमधल्या meetings हाताळा (sweeps चा dict), आणि रिकाम्या timetable, एकच meeting, आणि दोन सारख्या meetings साठी test लिहा. मग एका परिच्छेदात समजावा की sort-and-sweep O(n log n) का आहे.

🎓 कोर्स पूर्ण झाला

अभ्यास योजना बाराही धड्यांवर खूण करते; quiz त्यांची तपासणी करते; Database school धडा 09 चे trees disk वर नेते, आणि School portal वर प्रमाणपत्र आहे.

🎯 Lesson 12 — Choosing the right structure: the question decides

📍 You are here: Lesson 12 of 12 · 🎓 The last one

📦 What's in this branch

Lessons 01–12 — the whole course. The decision table, the complexity cheat sheet, a seven-step method for any problem, and the capstone.

dsa/demo.py — choose: the decision table
dsa/test_dsa.py — the smoke test over everything

🧒 Explain like I'm 5

You now own eleven places and walks. The last skill is hearing a question and knowing which one it is asking for. "By position?" — lockers. "By name?" — pigeonholes. "Most recent first?" — the tray pile. "First come first served?" — the lunch line. "Always the smallest?" — the podium. "Sorted, and it keeps changing?" — the catalogue drawer. "Rooms and corridors?" — the map. "The same smaller question again and again?" — the board. Say the question out loud; the structure answers.

🗺️ Diagram

flowchart TD
  Q{"what does the question ask for?"}
  Q -->|"the i-th thing"| A["array"] ; Q -->|"by name"| H["hash map / set"]
  Q -->|"most recent first"| S["stack"] ; Q -->|"first come first served"| U["queue"]
  Q -->|"smallest / biggest, repeatedly"| P["heap"] ; Q -->|"sorted while changing"| T["balanced tree"]
  Q -->|"rooms and corridors"| G["graph + BFS / DFS / Dijkstra"] ; Q -->|"overlapping sub-problems"| D["DP"]

❓ What

The cheat sheet

Structure / walk	Cost	Reach for it when
list index / append	O(1)	position, batches
list insert front / pop(0)	O(n)	never in a loop — use deque
dict / set	O(1) avg	by name, counting, dedupe, caching
deque	O(1) both ends	queues, windows
heapq push/pop	O(log n)	the smallest next, top-k, Dijkstra
sorted()	O(n log n)	once, then bisect or sweep
bisect	O(log n)	sorted and static
balanced tree / B-tree	O(log n)	sorted and changing, ranges
BFS / DFS	O(V + E)	hops, reachability, order
Dijkstra	O(E log V)	weighted shortest path
DP	poly	overlapping sub-problems

The method (interviews and design reviews alike): 1 restate the question with an example · 2 give the brute force and its O · 3 name the pattern (two pointers? by name? shortest path?) · 4 pick the structure · 5 code it · 6 test the edges (empty, one, duplicates, huge) · 7 state time and space, and the trade-off you chose.

🤔 Why

Nobody is paid to implement a heap; everybody is paid to notice that the nested loop should have been one. The table and the method turn a vague "make it faster" into a five-minute decision.

🔧 How (in this repo)

demo.py choose prints the decision table; test_dsa.py is the proof that every structure and recipe in the repo does what its docstring promises.

🧪 Try it

python3 dsa/demo.py choose
python3 dsa/test_dsa.py
python3 - <<'EOF'
# capstone: the timetable clash finder — which pairs of meetings overlap?
import random, time
random.seed(9); M = [(s, s + random.randint(1, 3)) for s in random.choices(range(0, 200), k=500)]
t = time.perf_counter(); n2 = sum(1 for i in range(len(M)) for j in range(i + 1, len(M)) if M[i][0] < M[j][1] and M[j][0] < M[i][1]); t2 = time.perf_counter() - t
t = time.perf_counter(); ev = sorted([(s, 1, i) for i, (s, e) in enumerate(M)] + [(e, 0, i) for i, (s, e) in enumerate(M)]); open_ = set(); sw = 0
for _, kind, i in ev:                                      # sort + sweep: ends (0) before starts (1) at the same time
    if kind: sw += len(open_); open_.add(i)
    else: open_.discard(i)
t1 = time.perf_counter() - t
print(f"O(n²): {n2} clashes in {t2*1000:.1f} ms · sort+sweep O(n log n): {sw} clashes in {t1*1000:.1f} ms")
EOF

✅ Verify — what you should see

The decision table; OK from the tests with 12 checks; both clash counts equal, with the sweep several times faster at 500 meetings — and the gap growing if you raise k.

🏁 What you just proved

Given a new question you can name the brute force, the pattern, the structure and the cost — and you built the capstone both ways and measured the difference.

⚠️ Common mistakes

Reaching for the clever structure before writing the brute force (you need it to test against).
Optimising the wrong part: measure first (lesson 01).
Forgetting the edges: empty input, one item, all equal, already sorted, enormous.

🏭 Why this matters in production: this table is the performance review checklist: every hot path should be able to say which row it is on and why.

🏆 Capstone

Extend the clash finder: report which meetings clash (not just how many), handle meetings in several rooms (a dict of sweeps), and write a test for an empty timetable, a single meeting, and two identical meetings. Then explain, in a paragraph, why sort-and-sweep is O(n log n).

🎓 The course is complete

The study plan ticks the twelve off; the quiz checks them; the Database school puts lesson 09's trees on disk, and the School portal has the certificate.

← Previousdp greedy Finished! Take the quiz →check what stuck

This page is the lesson's README from the lesson-12-choosing branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.