फ्लिप बिट टू विन: एक पलट के बाद सबसे लंबी एक-श्रृंखला (जावा)

टीएल;डीआर

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

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

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

स्विचों की एक कतार देखो। ज्यादातर चालू हैं। कुछ बंद। तुम ठीक एक बंद स्विच को चालू कर सकते हो। लक्ष्य: लगातार चालू बत्तियों का सबसे लंबा खंड। यही फ्लिप बिट टू विन है: शून्य से एक का एक मुफ़्त बदलाव, फिर एकों की सबसे लंबी दौड़ मापो।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली बिट-दौड़ प्रश्नों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ५, बिट मैनिपुलेशन, समस्या ५.३।

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

पार्किंग की एक लंबी पट्टी सोचो, जगहें एक पंक्ति में। भरी जगह 1 है। खाली 0। तुम्हें एक मुफ़्त भराई मिलती है: एक खाली चुनो और रंग दो।

अगर दो भरे खंड एक अकेली खाली जगह के दोनों तरफ़ हों, उसे भरने से वे एक लंबे खंड में जुड़ जाते हैं। अगर दो खाली लगातार हों, सिर्फ एक भरने से बाहरी भरे खंड नहीं जुड़ते। स्थानीय दौड़ लंबी हो सकती है, पर दो खाली का गैप टूटा रहता है।

काम "सभी एक गिनना" नहीं है। काम है "अपनी एक भराई कहाँ खर्च करनी है, सबसे अच्छा स्थान ढूँढना"।

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

इनपुट: ३२-बिट पूर्णांक n (बिट सोचो; इंटरव्यू में अक्सर तय चौड़ाई का शब्द, प्रायः ३२)।

आउटपुट: अधिकतम एक 0 बिट को 1 में पलटकर बन सकने वाली 1 बिट्स की सबसे लंबी श्रृंखला की लंबाई। (अगर संख्या पहले से सब एक हो, उत्तर पूरे शब्द की चौड़ाई है।)

उदाहरण (बाइनरी में सबसे कम महत्त्व वाला बिट दाईं ओर):

इनपुट का विचार	बाइनरी (निचले बिट)	सबसे अच्छा पलट	परिणाम लंबाई
क्लासिक १७७५	`11011101111`	`111` और `1111` के बीच का शून्य	८
`0b11011`	`11011`	बीच वाला शून्य	५
`0b110011`	`110011`	कोई भी अकेला शून्य	३ (दोनों जोड़े नहीं जुड़ते)
`0`	सब शून्य	कोई भी एक बिट	१
`-1` (दो के पूरक में सब एक)	३२ एक	ज़रूरत नहीं	३२
`0b111`	`111`	दौड़ के ऊपर एक शून्य	४

कोड से पहले साफ़ करो:

शब्द की चौड़ाई? (यहाँ ३२-बिट int। Integer.SIZE इस्तेमाल करो।)
ज़रूरी है पलटना, या "पहले से सर्वोत्तम" चलता है? (अगर पहले से सब एक, ३२ लौटाओ।)
चिह्नित पूर्णांक: स्कैन बिना चिह्न वाले शिफ़्ट >>> से करो, ताकि चिह्न बिट चिपक न जाए।
लंबाई लौटाओ, पलटा हुआ पूर्णांक नहीं (जब तक दोनों न माँगे जाएँ)।

३. पहले सोचो

ब्रूट विचार (बोलो, कोड मत लिखो)

हर उस स्थिति पर जो ० हो, पलटो, एकों की सबसे लंबी दौड़ स्कैन करो, वापस करो। चौड़ाई b (३२ या ६४) पर यह ओ(ब²) है। छोटे b पर ठीक, आदत के रूप में कमज़ोर।

बेहतर विचार: शून्यों से अलग एकों की दौड़ें

बिट्स एक बार चलाओ। रखो:

currentLength: अभी तक जिस बिट पर रुके हो, वहाँ खत्म होने वाली लगातार एकों की गिनती।
previousLength: सबसे हाल के उपयोगी शून्य से ठीक पहले कितने एक थे, जिन्हें पुल की तरह बचाया जा सकता है।
maxLength: अब तक का सबसे अच्छा उत्तर।

