मैजिक इंडेक्स: वह आई खोजो जहाँ ए[आई] बराबर आई (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ८.३: क्रमबद्ध सरणी में इंडेक्स आई जहाँ ए[आई] == आई। अलग-अलग मानों पर बाइनरी खोज। डुप्लिकेट पर दोनों तरफ़ सिकुड़ी सीमाएँ।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

होटल के कमरे कतार में नंबर ०, १, २, ... पर बैठे हैं। मेहमान सूची कमरे की पसंद संख्या के हिसाब से क्रमबद्ध है। मैजिक इंडेक्स वह कमरा है जहाँ मेहमान संख्या कमरे के नंबर से मिलती है: A[i] == i। कोई एक ऐसा कमरा चाहिए, या सबूत कि कोई नहीं, बिना हर दरवाज़ा खोलने के जब बचा जा सके।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाले "क्रमबद्ध सरणी में स्थिर बिंदु" परिवार का हिस्सा, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ८ (रिकर्शन और डायनामिक प्रोग्रामिंग) ग्रिड वॉक के बाद यहाँ आगे बढ़ता है।

१. रोज़मर्रा की उपमा

ताले ० से ६ तक पेंट किए सोचो। हर ताले में एक पूर्णांक वाली पर्ची डालो। पर्चियाँ बाएँ से दाएँ पहले से बढ़ते क्रम में हैं।

इंडेक्स (ताला)	०	१	२	३	४	५	६
मान (पर्ची)	-१	०	१	३	५	७	९

ताला ३ में पर्ची ३ है। यही मैजिक इंडेक्स। ताला ४ में ५ है, ४ नहीं।

अगर हर पर्ची अनूठी है, क्रमबद्ध कतार का आकार साफ़ है: जब मान इंडेक्स से ऊपर चढ़ जाएँ और इंडेक्स जितनी तेज़ी से बढ़ें, तो जोड़ी दाईं ओर छिप नहीं सकती। इसलिए बाइनरी खोज चलती है।

अगर पर्चियाँ दोहराई जा सकती हैं, कतार डगमगा सकती है। मान २ इंडेक्स १ पर हो और आगे फिर। पूरी आधी कतार हमेशा नहीं फेंक सकते, पर स्थिर बिंदु के लिए असंभव रेंज अभी भी कूद सकते हो।

२. समस्या सादे शब्दों में

इनपुट: पूर्णांकों की क्रमबद्ध सरणी A (गैर-घटती)। क्लासिक वार्मअप अलग-अलग मान मानता है। फॉलो-अप डुप्लिकेट अनुमति देता है।

आउटपुट: कोई इंडेक्स i जहाँ A[i] == i, या कोई न हो तो संतरी (यहाँ -1)।

उदाहरण (अलग-अलग):

सरणी	मैजिक इंडेक्स	क्यों
`{-1, 0, 1, 3, 5, 7, 9}`	`3`	`A[3] == 3`
`{0, 2, 3, 4, 5}`	`0`	पहली सेल मिलती है
`{1, 2, 3, 4}`	कोई नहीं	हर मान अपने इंडेक्स से सख्ती से ऊपर
`{-10, -5, 2, 5}`	`2`	सिर्फ बीच मिलान

डुप्लिकेट वाला उदाहरण:

A = {-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13}

इंडेक्स ७ चलता है (A[7] == 7)। मिड के हिसाब से दूसरे स्थिर बिंदु भी मिल सकते हैं अगर हों; इस समस्या में कोई एक लौटाना काफ़ी है।

इंटरव्यू में साफ़ करो:

बढ़ते क्रम में? (हाँ।)
अलग-अलग या नहीं? (पूछो। पहले अलग-अलग, फिर डुप्लिकेट।)
कोई भी मैजिक इंडेक्स या सबसे बायाँ? (कोई भी, जब तक वे न कहें।)
खाली सरणी? -1 लौटाओ।
ऋणात्मक मान ठीक? हाँ। इंडेक्स गैर-ऋणात्मक रहते हैं, इसलिए ऋणात्मक मान कभी अपने इंडेक्स से नहीं मिलता।

३. पहले सोचो

ब्रूट फोर्स

i को ० से n - 1 तक चलाओ। अगर A[i] == i, i लौटाओ। समय ओ(एन), जगह ओ(१)। छोटे एन पर ठीक। इंटरव्यू क्रम का इस्तेमाल चाहता है।

अलग-अलग मान: स्थिर-बिंदु अंतर पर बाइनरी खोज

मिड देखो। A[mid] की mid से तुलना करो।

बराबर: हो गया। mid लौटाओ।
A[mid] > mid: हर j > mid के लिए, क्रमबद्ध + अलग-अलग का मतलब A[j] >= A[mid] + (j - mid) > mid + (j - mid) = j। तो दाईं ओर हमेशा A[j] > j। सिर्फ बाएँ खोजो: 0 .. mid - 1।
A[mid] < mid: हर j < mid के लिए, A[j] <= A[mid] - (mid - j) < mid - (mid - j) = j। तो बाईं ओर हमेशा A[j] < j। सिर्फ दाएँ खोजो: mid + 1 .. n - 1।

यह सामान्य बाइनरी खोज है, अपनी तुलना के साथ (मान - इंडेक्स शून्य पार करता है)। रिकर्शन गहराई ओ(लॉग एन)।

डुप्लिकेट: दोनों तरफ़, पर सिकुड़ी

"अलग-अलग" कूद तब टूटती है जब मान सपाट रह सकते हैं। उदाहरण:

index: 0  1  2  3  4  5
value: 1  1  1  3  5  6

मिड २ पर, A[2] == 1 < 2। अलग-अलग नियम से सिर्फ दाएँ जाते; दूसरे आकार एक तरफ़ त्याग तोड़ देते हैं। डुप्लिकेट पर सुरक्षित नियम:

१. मिड जाँचो। मिलान हो तो लौटाओ। २. बाएँ तंग रेंज पर खोजो: start से Math.min(mid - 1, A[mid]) तक। ३. बायाँ फेल हो तो दाएँ Math.max(mid + 1, A[mid]) से end तक।

मिन/मैक्स क्यों?

बाएँ मैजिक इंडेक्स k को k <= mid - 1 और A[k] == k चाहिए। क्रम से A[k] <= A[mid], इसलिए k <= A[mid]। बायाँ ऊपरी बाउंड min(mid - 1, A[mid])।
दाएँ, k >= mid + 1 और k == A[k] >= A[mid], इसलिए निचला बाउंड max(mid + 1, A[mid])।

सबसे खराब अभी भी ओ(एन) अगर बहुत डुप्लिकेट दोनों शाखाएँ अक्सर खोलें। औसत पर सख्त सरणी में शुद्ध स्कैन से बहुत बेहतर। क्रम अभी भी काम आता है, अनदेखा नहीं।

रिकर्शन बनाम इटेरेशन

अलग-अलग मामला लूप पर साफ़ बैठता है (बाइनरी खोज जैसा)। डुप्लिकेट रिकर्सिव आसान: पहले बायाँ, फिर दायाँ। स्टैक संतुलित बाँट पर ओ(लॉग एन), बदसूरत मामलों में ओ(एन) तक। इंटरव्यू में रिकर्सिव रूप आमतौर पर चल जाता है।

४. जावा समाधान

अलग-अलग पूर्णांक

/**
 * Magic index for a sorted array of distinct ints.
 * Returns some i with A[i] == i, or -1 if none.
 */
public static int magicIndexDistinct(int[] a) {
    if (a == null || a.length == 0) {
        return -1;
    }
    return magicIndexDistinct(a, 0, a.length - 1);
}

private static int magicIndexDistinct(int[] a, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }
    int mid = lo + (hi - lo) / 2;
    int val = a[mid];
    if (val == mid) {
        return mid;
    }
    if (val > mid) {
        // fixed point, if any, is strictly left
        return magicIndexDistinct(a, lo, mid - 1);
    }
    // val < mid: search right
    return magicIndexDistinct(a, mid + 1, hi);
}

