कोडिंग इंटरव्यू: बाइनरी सर्च के साथ k-वां मिसिंग पॉजिटिव पूर्णांक कैसे खोजें?

इंटरव्यूअर क्या मूल्यांकन करता है

सतही समस्या ऐरे में गिनने की है; मुख्य बात यह है कि "इंडेक्स i तक कितने मान मिसिंग हैं" को एक मोनोटोन प्रेडिकेट में बदलना और फिर उसकी बाउंड्री खोजना। LeetCode 1539 सार्वजनिक समस्या विवरण और एक Amazon समस्या-सेट प्रविष्टि प्रदान करता है। Amazon का SDE मार्गदर्शन निष्पादन योग्य, मजबूत, परीक्षित कोड और एज-केस जांचों पर जोर देता है। ये स्रोत तैयारी के मूल्य का समर्थन करते हैं, किसी भी कंपनी के लिए एक निश्चित इंटरव्यू-आवृत्ति का दावा नहीं करते।

• क्या आप missing(i) = arr[i] - i - 1 लिखते हैं।
• क्या आप सिद्ध करते हैं कि मिसिंग काउंट गैर-घटता (non-decreasing) है।
• क्या आप ऐरे के अंतिम तत्व से परे के उत्तर को संभालते हैं।
• क्या आप कॉन्ट्रैक्ट के अनुसार स्कैनिंग, बाइनरी सर्च और प्रत्यक्ष जनरेशन की तुलना करते हैं।

30-सेकंड उत्तर ढांचा

बताएं कि ऐरे शून्य-आधारित इंडेक्स का उपयोग करता है। arr[i] तक, मान रेंज में arr[i] धनात्मक पूर्णांक हैं लेकिन केवल i + 1 देखे गए तत्व हैं, इसलिए मिसिंग काउंट arr[i] - i - 1 है। missing(i) >= k वाले पहले इंडेक्स को बाइनरी-सर्च करें। यदि यह i है, तो उत्तर k + i है; यदि कोई इंडेक्स इसे संतुष्ट नहीं करता है, तो उत्तर ऐरे के बाद है और k + n है। स्कैनिंग में O(n), बाइनरी सर्च में O(log n) समय लगता है, और दोनों O(1) अतिरिक्त स्पेस का उपयोग करते हैं।

उत्तर देने से पहले स्पष्ट करने वाले प्रश्न

1. क्या ऐरे के स्ट्रिक्टली बढ़ते क्रम में और धनात्मक होने की गारंटी है? यदि नहीं, तो सॉर्टिंग या डुप्लिकेट हटाना कॉन्ट्रैक्ट को बदल देता है।
2. क्या k धनात्मक है, और क्या मान भाषा की सुरक्षित पूर्णांक सीमा से अधिक हो सकते हैं?
3. क्या एक मान की आवश्यकता है, या सभी मिसिंग मानों की? सभी मान लौटाने की आउटपुट लागत होती है।
4. क्या इनपुट को रैंडम एक्सेस के बिना स्ट्रीम किया जा सकता है? वह स्कैन के पक्ष में हो सकता है।
5. क्या मूल ऐरे को अपरिवर्तित रहना चाहिए? बाइनरी-सर्च समाधान इसे म्यूटेट नहीं करता है।

चरण-दर-चरण विस्तृत विश्लेषण

चरण 1: मिसिंग-काउंट सूत्र बनाएं

यदि ऐरे निरंतर होता, तो arr[i] का मान i + 1 के बराबर होता। यह अंतर [1, arr[i]] से मिसिंग धनात्मक पूर्णांकों की संख्या है:

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

arr = [2, 3, 4, 7, 11] और i=3 के लिए, missing(3) = 7 - 3 - 1 = 3; मिसिंग मान 1, 5 और 6 हैं।

चरण 2: बाउंड्री के लिए मोनोटोनिसिटी का उपयोग करें

स्ट्रिक्ट बढ़ोतरी से arr[i+1] >= arr[i] + 1 मिलता है। इसलिए missing(i+1) >= missing(i), जिससे काउंट कभी नहीं घटता। missing(i) >= k वाले पहले इंडेक्स को खोजें: इससे पहले की हर चीज़ में बहुत कम मिसिंग मान हैं, जबकि वह इंडेक्स और उसके बाद की हर चीज़ में कम से कम k हैं।

चरण 3: बाउंड्री से उत्तर पुनर्प्राप्त करें

मान लें कि बाउंड्री i है। इसके पहले ऐरे के i देखे गए तत्व हैं, और बाउंड्री से पहले k से कम मिसिंग मान हैं। इसलिए k-वां मिसिंग मान k + i है। यदि कोई बाउंड्री मौजूद नहीं है, तो अंतिम मिसिंग काउंट अभी भी k से कम है; सभी n देखे गए तत्व उत्तर से पहले स्थित हैं, इसलिए परिणाम k + n है।

चरण 4: बाइनरी सर्च लागू करें

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

right = n का उपयोग करने से बाउंड्री को ऐरे के तुरंत बाद आने की अनुमति मिलती है। समाप्ति पर, left वह पहली स्थिति है जिसकी मिसिंग काउंट k तक पहुँचती है, इसलिए वही k + left सूत्र दोनों स्थितियों को संभालता है।

चरण 5: जटिलता सिद्ध करें और बाउंड्री का परीक्षण करें