जब वर्तमान बिट 1 हो, currentLength बढ़ाओ।

जब वर्तमान बिट 0 हो:

जो एकों की दौड़ अभी खत्म हुई, वह भविष्य के जोड़ का बायाँ पक्ष बन सकती है।
एक बिट आगे देखो। अगर अगला भी 0 है, दो शून्य लगातार: इस शून्य को बाद की एक-दौड़ से जोड़ने का पुल नहीं बना सकते जिसमें बीच में और शून्य हो। previousLength = 0 करो।
अगर अगला 1 है, previousLength = currentLength करो।
currentLength = 0 रीसेट करो।

हर बिट के बाद, सबसे हाल के शून्य को पलट मानकर सबसे अच्छा जोड़:

previousLength + 1 + currentLength

+ 1 वही पलटा शून्य है। maxLength अपडेट करो।

अगर संख्या सब एक है (पूरी चौड़ाई पर ~n == 0), तुरंत शब्द का आकार लौटाओ।

एक बिट आगे देखना क्यों काम करता है

बस इतना जानना है कि अभी छुआ शून्य अकेला विभाजक है या दोहरे गैप की शुरुआत। (n & 2) == 0 का मतलब "अगला बिट भी शून्य" है, जब तक वर्तमान शून्य निचले बिट में है। कोड में शिफ़्ट से पहले, n के वर्तमान मान से जाँचो।

वैकल्पिक मानसिक मॉडल: अनुक्रम सूची

शून्य और एक की दौड़ों की लंबाइयों की सूची बनाओ, उदाहरण:

11011101111  →  एक:२, शून्य:१, एक:३, शून्य:१, एक:४

हर उस शून्य-दौड़ के लिए जिसकी लंबाई १ है, उम्मीदवार = बाएँ एक + १ + दाएँ एक। शून्य-दौड़ १ से लंबी हो तो स्थानीय सबसे अच्छा पलट सिर्फ एक पड़ोसी एक-दौड़ को १ बढ़ाता है। वैश्विक अधिकतम लो। वही उत्तर, ज़्यादा मेमोरी। ओ(१) पिछला/वर्तमान स्कैन इंटरव्यू का डिफ़ॉल्ट है।

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

/**
 * Longest run of 1-bits after flipping at most one 0-bit to 1.
 * Assumes a 32-bit word (Integer.SIZE).
 */
int flipBitToWin(int n) {
    // Already all ones: no flip needed.
    if (~n == 0) {
        return Integer.SIZE;
    }

    int currentLength = 0;
    int previousLength = 0;
    int maxLength = 1; // flipping one zero in a sea of zeros still yields length 1

    while (n != 0) {
        if ((n & 1) == 1) {
            currentLength++;
        } else {
            // Current bit is 0. If the next bit is also 0, no useful left run to keep.
            previousLength = ((n & 2) == 0) ? 0 : currentLength;
            currentLength = 0;
        }
        maxLength = Math.max(previousLength + 1 + currentLength, maxLength);
        n >>>= 1; // logical shift; do not sign-extend
    }

    return maxLength;
}

चलकर देखो: १७७५ (`11011101111`)

लूप जैसे बिट्स निचले से ऊँचे देखता है: 1 1 1 1 0 1 1 1 0 1 1।

बिट	क्रिया	पिछला	वर्तमान	अधिकतम
१	एक++	०	१	२
१	एक++	०	२	३
१	एक++	०	३	४
१	एक++	०	४	५
०	अगला १ → पिछला=४, वर्तमान=०	४	०	५
१	एक++	४	१	६
१	एक++	४	२	७
१	एक++	४	३	८
०	अगला १ → पिछला=३, वर्तमान=०	३	०	८
१	एक++	३	१	८
१	एक++	३	२	८

उत्तर ८: तीन एक और चार एक के बीच का शून्य पलटो।

चलकर देखो: `0b110011` (दोनों जोड़े नहीं जुड़ते)

एक, एक, शून्य, शून्य, एक, एक। पहले शून्य पर अगला भी शून्य, इसलिए previousLength ० हो जाता है। बाद के एक पहले जोड़े से नहीं मिलते। सबसे अच्छी लंबाई ३।