इटेरटिव जोड़ी (वही तर्क):

public static int magicIndexDistinctIter(int[] a) {
    if (a == null || a.length == 0) {
        return -1;
    }
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = a[mid];
        if (val == mid) {
            return mid;
        }
        if (val > mid) {
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    return -1;
}

डुप्लिकेट के साथ (सिकुड़ी रेंज)

/**
 * Magic index when the sorted array may contain duplicates.
 * Still returns any match, or -1.
 */
public static int magicIndex(int[] a) {
    if (a == null || a.length == 0) {
        return -1;
    }
    return magicIndex(a, 0, a.length - 1);
}

private static int magicIndex(int[] a, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }
    int mid = lo + (hi - lo) / 2;
    int val = a[mid];
    if (val == mid) {
        return mid;
    }

    // Left: only indices that can still equal their value
    int leftHi = Math.min(mid - 1, val);
    int left = magicIndex(a, lo, leftHi);
    if (left >= 0) {
        return left;
    }

    // Right: skip indices that cannot match
    int rightLo = Math.max(mid + 1, val);
    return magicIndex(a, rightLo, hi);
}

जब इंटरव्यूअर अनोखापन गारंटी दे तो डिस्टिंक्ट तरीका चुनो (साफ़ कहानी, असली ओ(लॉग एन))। जब डुप्लिकेट या "गैर-घटती" कहें तो सामान्य विधि पर जाओ।