प्रत्येक इटरेशन सर्च अंतराल को आधा कर देता है, जिससे O(log n) समय और स्थिर अतिरिक्त वेरिएबल मिलते हैं। 6 के लिए arr = [1,2,3,4], k = 2, 9 के लिए arr = [2,3,4,7,11], k = 5, 1 से मिसिंग अनुक्रम, एक निरंतर टेल, k=1, और एक-तत्व वाले ऐरे का परीक्षण करें। चुनी गई भाषा में पूर्णांक सीमाओं की भी जांच करें।

मॉडल उच्च-गुणवत्ता वाला उत्तर

मैं इंडेक्स i तक मिसिंग धनात्मक पूर्णांकों की संख्या को arr[i] - i - 1 के रूप में परिभाषित करूँगा। चूंकि ऐरे स्ट्रिक्टली बढ़ता हुआ है, इसलिए वह काउंट मोनोटोन है, इसलिए मैं पहले इंडेक्स को बाइनरी-सर्च करता हूँ जिसका काउंट कम से कम k है। यदि बाउंड्री i है, तो k-वां मिसिंग मान k + i है; राइट बाउंड्री को n पर सेट करना स्वाभाविक रूप से अधिकतम ऐरे मान के बाद के उत्तर को संभालता है।

मैं एक हाफ-ओपन अंतराल [left, right) का उपयोग करता हूँ। जब missing(mid) का मान k से कम होता है, तो बाउंड्री दाईं ओर होती है; अन्यथा मैं mid को बनाए रखता हूँ। परिणाम k + left है, जो O(log n) समय और O(1) स्पेस में आता है। मैं शुरुआती गैप, अंतिम गैप, एक निरंतर ऐरे, सिंगलटन और कई k मानों का परीक्षण करता हूँ, और स्कैन-आधारित ओरेकल से तुलना करता हूँ।

सामान्य गलतियाँ

• arr[i] - i लिखना और घटाव वाले एक पद को छोड़ देना।
• अंतिम false स्थिति को खोजना लेकिन पहले true वाले उत्तर सूत्र का उपयोग करना।
• right को n - 1 पर सेट करना और ऐरे के बाद के उत्तरों को गलत तरीके से संभालना।
• इनपुट के अनसॉर्टेड होने या डुप्लिकेट होने पर सूत्र लागू करना।
• केवल उदाहरणों का परीक्षण करना और [1,2,3], [2], या निरंतर टेल को छोड़ देना।
• सॉर्ट किए गए इनपुट और छोटे-n स्थिरांकों पर चर्चा किए बिना यह दावा करना कि बाइनरी सर्च हमेशा तेज़ होता है।

कार्यान्वयन के ट्रेड-ऑफ

डेटा आकार और बाउंड्री कॉन्ट्रैक्ट से लीनियर स्कैनिंग या बाइनरी सर्च चुनें, फिर परीक्षणों के साथ इनवेरिएंट को सत्यापित करें।

फॉलो-अप प्रश्न और उत्तर

मिसिंग काउंट मोनोटोन क्यों है?

स्ट्रिक्ट वृद्धि का अर्थ है कि अगला मान कम से कम एक से बढ़ता है। जब इंडेक्स एक बढ़ता है, तो मान भी कम से कम एक बढ़ता है, इसलिए arr[i] - i - 1 घट नहीं सकता।

क्या होगा यदि ऐरे अनसॉर्टेड है या इसमें डुप्लिकेट हैं?

पहले कॉन्ट्रैक्ट बदलें: सॉर्ट करें, डुप्लिकेट हटाएं, और धनात्मक मान रखें। सॉर्टिंग की लागत कम से कम O(n log n) है; केवल तभी मूल मिसिंग-काउंट सूत्र लागू होता है। अनसॉर्टेड इनपुट के लिए O(log n) का दावा न करें।

लीनियर स्कैन कब बेहतर होता है?

छोटे ऐरे, एकल क्वेरी, या बिना रैंडम एक्सेस वाले स्ट्रीम के लिए, स्कैनिंग सरल है। बाइनरी सर्च सॉर्ट किए गए रैंडम-एक्सेस इनपुट को मानता है और इसमें सेटअप और स्थिर लागत होती है।

आप पहले k मिसिंग मान कैसे लौटाएंगे?

मान बाउंड्री खोजें, फिर ऐरे पॉइंटर के साथ O(k) आउटपुट समय में मान उत्पन्न करें। आउटपुट कार्य को O(log n) के दावे के अंदर छिपाया नहीं जा सकता।

बड़े k या मानों के लिए ओवरफ्लो को कैसे रोकें?

एक सुरक्षित पूर्णांक या 64-बिट प्रकार का उपयोग करें और k + left और arr[i] - i - 1 की जांच करें। यदि मनमानी सटीकता की अनुमति है, तो इंटरफ़ेस और परीक्षणों में BigInt या समकक्ष निरूपण निर्दिष्ट करें।

स्कोरिंग रूब्रिक

एक मजबूत उम्मीदवार मोनोटोन प्रेडिकेट निकालता है, हाफ-ओपन सर्च लागू करता है, और उत्तर सूत्र की व्याख्या करता है। एक उम्मीदवार जो केवल कोड याद रखता है और बाउंड्री को सिद्ध नहीं कर सकता, उसे आगे जांचने की आवश्यकता होती है।