भाग 1: जागा (पिवळसर, 1–6) · भाग 2: चाली (निळा, 7–12). प्रत्येक आकृती म्हणजे खरी structure — आणि प्रत्येकीखाली हाताळता येणारी lab: ट्रे ठेवा, नाव hash करा, search पावलापावलाने चालवा, झाड वाढवा, नकाशा चाला. वर्तुळातले आकडे 1 → 2 → 3 या क्रमाने पहा.
शाळा दुप्पट झाल्यावर काम कसे वाढते — O(1), O(log n), O(n), O(n log n), O(n²); आकार हाच अख्खा विषय.
प्रगतिपुस्तके वाटण्याचा विचार करा. शाळा 1,000 वरून 2,000 विद्यार्थ्यांची झाली की काही कामांना तेवढाच वेळ लागतो, काहींना दुप्पट, आणि प्रत्येक विद्यार्थ्याची प्रत्येकाशी तुलना करायला चारपट. वाढीच्या या आकारालाच Big-O म्हणतात, म्हणजे शाळा वाढण्याआधीच खर्च कळतो.
Big-O शिवाय शाळा दुप्पट झाल्यावर program अचानक चारपट वेळ घेतो तेव्हाच तो slow आहे हे कळते.
n वाढला की steps कसे वाढतात त्याच्या आकाराला Big-O नाव देते: O(1), O(log n), O(n), O(n log n), O(n²).
constants काढा आणि सर्वात मोठे पद ठेवा: 3n + 5 म्हणजे O(n), n² + n म्हणजे O(n²), आणि x in list worst case मध्ये O(n).
1,000 चे 2,000 विद्यार्थी झाले तर O(log n) ला फक्त +1 look, पण O(n²) ला ×4 काम; म्हणून आकारच पुढचा खर्च ठरवतो.
arrays पासून graphs पर्यंत पुढचा प्रत्येक lesson याच एका मापाने तपासला जातो: n दुप्पट झाला की खर्च कसा वाढतो?
लॉकर्सची रांग — लॉकर 17 वर एका पावलात; पुढे घातले की सगळे सरकतात; two pointers आणि sliding window.
शाळेचे lockers एकाच क्रमांकित रांगेत आहेत, सगळे एकाच आकाराचे. locker 17 गाठायला इतर lockers ओलांडावे लागत नाहीत; एका step मध्ये थेट तिथे जाता येते. पण locker 0 मध्ये नवा विद्यार्थी घुसवला तर प्रत्येकाला एक locker पुढे सरकावे लागते, म्हणून सुरुवातीला जोडणे हळू आणि शेवटी जोडणे जलद.
क्रमांक असलेले lockers नसतील तर slot 3 मधला विद्यार्थी शोधायला सुरुवातीपासून प्रत्येक locker पार करावा लागतो.
array म्हणजे शेजारी-शेजारी ठेवलेली समान आकाराच्या lockers ची रांग, त्यामुळे कोणताही index एका step मध्ये मिळतो.
address = start + index × size, म्हणून lockers[3] एका step मध्ये Meera देतो, पण insert(0) सर्व n items सरकवतो: O(n).
index ने जलद वाचन, शेवटी O(1) append, आणि two pointers सारख्या युक्त्या O(n²) शोध एका O(n) pass मध्ये आणतात.
insert करताना सरकवणे महाग पडते तेव्हा पुढचा lesson linked lists वापरून index jump च्या बदल्यात स्वस्त insert देतो.
खजिन्याचा शोध — प्रत्येक चिठ्ठी सांगते पुढची कुठे; चिठ्ठी जोडायला O(1), शोधायला O(n), उडी नाही; जागच्या जागी उलटी करा.
treasure hunt मध्ये प्रत्येक चिठ्ठी पुढची चिठ्ठी कुठे लपवली आहे ते सांगते. सुरुवातीला नवी चिठ्ठी जोडणे सोपे: ती लिहा, जुन्या पहिल्या चिठ्ठीकडे दाखवा, आणि बाकी कोणीच हलत नाही. पण चौथी चिठ्ठी गाठायला आधीच्या तीन वाचाव्या लागतात, कारण चिठ्ठ्यांना थेट उडी मारता येईल असे क्रमांक नसतात.
array मध्ये पुढे एक विद्यार्थी जोडला तर बाकी सर्व lockers सरकतात, n विद्यार्थ्यांसाठी n moves.
linked list म्हणजे चिठ्ठ्यांचा treasure hunt, जिथे प्रत्येक चिठ्ठीत value आणि पुढच्या चिठ्ठीकडे pointer असतो.
push_front एक नवी चिठ्ठी जुन्या head कडे point करून लिहितो आणि head तिच्याकडे हलवतो: O(1), पण Meera शोधणे O(n).
हातातल्या चिठ्ठीजवळ जोडणे किंवा काढणे O(1) आहे आणि array insert सारखे इतर कोणीही सरकत नाही.
जोडलेले nodes पुढच्या lessons मधल्या stacks, queues, trees आणि graphs चे मूळ घटक बनतात.
ट्रेची चळत आणि जेवणाची रांग — LIFO आणि FIFO; brackets, undo, call stack; रांग सोडणे O(1) व्हावे म्हणून ring buffer.
canteen मध्ये स्वच्छ trays चा ढीग असतो आणि तुम्ही नेहमी वरचा tray घेता: शेवटी ठेवलेला tray आधी उचलला जातो. जेवणाची रांग उलट: आधी आलेल्याला आधी जेवण. computers दोन्ही सतत वापरतात, undo बटणासाठी आणि वाट पाहणाऱ्या पाळ्यांसाठी, आणि ring buffer मुळे कोणालाही न सरकवता रांग पुढे जाते.
lunch line साठी list.pop(0) वापरले तर प्रत्येक वेळी सर्वांना पुढे सरकवावे लागते: प्रत्येक जाण्याला O(n).
stack म्हणजे trays चा ढीग, शेवटी आलेला आधी बाहेर (LIFO); queue म्हणजे lunch line, आधी आलेला आधी बाहेर (FIFO).
push, pop, peek फक्त top ला हात लावतात: O(1); ring buffer मध्ये (i + 1) % 8 ने head आणि tail हलतात, कोणी सरकत नाही.
bracket matching, undo, call stack आणि न्याय्य रांगा हे सर्व यांच्यावर चालते, प्रत्येक operation O(1) मध्ये.
recursion मध्ये call stack पुन्हा येतो, आणि lesson 10 मध्ये graphs शोधताना queue BFS चालवते.
नावानुसार कप्पे — hash(name) सांगते कोणता कप्पा; सरासरी O(1); collisions, rehashing, मोजणी, dedupe.
शाळेच्या office मध्ये pigeonholes आहेत. प्रत्येक कप्पा शोधण्याऐवजी एक नियम विद्यार्थ्याच्या नावाचा box क्रमांक बनवतो, म्हणून तुम्ही थेट Meera च्या box कडे जाता. कधी दोन नावे एकाच box मध्ये येतात; हरकत नाही, एक-दोन cards तपासायचे. boxes खूप भरले की office त्यांची संख्या दुप्पट करते आणि सगळ्यांना एकदा पुन्हा मांडते.
साध्या list मध्ये नावाने विद्यार्थी शोधायचा तर तो सापडेपर्यंत प्रत्येक card वाचावे लागते: प्रत्येक वेळी O(n).
hash map प्रत्येक item त्याच्या नावावरून ठरलेल्या pigeonhole मध्ये ठेवतो, म्हणून key ने शोध सरासरी O(1).
hash(name) % 8 box निवडतो; collision झाले तर एकाच box मध्ये दोन cards, आणि load 0.75 झाला की 16 boxes करून पुन्हा मांडणी.
शब्द मोजणे, duplicates काढणे आणि नावाने शोधणे एका pass मध्ये होते, म्हणूनच dict आणि set सगळीकडे दिसतात.
वाईट hash सर्वांना एकाच box मध्ये टाकतो आणि O(n) परत येतो, म्हणून खऱ्या systems चांगले hash निवडून load factor पाहतात.
मुख्याध्यापक उपमुख्याध्यापकांना विचारतात, ते शिक्षकांना — base case, एक लहान प्रश्न, call stack; फळ्याशिवाय fib का फुटते.
मुख्याध्यापकांना 5! हवा, ते उपमुख्याध्यापकांना 4! विचारतात, ते एका शिक्षकांना 3!, असे 1! = 1 पर्यंत, जे सगळ्यांना माहीत आहे. मग उत्तरे परत वर जातात: 1, 2, 6, 24, 120. हेच recursion: त्याच प्रश्नाची छोटी आवृत्ती विचारून काम सोडवणे. पण उत्तरे लिहायला फळा नसेल तर fib तेच प्रश्न पुन्हा पुन्हा विचारतो.
काही प्रश्न, जसे 5!, हे त्याच प्रश्नाचे लहान रूप असतात, आणि त्यांना हाताने loop म्हणून लिहिणे अवघड होते.
recursion म्हणजे function जो base case पर्यंत पोहोचेपर्यंत स्वतःलाच लहान प्रश्न विचारून उत्तर देतो.
fact(5) fact(4) ला विचारतो, असे 1! = 1 पर्यंत; पाच frames call stack वर थांबतात आणि उत्तरे 120 पर्यंत वर परत येतात.
stack depth आणि पुन्हा पुन्हा होणारे काम लक्षात ठेवले तर tree आणि divide-and-conquer code छोटा आणि स्पष्ट होतो.
board शिवाय fib हा fib(3) वगैरे पुन्हा विचारतो; हाच अपव्यय lesson 11 मधले dynamic programming काढून टाकते.
वर्गाची उंचीनुसार रांग — bubble आणि insertion (n²), merge आणि quick (n log n), stability, आणि तुम्ही sorted() का बोलावता.
वर्गाला उंचीप्रमाणे रांगेत उभे करा. शेजाऱ्यांची पुन्हा पुन्हा अदलाबदल करणे चालते, पण 2,000 विद्यार्थ्यांसाठी सुमारे 20 लाख तुलना लागतात. merge sort वर्गाचे अर्धे भाग करतो, प्रत्येक भाग क्रमाने लावतो, मग दोन क्रमाने लावलेल्या रांगा एकत्र गुंफतो, खूप कमी तुलनांत. sorting महत्त्वाचे कारण क्रमाने लावलेल्या list मध्ये शोधणे आणि गट करणे जलद होते.
शेजारी अदलाबदल करून 2,000 विद्यार्थी रांगेत लावायला सुमारे वीस लाख तुलना लागतात, आणि n दुप्पट झाला की चारपट.
sorting म्हणजे items क्रमाने लावणे; bubble आणि insertion sort O(n²) आहेत, तर merge sort आणि quicksort O(n log n).
merge sort रांग log n levels पर्यंत अर्धी करतो, मग प्रत्येक level वर n काम करून sorted अर्धे जोडतो: n log n.
sorted data मुळे binary search आणि सोपे grouping शक्य होते, आणि stability समजली तर equal keys चा क्रम टिकतो का ते कळते.
खऱ्या code मध्ये तुम्ही sorted() वापरता, जो stable n log n sort आहे, आणि तुमची मेहनत योग्य key निवडण्यात जाते.
क्रमाने लावलेली नोंदवही — मधोमध उघडा, अर्धी फेकून द्या, 50,000 नावांसाठी जास्तीत जास्त 16 नजरा; उत्तरावर search.
क्रमाने लावलेल्या हजेरीपटात नाव शोधायला तो मध्यभागी उघडा. नाव आधी येत असेल तर मागचा अर्धा भाग बाजूला टाका; नंतर येत असेल तर पुढचा. असे अर्धे करत राहिले तर 50,000 नावांसाठीही जास्तीत जास्त 16 वेळा पाहावे लागते. हे फक्त हजेरीपट क्रमाने लावलेला असल्यामुळेच चालते.
register मध्ये एकेक ओळ वाचून नाव शोधले तर 50,000 नावांसाठी 50,000 पर्यंत looks लागतात.
binary search sorted list मध्ये मध्य उघडून दर वेळी अर्धा भाग टाकून item शोधतो: O(log n).
37 शोधताना: mid 42 डावा भाग ठेवतो, mid 18 मुळे 25 ते 37, mid 31 नंतर फक्त 37 उरतो; 4 looks मध्ये index 6.
register sorted ठेवले तर 50,000 नावांसाठी जास्तीत जास्त 16 looks आणि दहा लाखांसाठी फक्त 20.
हीच अर्धे करण्याची कल्पना थेट उत्तरावर search करू देते, आणि lesson 9 मधल्या balanced trees मध्येही तीच आहे.
कॅटलॉगचा खण आणि व्यासपीठ — BST insert आणि search, in-order चाल, balance का महत्त्वाचा; heap सगळ्यात लहान वर ठेवतो.
ग्रंथालयाच्या catalogue drawer मध्ये लहान क्रमांक डावीकडे आणि मोठे उजवीकडे जातात, म्हणून प्रत्येक वेळी पाहताना उरलेल्यापैकी अर्धे वगळले जाते. पण आधीच क्रमाने असलेली cards जोडली तर tree एक लांब रांग बनते आणि वेग जातो, म्हणून ते balanced राहायला हवे. heap म्हणजे podium: सर्वात लहान नेहमी वर, आधी उचलायला तयार.
sorted array मध्ये शोध जलद पण प्रत्येक insert मध्ये items सरकतात, आणि साध्या list मध्ये सर्वात लहान शोधायला सर्व वाचावे लागते.
BST लहान keys डावीकडे आणि मोठ्या उजवीकडे ठेवतो; heap हा tree नेहमी सर्वात लहान value वर ठेवतो.
search(37): 50 वरून डावीकडे, 25 वरून उजवीकडे, 3 looks मध्ये सापडले; array मधल्या heap मध्ये i ची मुले 2i+1 आणि 2i+2 वर.
balanced trees O(log n) search आणि insert तसेच मोफत sorted walk देतात, आणि heap पुढचा सर्वात लहान पटकन देतो.
1 ते 7 क्रमाने घातले तर height 7 ची list बनते, म्हणून खऱ्या systems AVL सारखे self-balancing trees वापरतात.
कॉरिडॉरचा नकाशा — adjacency lists, BFS hops ने पसरतो, DFS एक कॉरिडॉर धरतो, Dijkstra मोजतो, cycles.
शाळेचा नकाशा म्हणजे corridors ने जोडलेल्या खोल्या. gym पर्यंत सर्वात कमी corridors शोधायला office पासून एकेक फेरी बाहेर पसरा (BFS). सर्वात कमी मीटर शोधायला अजून निश्चित न झालेली सर्वात जवळची खोली निवडत राहा (Dijkstra). दोन्ही वेगळे उत्तर देऊ शकतात: lab मार्गे gym 65 m, पण library मार्गे 90 m.
rooms आणि corridors एका रांगेत किंवा tree मध्ये बसत नाहीत, म्हणून graphs शिवाय gym कडे सर्वात छोटा रस्ता विचारताही येत नाही.
graph म्हणजे corridors (edges) ने जोडलेल्या rooms (vertices) चा संच, जो neighbours च्या adjacency list मध्ये साठवला जातो.
BFS hops ने पसरतो, DFS एक corridor खोलवर पकडतो, आणि Dijkstra metres मोजून office ते gym चा 65 m रस्ता शोधतो.
सर्वात कमी hops आणि सर्वात कमी metres वेगळे असू शकतात, म्हणून BFS आणि Dijkstra मधला फरक कळला तर नेमक्या प्रश्नाचे उत्तर मिळते.
maps, networks, build systems आणि friend lists हे सर्व graphs आहेत, म्हणून हे walks खऱ्या software मध्ये सगळीकडे दिसतात.
फळ्यावरची उत्तरे — memoisation आणि tabulation (पायऱ्या, नाणी); greedy: आधी संपणारी meeting घ्या.
एका वेळी 1 किंवा 2 पायऱ्या चढत 8 पायऱ्या किती प्रकारे चढता येतील? खालून सुरू करा आणि प्रत्येक उत्तर फळ्यावर लिहा: प्रत्येक नवे उत्तर म्हणजे आधीच्या दोनांची बेरीज, म्हणून काहीच दोनदा मोजावे लागत नाही. greedy म्हणजे आत्ता सर्वात चांगला दिसणारा पर्याय घेणे; आधी संपणारी meeting निवडताना ते चालते, पण 1, 3, 4 च्या coins ने 6 बनवताना चुकते.
साधे recursion तेच छोटे प्रश्न पुन्हा पुन्हा सोडवते, म्हणून stairs(n) किंवा fib(n) exponentially वाढतो.
dynamic programming प्रत्येक छोटे उत्तर board वर एकदाच लिहून पुन्हा वापरते; greedy आत्ता सर्वात चांगली दिसणारी पायरी घेतो.
board खालून वर भरा: s(5) = s(4) + s(3) = 5 + 3, प्रत्येक cell एकदाच लिहिली जाते, म्हणून stairs O(n) होतो.
coins [1, 3, 4] ने 6 बनवताना DP 2 coins (3 + 3) शोधते, greedy 4 + 1 + 1 घेतो; म्हणून greedy कधी सुरक्षित ते कळते.
board ची ही विचारपद्धत diff tools, route planners आणि schedulers चालवते, आणि लवकर संपणारी meeting सारखा greedy सिद्ध झाल्यावर जिंकतो.
प्रश्न ठरवतो — complexity cheat sheet, निर्णय तक्ता, मुलाखतीची पद्धत, आणि कळस-प्रकल्प.
काहीही बनवण्याआधी प्रश्न मोठ्याने बोला. '5 वा विद्यार्थी दे' म्हणजे array; 'नावाने शोध' म्हणजे hash map; 'पुढचा सर्वात लहान कोण' म्हणजे heap; 'खोल्या आणि corridors' म्हणजे graph. प्रश्नच structure निवडतो, आणि योग्य structure हळू कामाला जलद बनवते.
दहा structures माहीत असूनही नवीन प्रश्नासमोर कोणता हवा हे ओळखता आले नाही तर उपयोग नाही.
प्रश्न काय विचारतो आणि कोणता structure त्याचे उत्तर देतो, त्याच्या Big-O खर्चासह, हे जोडणारे decision table.
i-th गोष्ट म्हणजे array O(1), नावाने म्हणजे hash map O(1) avg, पुढचा लहान म्हणजे heap O(log n), rooms म्हणजे graph O(V+E).
प्रश्न मोठ्याने बोला आणि structure स्वतः उत्तर देतो; हीच पद्धत coding interviews मध्येही कामी येते.
आधी brute force लिहा, मग pattern ओळखा; capstone आणि प्रत्येक खरा design review याच सवयीने चालतो.