ज़हर: दस पट्टियों से एक महीने में जहरीली बोतल ढूँढो (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ६.१०: १००० बोतलें, एक जहरीली, १० परीक्षण पट्टियाँ, नतीजा एक महीना लेता है। हर बोतल को बिट पैटर्न दो ताकि एक राउंड घूँट से बोतल का नाम निकल आए।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

तुम्हारे पास १००० सोडा की बोतलें हैं। ठीक एक जहरीली है। तुम्हारे पास १० परीक्षण पट्टियाँ हैं। पट्टी या तो साफ रहती है या जहर चखने के बाद सकारात्मक हो जाती है। हर परीक्षण का नतीजा पढ़ने से पहले पूरा एक महीना लगता है, और तुम्हारे पास सिर्फ एक महीना है। जहरीली बोतल कैसे ढूँढोगे?

पहले तर्क का पहेली, फिर कोड। चाल द्विआधारी है: हर बोतल को एक संख्या मानो, हर पट्टी एक बिट बने। यह पोस्ट शुरुआती लोगों के लिए मूल शिक्षण है, वैकल्पिक जावा के साथ घूँट एनकोड और पट्टी नतीजे डिकोड करने को। इंटरव्यू वाली सूचना-सिद्धांत पहेलियों का परिवार, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ६, गणित और तर्क, यहीं खत्म होता है।

---

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

एक हज़ार सील जूस के डिब्बे सोचो। एक खराब है। दस लिटमस कागज़ हैं और पार्टी से एक रात पहले। हर कागज़ सुबह ही चेक होगा, इसलिए एक ही बैच परीक्षण मिलता है, आगे-पीछे खोज का पेड़ नहीं।

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

हर डिब्बे को द्विआधारी पहचान दो। डिब्बा १३ दस बिट में 0000001101 है। जो बिट 1 है, उस डिब्बे की एक बूँद मेल खाते कागज़ पर। सुबह गंदे कागज़ों का पैटर्न ठीक उसी खराब डिब्बे की द्विआधारी पहचान है। दस कागज़, दस बिट, अधिकतम १०२४ पहचान। तुम्हें १००० ही चाहिए।

---

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

सेटअप:

• १००० बोतलें, लेबल 0 से 999 (या 1 से 1000; एक चुनो और उसी पर रहो)।
• ठीक एक बोतल जहरीली। बाकी सुरक्षित।
• १० परीक्षण पट्टियाँ। हर पट्टी एकमात्र परीक्षण राउंड में कई बोतलों की बूँदों का मिश्रण चख सकती है।
• अगर पट्टी कभी जहर चखे (सुरक्षित तरल के साथ मिला हो तब भी), एक महीने बाद सकारात्मक हो जाती है। वरना नकारात्मक रहती है।
• अभी एक परीक्षण राउंड चलाओ, एक महीना रुको, सभी पट्टियाँ एक साथ पढ़ो।

लक्ष्य: उस एक रीडआउट से जहरीली बोतल का नाम बताओ।

इंटरव्यू में साफ करने वाले अनुमान:

• जहर इतना तेज़ है कि पट्टी पर कोई भी सकारात्मक मात्रा सकारात्मक कर दे (मिश्रण की बारीकियाँ न लें)।
• पट्टियाँ झूठा सकारात्मक या झूठा नकारात्मक नहीं देतीं।
• ठीक एक जहरीली बोतल (न शून्य, न दो)।
• एक पट्टी पर बूँदें मिलाना मना नहीं, मुफ्त है।
• नतीजे देखने के बाद दूसरा राउंड नहीं (समय बजट एक महीना)।

अगर सिमुलेटर लिखो तो सिग्नेचर का आकार:

// bottle ids 0..999; strips 0..9
// returns which bottles strip s should sip
int[] bottlesForStrip(int stripIndex, int bottleCount);

// after one month: positive[s] is true if strip s turned positive
// recover the poisoned bottle id
int decodePoisonedBottle(boolean[] positive);

या पहेली के लिए ज़्यादा ईमानदार:

// given the true poisoned bottle, simulate sips + one month, recover the id
int identifyPoisoned(int truePoisoned, int bottleCount, int stripCount);

छोटा संख्या पूर्वावलोकन (८ बोतलें, ३ पट्टियाँ):

बोतलें 0..7, बिट 0, 1, 2 की पट्टियाँ (बिट ० = सबसे कम महत्व):

बोतल	द्विआधारी	किन पट्टियों पर घूँट
०	०००	कोई नहीं
१	००१	०
२	०१०	१
३	०११	०, १
४	१००	२
५	१०१	०, २
६	११०	१, २
७	१११	०, १, २

अगर बोतल ५ जहरीली है, पट्टियाँ ० और २ सकारात्मक, पट्टी १ साफ। रीडआउट बिट: 101 द्विआधारी = ५।

१० पट्टियों से 2^10 = 1024 पैटर्न मिलते हैं, १००० बोतलों के लिए काफी, थोड़ा अतिरिक्त भी।

---

३. पहले सोचो

क्रमबद्ध या द्विआधारी खोज शैली क्यों फेल

प्रति पट्टी एक बोतल: १० बोतलें ढकीं, ९९० अछूतीं। बेकार।

द्विआधारी खोज: आधी बोतलें पट्टी १ पर, एक महीना रुको, फिर बची आधी की आधी, और आगे। करीब log2(1000) ≈ 10 राउंड, यानी करीब १० महीने। समस्या तुम्हें एक महीने पर बाँधती है।

सूचना बजट

हर पट्टी के २ नतीजे: सकारात्मक या नकारात्मक। दस स्वतंत्र पट्टियाँ 2^10 = 1024 संभावित पैटर्न देती हैं। १००० संभावनाएँ अलग करनी हैं (कौन सी बोतल खराब)। १०२४ ≥ १०००, इसलिए सिद्धांत में एक राउंड काफी है। सवाल है बोतलों को पैटर्न से कैसे जोड़ना।

बोतल सूचकांक को पट्टी पैटर्न में एनकोड करो

बोतलें 0 से 999 तक नंबर दो। हर सूचकांक को अधिकतम १० बिट द्विआधारी में लिखो:

bottle b -> bits b0 b1 ... b9
  where bi = 1 if (b & (1 << i)) != 0

एनकोड (आज क्या करोगे):

• हर पट्टी i के लिए 0..9 में:
  • पट्टी i हर उस बोतल b से एक बूँद लेती है जहाँ b का बिट i सेट है।

डिकोड (एक महीने बाद क्या करोगे):

• result = 0 लो।
• हर पट्टी i पर, अगर पट्टी i सकारात्मक है तो result में बिट i सेट करो: result |= (1 << i)।
• result ही जहरीली बोतल का सूचकांक है।

क्यों चलता है: सिर्फ जहरीली बोतल जहर देती है। पट्टी i सकारात्मक होती है तब और सिर्फ तब जब जहरीली बोतल का बिट i सेट हो। पट्टियों के नतीजों का सदिश ठीक उसी बोतल का द्विआधारी रूप है।

लेबल १..१००० बनाम ०..९९९

दोनों चलते हैं।

• ०..९९९: पैटर्न खुद संख्याएँ हैं। बोतल ० कहीं नहीं चखती। अगर सब पट्टियाँ नकारात्मक रहें, बोतल ० जहरीली है (तभी जब बोतल ० मान्य हो)।
• १..१०००: लेबल का द्विआधारी लो, या label - 1 का। साफ बोलो। 2^10 = 1024 अभी भी १..१००० ढकता है।

इंटरव्यूअर को बिट मैप गढ़ना चाहिए, "० से शुरू करो" रटना नहीं।

लोग जो रूप लाते हैं

• कई जहरीली बोतलें: एक पैटर्न टकरा सकता है। और पट्टियाँ या दूसरा कोड चाहिए (त्रुटि सुधार / समूह परीक्षण)।
• समय में कई राउंड पर दोबारा इस्तेमाल पट्टियाँ: अलग समस्या; समय के साथ ज्यादा जानकारी।
• सिर्फ k पट्टियाँ, n बोतलें: एक राउंड के लिए 2^k >= n चाहिए, या समय हो तो और राउंड।
• झूठा सकारात्मक: तब अतिरिक्त कोडिंग। क्लासिक ६.१० के बाहर।

---

४. जावा समाधान (सिमुलेशन)

पहेली तर्क से सुलझती है। कोड दिखाता है कि बिट सूचकांक पर ऑफ-बाय-वन के बिना एनकोड-डिकोड लिख सकते हो।

पट्टी नतीजों को बोतल पहचान में डिकोड

/**
 * positive[i] == true means strip i turned positive after one month.
 * Returns bottle id in 0 .. (2^strips - 1).
 */
static int decodePoisonedBottle(boolean[] positive) {
    int id = 0;
    for (int i = 0; i < positive.length; i++) {
        if (positive[i]) {
            id |= (1 << i);
        }
    }
    return id;
}

पट्टी i किन बोतलों से घूँट लेती है?

/**
 * Bottles are 0 .. bottleCount-1.
 * Strip i sips every bottle whose bit i is set.
 */
static boolean stripSipsBottle(int stripIndex, int bottleId) {
    return ((bottleId >> stripIndex) & 1) == 1;
}

एक सच्ची जहरीली बोतल का सिमुलेशन

/**
 * bottleCount typically 1000, stripCount typically 10.
 * truePoisoned is 0-based in [0, bottleCount).
 */
static int identifyPoisoned(int truePoisoned, int bottleCount, int stripCount) {
    if (truePoisoned < 0 || truePoisoned >= bottleCount) {
        throw new IllegalArgumentException("truePoisoned out of range");
    }
    if ((1 << stripCount) < bottleCount) {
        throw new IllegalArgumentException("not enough strips for one round");
    }

    boolean[] positive = new boolean[stripCount];
    for (int strip = 0; strip < stripCount; strip++) {
        // strip turns positive iff the poisoned bottle has this bit set
        // (equivalent to mixing all bottles with that bit and waiting)
        positive[strip] = stripSipsBottle(strip, truePoisoned);
    }
    int found = decodePoisonedBottle(positive);
    if (found >= bottleCount) {
        throw new IllegalStateException("decoded id outside bottle range: " + found);
    }
    return found;
}

ऊपर वाला लूप गणितीय शॉर्टकट है: अगर पहले से पता है कौन जहरीली है तो हर बोतल घूमने की ज़रूरत नहीं। "असली लैब" संस्करण में हर पट्टी का मिश्रण सभी मेल खाती बोतलों से बनाओगे, और सिर्फ सच्चा जहर उन्हीं पट्टियों को उसी तरह पलटेगा।

साफ मिश्रण निर्माण (सिखाने के लिए स्पष्ट)

static int identifyPoisonedByMixing(int truePoisoned, int bottleCount, int stripCount) {
    boolean[] positive = new boolean[stripCount];
    for (int strip = 0; strip < stripCount; strip++) {
        boolean gotPoison = false;
        for (int bottle = 0; bottle < bottleCount; bottle++) {
            if (!stripSipsBottle(strip, bottle)) {
                continue;
            }
            // drop from this bottle goes on the strip
            if (bottle == truePoisoned) {
                gotPoison = true;
            }
        }
        positive[strip] = gotPoison;
    }
    return decodePoisonedBottle(positive);
}

सभी १००० मामलों की जाँच

static void verifyAll() {
    int bottles = 1000;
    int strips = 10;
    for (int p = 0; p < bottles; p++) {
        int a = identifyPoisoned(p, bottles, strips);
        int b = identifyPoisonedByMixing(p, bottles, strips);
        if (a != p || b != p) {
            throw new AssertionError("failed for bottle " + p);
        }
    }
    System.out.println("ok: all " + bottles + " bottles identified");
}

गिने-चुने आँकड़े

बोतल ३२६ जहरीली, १० पट्टियाँ, ० से शुरू पहचान:

326 in binary (bits 0 = LSB on the right when written normally):
  326 = 256 + 64 + 4 + 2
      = 2^8 + 2^6 + 2^2 + 2^1
  bits set: 1, 2, 6, 8

Strips that go positive: 1, 2, 6, 8
decode: (1<<1) | (1<<2) | (1<<6) | (1<<8) = 2 + 4 + 64 + 256 = 326

छोटा ३-पट्टी मामला, बोतल ५:

positive = [true, false, true]  // strips 0 and 2
id = 1 | 4 = 5

वैकल्पिक: एक पट्टी की बोतल सूची (तैयारी का दिन)

static java.util.List<Integer> bottlesForStrip(int stripIndex, int bottleCount) {
    java.util.ArrayList<Integer> list = new java.util.ArrayList<>();
    for (int b = 0; b < bottleCount; b++) {
        if (stripSipsBottle(stripIndex, b)) {
            list.add(b);
        }
    }
    return list;
}

पट्टी ० हर विषम बोतल चखती है। पट्टी ९ उन बोतलों को चखती है जिन पर 2^9 = 512 बिट सेट है (पूरे १०-बिट स्थान में ५१२..१०२३; १००० से कम ही मायने रखते हैं)।

---

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

तरीका	परीक्षण राउंड	पट्टियाँ	नोट
प्रति पट्टी एक बोतल	१	१०	सिर्फ १० बोतलें ढकीं
द्विआधारी खोज समूह	~१०	१+	अगले कट से पहले नतीजा चाहिए; ~१० महीने
बिट द्वारा द्विआधारी एनकोड	१	१०	अधिकतम १०२४ बोतलें
बिना योजना के बेतरतीब मिश्रण	१	१०	अक्सर टकराव या छेद

कोड में लंबे रास्ते सब मिश्रण बनाना O(bottles * strips) है। डिकोड O(strips)। इंटरव्यू में दिलचस्प लागत इंतज़ार के राउंड = १ है, सीपीयू का बड़ा-ओ नहीं।

---

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

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

• बोतल ० जहरीली (०-आधार): सब पट्टियाँ नकारात्मक। वैध कोडवर्ड है। अगर लेबल १ से शुरू हों तो बोलो, और "सब नकारात्मक = कोई जहर नहीं" मत कहो जब तक समस्या शून्य जहर न माने।
• बोतल ९९९: ९९९ के बिट १० बिट में समाते हैं (999 < 1024)। ठीक।
• १-आधार लेबल पर बोतल १०००: फिर भी ठीक; १००० १०२४ से कम ही है।
• कम पट्टियाँ: ९ पट्टियाँ सिर्फ ५१२ बोतलें ढकती हैं। 2^k >= n जाँच बताओ।
• एमएसबी बनाम एलएसबी पट्टी नंबर: पट्टी i = बिट i चुनो और एनकोड-डिकोड में एक सा रहो।
• नतीजों के बाद दोबारा परीक्षण: समय सीमा से मना। फॉलो-अप न माँगे तो बहु-राउंड एल्गोरिदम मत बयान करो।
• दो जहरीली बोतलें: दो पैटर्न का OR तीसरी बोतल जैसा दिख सकता है। क्लासिक ठीक एक मानता है।
• पट्टी क्षमता / बूँद गिनती: जब तक इंटरव्यूअर बाधा न डाले, अनदेखा।

आम गलतियाँ:

१. द्विआधारी खोज बयान करना और हर परीक्षण पर एक महीने का ताला भूलना। २. पट्टियों को "१०० के समूह" मानना बिना हर बोतल की अनोखी पहचान। ३. लेबल पर ऑफ-बाय-वन (० बनाम १) जिससे डिकोड एक खिसक जाए। ४. बिट सूचकांक और पट्टी सूचकांक मिलाना (एनकोड में बिट ० पट्टी ० पर, डिकोड में बिट ० पट्टी ९ पर)। ५. कहना कि १००० पट्टियाँ चाहिए या प्रति बोतल एक पट्टी। ६. भूलना कि बोतल ० कहीं नहीं चखती और सब साफ होने पर घबराना।

न्यूनतम धुआँ जाँच:

verifyAll();
System.out.println(identifyPoisoned(0, 1000, 10));   // 0
System.out.println(identifyPoisoned(5, 1000, 10));   // 5
System.out.println(identifyPoisoned(326, 1000, 10)); // 326
System.out.println(identifyPoisoned(999, 1000, 10)); // 999
System.out.println(bottlesForStrip(0, 8)); // odds: 1,3,5,7

---

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

एक हज़ार बोतलें, एक जहरीली, दस पट्टियाँ, एक महीना।

१. सिर्फ एक परीक्षण राउंड मिलता है। कैलेंडर समय में द्विआधारी खोज बहुत धीमी। २. दस पट्टियाँ 2^10 = 1024 नतीजा पैटर्न देती हैं। १००० में से किसी भी बोतल का नाम काफी है। ३. बोतलें 0..999 नंबर करो। हर संख्या द्विआधारी में लिखो। ४. पट्टी i हर उस बोतल से घूँट लेती है जिसका बिट i 1 है। ५. एक महीने बाद सकारात्मक पट्टियाँ एक द्विआधारी संख्या बनाती हैं। वही संख्या जहरीली बोतल है। ६. कोड में एनकोड (bottle >> i) & 1, डिकोड हर सकारात्मक पट्टी पर id |= (1 << i)।

बिना कोड लिखे अगर बता सको कि पट्टी सदिश बोतल पहचान क्यों है, तो समस्या ६.१० तुम्हारी है। अध्याय ६ शुद्ध सूचना डिज़ाइन पर बंद होता है: एक बार मापो, बिट पैटर्न पढ़ो, चल दो।

---

श्रृंखला

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: १०० लॉकर्स
• अगला: डेक ऑफ कार्ड्स