५. कदम-दर-कदम चाल

अलग-अलग: `{-1, 0, 1, 3, 5, 7, 9}`

लो	हाई	मिड	ए[मिड]	क्रिया
०	६	३	३	बराबर, ३ लौटाओ

एक वार। भाग्यशाली मिड, पर वही नियम दूसरे शुरू से भी ढूँढते हैं।

अलग-अलग चूक: `{1, 2, 3, 4}`

लो	हाई	मिड	ए[मिड]	क्रिया
०	३	१	२	२ > १, बाएँ
०	०	०	१	१ > ०, बाएँ
०	-१			खाली, `-1`

हर मान अपने इंडेक्स से ऊपर; खोज सही खाली होती है।

डुप्लिकेट: `{-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13}`

मान लो मिड इंडेक्स ५ पर गिरे (A[5] == 3)।

बराबर नहीं।
बायाँ ऊपरी = min(4, 3) = 3। खोज 0..3।
उस रेंज में ७ नहीं भी छुए; बायाँ -1 लौटाए।
दायाँ निचला = max(6, 3) = 6। खोज 6..10।
वहाँ मिड ८ (A[8] == 9 > 8) या ७ (A[7] == 7) हो सकता है। मिड ७ हो तो ७ लौटाओ।

सिकुड़ी सीमाएँ खुद इंडेक्स ५ छोड़ती हैं (पहले जाँचा) और जब val व mid बहुत अलग हों तो कुछ मृत सेल कूद सकती हैं।

कोड में त्वरित जाँच

int[] distinct = {-1, 0, 1, 3, 5, 7, 9};
assert magicIndexDistinct(distinct) == 3;

int[] none = {1, 2, 3, 4};
assert magicIndexDistinct(none) == -1;

int[] dups = {-10, -5, 2, 2, 2, 3, 4, 7, 9, 12, 13};
int m = magicIndex(dups);
assert m >= 0 && dups[m] == m;

assert magicIndex(new int[]{}) == -1;
assert magicIndex(null) == -1;
assert magicIndex(new int[]{0}) == 0;
assert magicIndex(new int[]{1}) == -1;

६. जटिलता, किनारे, इंटरव्यू सुझाव