न्यूनतम धुआँ परीक्षण

public static void main(String[] args) {
    System.out.println(flipBitToWin(1775));      // 8
    System.out.println(flipBitToWin(0b11011));   // 5
    System.out.println(flipBitToWin(0b110011));  // 3
    System.out.println(flipBitToWin(0));         // 1
    System.out.println(flipBitToWin(-1));        // 32
    System.out.println(flipBitToWin(0b111));     // 4
}

५. जटिलता तालिका

तरीका	समय	अतिरिक्त स्थान	नोट
हर शून्य पलटो, फिर स्कैन	ओ(ब²)	ओ(१)	ब = शब्द चौड़ाई (३२/६४); सरल पर कमज़ोर
पिछला/वर्तमान एक पास	ओ(ब)	ओ(१)	इंटरव्यू का पसंदीदा उत्तर
दौड़-लंबाई सूची बनाओ	ओ(ब)	ओ(ब)	साफ़ तस्वीर; ज़्यादा आवंटन

३२-बिट int पर ओ(ब) व्यवहार में नियत समय है। फिर भी ज़ोर से ओ(ब) कहो।

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर ये छूते हैं:

सब एक (-1) → Integer.SIZE (३२) लौटाओ। शुरू में विशेष मामला।
सब शून्य (0) → १ लौटाओ (कोई भी बिट पलटो)।
अकेला एक → बगल में शून्य हो तो २; सूत्र previousLength + 1 + currentLength ढकता है।
दो लगातार शून्य → पुराना previousLength मत रखो। (n & 2) == 0 शाखा साफ़ करती है।
ऊँचे सिरे पर एक → n शून्य होते ही लूप रुकता है; ऊँचे शून्य उतने ही काम आते हैं जितना सूत्र एकों को खाते समय पहले ही अंकित कर चुका।
>> के बजाय >>> न लगाना → ऋणात्मक पर चिह्न बिट हमेशा दोहराता है। बिट स्कैन में तार्किक शिफ़्ट ही लगाओ।

आम गलतियाँ:

१. सब-एक का तेज़ रास्ता भूलना। बिना इसके कभी-कभी कोड चल भी जाता है, पर if (~n == 0) से इरादा साफ़। २. maxLength = 0 से शुरू। तब सब-शून्य इनपुट ० देता है। हमेशा एक एक बना सकते हो। ३. हर शून्य पर बिना अगला बिट देखे previousLength = currentLength। दोहरे गैप गलत जुड़ जाते। ४. लंबाई की जगह पलटा संख्या लौटाना। सवाल दोबारा पढ़ो। ५. ३२ अक्षर की स्ट्रिंग बनाकर charAt से स्कैन। चलता है, सोच धीमी, ऑफ-बाय-वन आसान। n पर अंकगणित बेहतर।

७. दोस्त को समझाओ सार

फ्लिप बिट टू विन पूछता है: अधिकतम एक शून्य को एक में पलटो, एकों की सबसे लंबी श्रृंखला कितनी?

१. शब्द पहले से सब एक हो तो उत्तर शब्द की चौड़ाई (३२)। २. तार्किक शिफ़्ट से बिट चलाओ। वर्तमान एक-दौड़ और आखिरी उपयोगी शून्य से पहले की दौड़ रखो। ३. शून्य पर, अगर अगला भी शून्य हो तो बची बाईं दौड़ छोड़ दो। नहीं तो जो दौड़ अभी खत्म हुई उसे बायाँ पक्ष बनाकर बचाओ। ४. हर बिट के बाद उम्मीदवार = बाईं दौड़ + १ (पलट) + अब तक की दाईं दौड़। ५. एक पास, नियत अतिरिक्त मेमोरी, १७७५ का उदाहरण जो ८ बनता है, आसानी से बोर्ड पर।

अगर 11011101111 पर सबसे अच्छा शून्य चिह्नित कर सको और बता सको कि 110011 सिर्फ ३ तक क्यों पहुँचता है, समस्या ५.३ तुम्हारी है।