1. इनपुट 1,000 से 1,000,000 हो जाता है। O(log n) चरण गणना लगभग...
- तीन गुना
- 1000 गुना बढ़ती है
- ~10 चरण बढ़ती है
- दोगुना होता है
जवाब देखें
जवाब: ~10 चरण बढ़ती है
log2(1e6) - log2(1e3) लगभग 20 - 10 = 10 अतिरिक्त चरण।
पाठ: Big-O और जटिलता
Data Structures और Algorithms: Interviews के लिए Patterns कोर्स के 22 सवाल, हर सवाल के सही जवाब और explanation के साथ। जवाब देखने से पहले ख़ुद सोचें।
जवाब: ~10 चरण बढ़ती है
log2(1e6) - log2(1e3) लगभग 20 - 10 = 10 अतिरिक्त चरण।
पाठ: Big-O और जटिलता
जवाब: वर्ण गणनाओं की तुलना करें
हर वर्ण गिनना O(n) है; क्रमचय O(n!) हैं।
पाठ: Strings
जवाब: Hash map
Hash map प्रति lookup औसत O(1); binary search O(log n) और sorting चाहिए।
पाठ: Hash Map
जवाब: O(n)
क्रमबद्ध insert दाईं ओर झुकी श्रृंखला बनाते हैं — असल में linked list। संतुलित trees (AVL, red-black) इसे ठीक करते हैं।
पाठ: Binary Search Tree
जवाब: O(log n)
दोनों index को सबसे कम set bit बदलते हुए ऊपर/नीचे जाते हैं, O(log n) चरणों में।
पाठ: Fenwick Tree (BIT)
जवाब: सभी edge weights गैर-ऋणात्मक हों
Negative weights greedy 'सबसे नज़दीकी node final है' मान्यता को गलत कर सकते हैं — इसकी जगह Bellman-Ford इस्तेमाल करें।
पाठ: Dijkstra's Algorithm
जवाब: लगभग O(1) (inverse-Ackermann)
Amortized complexity O(α(n)) है, inverse Ackermann function, जो किसी भी वास्तविक n के लिए प्रभावी रूप से स्थिर है।
जवाब: Sorted (या predicate पर monotonic)
आधा हटाना तभी काम करता है जब एक ओर लक्ष्य न होने की गारंटी हो — इसके लिए क्रम चाहिए।
पाठ: Binary Search
जवाब: O(n log n)
विभाजन हमेशा संतुलित होता है, इसलिए हर मामले में O(n log n) — quicksort के विपरीत।
पाठ: Merge Sort
जवाब: Sorted
Sorted क्रम ही तय करने देता है कि वर्तमान योग से कौन-सा पॉइंटर हिलाना है।
पाठ: Two Pointers
जवाब: BFS
BFS दूरी के क्रम में खोजता है, तो लक्ष्य तक पहली बार पहुँचना सबसे छोटा पथ है। DFS ऐसी गारंटी नहीं देता।
पाठ: Depth-First Search
जवाब: 2 सिक्के (3 + 3)
3+3 = 6 दो सिक्के उपयोग करता है। यहाँ greedy विफल — coin change को सामान्यतः DP चाहिए।
पाठ: Greedy
जवाब: O(n + m)
LPS array O(m) में बनती है, और खोज खुद O(n) है क्योंकि text pointer कभी पीछे नहीं जाता।
पाठ: String Matching
जवाब: यह किसी node को केवल उसका pointer देकर O(1) में हटाने देती है
prev pointer के साथ, एक node खुद को O(1) में unlink कर सकता है; singly linked list में पिछला node खोजने में O(n) लगेगा।
पाठ: LRU Cache Design
जवाब: O(log n)
हर कदम search range आधी करता है।
पाठ: K-way Merge
जवाब: Hash map
Hash function keys को buckets से map करता है।
पाठ: K-way Merge
जवाब: Stack
Opening push करें, closing पर pop करें।
पाठ: K-way Merge
जवाब: BFS
BFS level-by-level खोजता है।
पाठ: K-way Merge
जवाब: All edge weights are non-negative
Negative edges के लिए Bellman-Ford चाहिए।
पाठ: K-way Merge
जवाब: O(n log n)
यह हमेशा बराबर बाँटता और merge करता है।
पाठ: K-way Merge
जवाब: Sliding window
दाएँ बढ़ाएँ, ज़रूरत पर बाएँ घटाएँ।
पाठ: K-way Merge
जवाब: Overlapping subproblems and optimal substructure
पुनर्गणना से बचने के लिए subproblem उत्तर रखें।
पाठ: K-way Merge