विषय	अलग-अलग	डुप्लिकेट के साथ
समय	ओ(लॉग एन)	बेहतर ओ(लॉग एन), खराब ओ(एन)
अतिरिक्त जगह	रिकर्शन ओ(लॉग एन) या इटेरटिव ओ(१)	स्टैक ओ(लॉग एन) से ओ(एन)
क्रम ज़रूरी	हाँ	हाँ (गैर-घटती)
ऋणात्मक	ठीक; सिर्फ गैर-ऋणात्मक इंडेक्स मिल सकते हैं	वही

किनारे:

खाली / नल → -1।
एक तत्व {0} → 0; {5} → -1।
सिरों पर मैजिक: इंडेक्स ० या n - 1।
सब ऋणात्मक: कोई मैजिक इंडेक्स नहीं (मान गैर-ऋणात्मक इंडेक्स नहीं पकड़ते)।
एक ही मान v की सपाट सरणी: सिर्फ इंडेक्स v चल सकता है, और तभी जब 0 <= v < n और A[v] == v।

आम बग:

१. इंटरव्यूअर ने डुप्लिकेट दिए बाद भी अलग-अलग वाला एक-तरफ़ा नियम। २. शाखा से पहले A[mid] == mid जाँचना भूलना। ३. lo/hi पर ऑफ-बाय-वन (mid - 1 / mid + 1)। ४. डुप्लिकेट पर पूरा 0..mid-1 और mid+1..n-1 बिना min/max स्किप (सही, बस धीमा; ऑप्टिमाइज़ेशन बताओ)। ५. जब इंडेक्स माँगा हो तब सिर्फ बूलियन लौटाना। ६. स्थिर-चौड़ाई पूर्णांक पर (lo + hi) / 2 ओवरफ़्लो; lo + (hi - lo) / 2 बेहतर।

कैसे बोलो:

१. दोहराओ: "क्रमबद्ध सरणी में i जहाँ A[i] == i।" २. ब्रूट ओ(एन), फिर "क्रमबद्ध + अलग-अलग मतलब एक-तरफ़ा बाइनरी खोज।" ३. एक-एक वाक्य में अलग-अलग + क्रम से तरफ़ त्याग साबित करो। ४. डिस्टिंक्ट संस्करण साफ़ लिखो। ५. फॉलो-अप: "डुप्लिकेट पर दोनों तरफ़ खोजो पर min(mid-1, A[mid]) और max(mid+1, A[mid]) से काटो।"

७. दोस्त को समझाने वाला सार

मैजिक इंडेक्स क्रमबद्ध सरणी में स्थिर बिंदु माँगता है: इंडेक्स मान के बराबर।

१. ब्रूट फोर्स सीधा लूप है। सिर्फ छोटे एन या बिना क्रम पर। २. अलग-अलग + क्रमबद्ध: मिड की A[mid] से तुलना। बहुत ऊँचा तो सिर्फ बायाँ। बहुत नीचा तो सिर्फ दायाँ। अंतर पर बाइनरी खोज। ३. डुप्लिकेट: मिड जाँचो, फिर बाएँ min(mid - 1, A[mid]) तक, फिर दाएँ max(mid + 1, A[mid]) से। क्रम असंभव इंडेक्स बैंड अभी भी मारता है। ४. कोई भी मिलता इंडेक्स लौटाओ, या -1। ऋणात्मक मान वैध इंडेक्स से नहीं मिलते। ५. डिस्टिंक्ट रास्ता ओ(लॉग एन)। डुप्लिकेट रास्ता ओ(एन) तक गिर सकता है; ज़ोर से कहो।

अगर {-1,0,1,3,5,7,9} को इंडेक्स ३ तक चला सको और बता सको डुप्लिकेट को दोनों तरफ़ कटी सीमा क्यों चाहिए, समस्या ८.३ तुम्हारी है। अगला: सेट का हर सबसेट बनाना।