उत्तर विश्लेषण के साथ इंटरव्यू प्रश्न — 52 में से पेज 51
तर्क, कार्यान्वयन विवरण, फॉलो-अप्स और सार्वजनिक स्रोतों के साथ Offer.cc इंटरव्यू प्रश्न और उत्तर विश्लेषण का पृष्ठ 51 ब्राउज़ करें।
कोडिंग इंटरव्यू: एक Array में kth सबसे बड़ा Element खोजें
सॉर्टिंग और bounded heap से लेकर randomized three-way quickselect तक kth सबसे बड़े उत्तर को सटीक partition invariant, डुप्लिकेट हैंडलिंग, कॉम्प्लेक्सिटी ट्रेड-ऑफ और निष्पादन योग्य टेस्ट्स के साथ समझें।
कोडिंग इंटरव्यू: रैंडम पॉइंटर्स वाली लिंक्ड लिस्ट को कॉपी करना
आइडेंटिटी मैप का उपयोग करके रैंडम पॉइंटर्स वाली लिंक्ड लिस्ट की डीप-कॉपी बनाना सीखें, फिर इंटरलीविंग ऑप्टिमाइज़ेशन निकालें, इसके इनवेरिएंट्स को सिद्ध करें और मूल लिस्ट को सुरक्षित रूप से पुनर्स्थापित करें।
कोडिंग इंटरव्यू: नेटवर्क में सभी क्रिटिकल कनेक्शन्स (Critical Connections) खोजें
डिस्कवरी समय (discovery times) और लो-लिंक (low-link) मानों का उपयोग करके एक अनडायरेक्टेड ग्राफ में प्रत्येक ब्रिज (bridge) खोजें, फिर सख्त ब्रिज शर्त को सिद्ध करें और स्टैक-सुरक्षित पुनरावृत्त (iterative) DFS लागू करें।
कोडिंग इंटरव्यू: k-ग्रुप में नोड्स को रिवर्स करना (Reverse Nodes in k-Group)
डमी नोड, कम्प्लीट-ग्रुप लुकअहेड और बाउंडेड पॉइंटर रिवर्सल का उपयोग करके k-ग्रुप में नोड्स को रिवर्स करने की समस्या को हल करें, और फिर साबित करें कि अधूरा अंतिम भाग (tail) अपरिवर्तित क्यों रहता है।
कोडिंग इंटरव्यू: हिस्टोग्राम में सबसे बड़ा आयत (Largest Rectangle) कैसे खोजें?
निकटतम-छोटे सीमाओं (nearest-smaller boundaries) से हिस्टोग्राम में सबसे बड़े आयत का एल्गोरिदम निकालें, वन-पास मोनोटोनिक स्टैक लागू करें, और इसकी शुद्धता और लीनियर कॉम्प्लेक्सिटी को सिद्ध करें।
कोडिंग इंटरव्यू: डायनेमिक प्रोग्रामिंग से एडिट डिस्टेंस की गणना कैसे करें?
स्ट्रिंग प्रीफिक्स पर एडिट-डिस्टेंस रिकरेंस व्युत्पन्न करें, इसके तीन ट्रांज़िशन सिद्ध करें, और O(mn) समय और O(min(m, n)) स्पेस के साथ एक रोलिंग-रो TypeScript समाधान लागू करें।
कोडिंग इंटरव्यू: सबसे लंबी बढ़ती उप-अनुक्रम (Longest Increasing Subsequence) कैसे खोजें?
द्विघातीय (quadratic) डायनेमिक प्रोग्रामिंग से न्यूनतम-टेल (minimum-tail) इनवेरिएंट प्राप्त करें, फिर बाइनरी सर्च, पूर्ववर्ती इंडेक्स (predecessor indices), और प्रॉपर्टी टेस्ट्स का उपयोग करके O(n log n) लॉन्गेस्ट इनक्रीजिंग सबसीक्वेंस एल्गोरिदम को लागू और सिद्ध करें।
कोडिंग इंटरव्यू: आप द्विदिशीय (Bidirectional) BFS के साथ Word Ladder को कैसे हल करते हैं?
Word Ladder को एक अप्रत्यक्ष (implicit) अभारित (unweighted) ग्राफ़ के रूप में मॉडल करें, सबसे छोटे अनुक्रम के अनुबंध से BFS प्राप्त करें, और सटीक प्रमाण, लागत मॉडल और प्रतिकूल (adversarial) परीक्षणों के साथ एक छोटे-फ्रंटियर वाली द्विदिशीय खोज को लागू करें।
कोडिंग इंटरव्यू: आप O(1) LFU कैश कैसे लागू करते हैं?
की इंडेक्स, फ्रीक्वेंसी बकेट्स, प्रति-बकेट डबल लिंक्ड लिस्ट्स और एक न्यूनतम-फ्रीक्वेंसी पॉइंटर के साथ एक LFU कैश लागू करें, फिर अपेक्षित O(1) get और put को सिद्ध करें।
कोडिंग इंटरव्यू: Minimum Window Substring को कैसे हल करें?
क्वाड्रैटिक बेसलाइन से वेरिएबल-लेंथ स्लाइडिंग विंडो प्राप्त करें, आवश्यक आवृत्तियों (frequencies) और संतुष्ट कैरेक्टर क्लासों को ट्रैक करें, और डुप्लिकेट्स, असंभव इनपुट्स तथा ब्रूट-फ़ोर्स ऑरेकल के विरुद्ध एक निष्पादन योग्य TypeScript समाधान सत्यापित करें।
कोडिंग इंटरव्यू: Two Pointers की मदद से Trapping Rain Water को कैसे हल करें?
प्रति-कॉलम जल सूत्र से प्रीफिक्स ऐरे और दो-पॉइंटर समाधान प्राप्त करें, यह सिद्ध करें कि ज्ञात छोटी सीमा को आगे बढ़ाना क्यों सुरक्षित है, और O(1) ऑक्जिलरी स्पेस के साथ O(n) टाइम को लागू और सत्यापित करें।
कोडिंग इंटरव्यू: आप K सॉर्टेड लिंक्ड लिस्ट्स को कैसे मर्ज करते हैं?
फ़्रंटियर इनवेरिएंट से O(N log k) मर्ज निकालें, इसे size-k मिन-हीप के साथ लागू करें, इसकी शुद्धता साबित करें, और इसकी तुलना स्कैनिंग, अनुक्रमिक मर्जिंग, सॉर्टिंग और डिवाइड-एंड-कॉन्कर से करें।
कोडिंग इंटरव्यू: Dijkstra का सबसे छोटा पथ (Shortest Path) एल्गोरिदम लागू करना
Adjacency list, lazy heap deletion, और path reconstruction के साथ Dijkstra को लागू करें; इसके greedy invariant को सिद्ध करें और early exit, जटिलता (complexity) तथा negative-edge की सीमाओं को स्पष्ट करें।
कोडिंग इंटरव्यू: Union-Find कैसे लागू करें और कनेक्टेड कॉम्पोनेंट्स को कैसे ट्रैक करें?
डायनामिक कनेक्टिविटी क्वेरीज़ से Union-Find को समझें, union by size और path halving के साथ union, connected और कॉम्पोनेंट काउंटिंग लागू करें, और शुद्धता (correctness), एमॉर्टाइज़्ड जटिलता, परीक्षणों (tests) और डिलीशन की सीमाओं की व्याख्या करें।
कोडिंग इंटरव्यू: मोनोटोनिक डेक (Monotonic Deque) से स्लाइडिंग विंडो मैक्सिमम कैसे हल करें?
ब्रूट-फोर्स और हीप दृष्टिकोणों से मोनोटोनिक डेक व्युत्पन्न करें, डॉमिनेशन, इनवेरिएंट्स और अमोर्टाइज्ड विश्लेषण के साथ O(n) समय सिद्ध करें, और TypeScript में एक सर्कुलर डेक लागू करें जो वास्तव में O(k) स्पेस का उपयोग करता है।
कोडिंग इंटरव्यू: एक बाइनरी ट्री का लोएस्ट कॉमन एन्सेस्टर (LCA) खोजें
पाथ बेसलाइन से सिंगल-पास पोस्टऑर्डर समाधान निकालें, इसे सब-ट्री रिटर्न इनवेरिएंट के साथ सिद्ध करें, और डुप्लिकेट वैल्यू, अनुपस्थित टारगेट, अत्यधिक गहरे ट्री और बार-बार की जाने वाली क्वेरी को संभालें।
कोडिंग इंटरव्यू: बाइनरी ट्री को सीरियलाइज़ और डिसीरियलाइज़ करना
स्पष्ट null मार्कर्स के साथ एक रिवर्सिबल प्रीऑर्डर एन्कोडिंग डिज़ाइन करें, सिद्ध करें कि डिकोडर ठीक एक सब-ट्री को क्यों प्रोसेस करता है, और गलत इनपुट, गहरे ट्री और वैकल्पिक प्रारूपों को संभालें।
कोडिंग इंटरव्यू: डेटा स्ट्रीम से मीडियन निकालना
छोटे आधे भाग को max-heap में और बड़े आधे भाग को min-heap में रखें, स्पष्ट invariants से O(log n) insertion और O(1) queries प्राप्त करें, और correctness, edge cases, तथा sliding-window follow-ups को संभालें।
कोडिंग इंटरव्यू: बाइनरी सर्च का उपयोग करके पहली और अंतिम स्थिति ज्ञात करना
डुप्लिकेट्स, खाली ऐरे और अनुपस्थित टार्गेट्स को समान रूप से संभालने के लिए लोअर और अपर बाउंड्स का उपयोग करें, फिर हाफ-ओपन इंटरवल इनवेरिएंट्स के साथ O(log n) समाधान सिद्ध करें।
कोडिंग इंटरव्यू: ओवरलैपिंग इंटरवल्स (Intervals) को कैसे मर्ज करें?
सॉर्टिंग और ग्रीडी स्कैन (greedy scan) का उपयोग करके ओवरलैपिंग बंद अंतरालों (closed intervals) को मर्ज करें, फिर एंडपॉइंट नियम, शुद्धता के इनवेरिएंट (invariants), जटिलता और नॉन-म्यूटेटिंग अनुबंध को सही ठहराते हुए नेस्टेड, चेन्ड और स्ट्रीमिंग फॉलो-अप्स को संभालें।
Topological Sort का उपयोग करके Course Schedule II को कैसे हल करें?
कोर्स की पूर्व-आवश्यकताओं (prerequisites) से Kahn's topological sort निकालें, इसके zero-indegree invariant और cycle check को सिद्ध करें, और एकाधिक ऑर्डर, डुप्लिकेट एज और समानांतर सेमेस्टरों से संबंधित फॉलो-अप प्रश्नों को हल करें।
Insert, Search, Prefix और Delete के साथ एक Trie लागू करें
सटीक-मिलान और उपसर्ग आवश्यकताओं से एक Trie प्राप्त करें, साझा पथों को नुकसान पहुँचाए बिना सुरक्षित विलोपन (deletion) लागू करें, और टर्मिनल-मार्कर इनवेरिएंट, जटिलता और प्रतिकूल मामलों को सत्यापित करें।
डायनामिक टॉप-K फ़्रीक्वेंट आइटम्स के लिए डेटा स्ट्रक्चर डिज़ाइन करना
रीड-राइट अनुपात के आधार पर एक सटीक डायनामिक टॉप-k डेटा स्ट्रक्चर तैयार करें, जिसमें रन करने योग्य फ़्रीक्वेंसी-बकेट कोड, इनवेरिएंट्स और जटिलता शामिल हो; फिर परिभाषित करें कि सीमित मेमोरी में Space-Saving या Count-Min Sketch की आवश्यकता कब होती है।
एक थ्रेड-सुरक्षित बाउंडेड ब्लॉकिंग कतार (Thread-Safe Bounded Blocking Queue) लागू करें
रिंग बफ़र, एक लॉक और दो कंडीशंस का उपयोग करके एक बाउंडेड ब्लॉकिंग कतार लागू करें, फिर स्थिति इनवेरिएंट्स (state invariants), लीनियराइजेशन पॉइंट्स, स्पूरियस वेकअप्स और इंटरप्शन सेमेंटिक्स के माध्यम से इसकी शुद्धता सिद्ध करें।