बिल्डिंग से अंडे फेंकने के बारे में Google रिक्रूटर्स की पहेली को कैसे हल करें

प्रोग्रामिंग जॉब इंटरव्यू के लिए कई बेहतरीन पहेलियां हैं। मेरे पसंदीदा को Google भर्तीकर्ताओं में से एक के रूप में भी जाना जाता है:

आप 100 मंजिल की इमारत में काम करते हैं और आपको 2 समान अंडे मिलते हैं। आपको उच्चतम मंजिल का पता लगाने की आवश्यकता है जिसे बिना टूटे एक अंडा गिराया जा सकता है। एक एल्गोरिथ्म ढूंढें जो सबसे खराब स्थिति में फेंकता की संख्या को कम कर रहा है।

हम कुछ अनुमान लगा सकते हैं:

  • यदि किसी मंजिल से गिरा दिया गया तो अंडा नहीं टूटेगा, तो किसी भी निचली मंजिल से गिराए जाने पर यह नहीं टूटेगा।
  • एक अंडा जो गिरने से बच जाता है उसे फिर से इस्तेमाल किया जा सकता है।
  • एक टूटे हुए अंडे को त्याग देना चाहिए।
  • एक गिरावट का प्रभाव सभी अंडों के लिए समान है।
  • अगर गिरा हुआ अंडा टूटता है, तो ऊंची मंजिल से गिरा तो टूट जाएगा।

अधिकांश लोग इस पहेली को हल करने के लिए कुछ एल्गोरिदम लिखते हैं (और हम इसे भी करेंगे), लेकिन वास्तव में एक आसान समाधान है।

सरलतम उत्तर

न्यूनतम मंजिल प्राप्त करने का सबसे सरल तरीका पहली मंजिल से एक अंडा फेंकना है, फिर दूसरी और से। इस तरह जब अंत में अंडा फूट जाएगा तो हमें पता चलेगा कि यह मंजिल है। यह एक विश्वसनीय एल्गोरिथ्म है, लेकिन सबसे खराब स्थिति में यह 100 फेंकता है।

नोटिस करने के लिए महत्वपूर्ण बात यह है कि यह एकमात्र विश्वसनीय एल्गोरिदम है जब आपके पास केवल एक अंडा होता है। तो जब आप पहले अंडे को तोड़ते हैं तो आपको इस एल्गोरिथ्म का उपयोग शुरू करना होगा।

सहज उत्तर

इस तरह, हमारे पहले अंडे को 100 मंजिलों की रेंज को कम से कम कुशलता से विभाजित करने के लिए इस्तेमाल किया जाना चाहिए। इस प्रकार, एक सहज और लोकप्रिय जवाब फर्श की 1 / n-th से पहले अंडे को जांचने के लिए फेंकना है। उदाहरण के लिए 1/3। तब एल्गोरिथ्म निम्नलिखित की तरह दिखेगा:

  • अंडे को 33 वीं मंजिल से फेंक दें। यदि यह टूट जाता है, तो हम दूसरे अंडे का उपयोग करके पहले 32 मंजिलों की जांच करते हैं।
  • अन्यथा, हम अंडे को 33 + (67 * 1/3) = 55 वीं मंजिल से फेंक देते हैं। यदि यह टूट जाता है, तो हम दूसरे अंडे का उपयोग करके फर्श को 34 से 55 तक जांचते हैं।
  • ...

1/3 के लिए सबसे खराब स्थिति अधिकतम (33, 24,…) = 33 है। इस तरह से हमें एक परिपूर्ण n मिल सकता है जो कुछ गतिशील प्रोग्रामिंग का उपयोग करके थ्रो की संख्या का अनुकूलन करता है। यह एक मूल्यवान समाधान है जो प्रोग्रामिंग सोच को प्रस्तुत करता है, लेकिन यह एक इष्टतम समाधान नहीं है।

सही समाधान

सही समाधान को समझने के लिए, हमें उस संतुलन को समझने की आवश्यकता है जिसका उपयोग सबसे खराब स्थिति में फेंकता की संख्या की गणना करने के लिए किया जाता है:

जहां F (n) अगली मंजिल है जहां से हम पहला अंडा फेंकते हैं

यदि हम निम्नलिखित चर का परिचय देते हैं:

तब संतुलन निम्नलिखित है:

इष्टतम समाधान तब होता है जब इस अधिकतम फ़ंक्शन के सभी तर्क समान होते हैं। हम इसे कैसे प्राप्त करेंगे? अंत से देखते हुए, अंतिम डी (एन) 1 होने जा रहा है, क्योंकि हम अंत में उस बिंदु पर पहुंचेंगे जहां पहले अंडे के लिए केवल एक मंजिल है। इसलिए डी (एन -1) 2 के बराबर होना चाहिए क्योंकि इसमें पहले अंडे का एक कम फेंक है।

फिर हम देखते हैं कि पहले अंडे को 99 वीं मंजिल से, अंत में 99-2 = 97 से, पहले 97-3 = 94, 90, 85, 79, 72, 64, 55, 45, 34, 22 और से फेंक दिया जाना चाहिए। 9 वीं मंजिल। यह एक इष्टतम समाधान है! इस तरह, हमें सबसे खराब स्थिति में 14 थ्रो की जरूरत है (सबसे छोटा अंतर 13 है, लेकिन हमें 9 वीं मंजिल पर एक अतिरिक्त फेंकना था)।

उत्तर खोजने के लिए सरल समीकरण निम्न है:

जहां च फर्श की संख्या है। इसे सरल बनाया जा सकता है:

वह इसके बराबर है:

चेक

ठीक है, इसलिए हमारे पास एक समाधान है और हम बिना किसी मदद के इसकी गणना कर सकते हैं। यह जांचने का समय है कि क्या यह सही है। हम इसके लिए एक सरल कोटलिन कार्यक्रम लिखेंगे। सबसे पहले, आइए कुछ निर्णय के लिए फेंकता की संख्या की गणना कैसे करें। जब 2 या उससे कम मंजिलें होती हैं, तो हमें उतने ही थ्रो चाहिए होते हैं जितनी मंजिलें बची हैं। अन्यथा हमें पहले से ही प्रस्तुत संतुलन का उपयोग करना चाहिए:

फन मैक्सहोट्स (फ़्लोरलेफ़्ट: इंट, नेक्स्ट फ़्लोर: इंट): इंट =
  if (फ़र्शलेफ़्ट <= 2) फ़्लोरलैट
  अन्य मैक्सओफ़ (नेक्स्ट फ़्लोर, बेस्टमैक्सट्रो (फ़्लोरलैफ्ट - नेक्स्ट फ़्लोर) + 1)

हमने यहां सबसे अच्छे मैक्त्रोट्स फंक्शन का उपयोग किया है। यह एक काल्पनिक कार्य है जो कई थ्रो को यह कहते हुए लौटाता है कि अगले निर्णय सही हैं। यह हम इसे कैसे परिभाषित कर सकते हैं:

सबसे अच्छा मज़ा मख्खन फेंकता है (फ़्लोरलैट: इंट): इंट =
  maxThrows (फ़्लोरलैट, bestNextStep (फ़्लोरलफ़्ट))

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

वैल बेस्टनेस्टेप (फ़्लोरलेफ़्ट: इंट): इंट =
  if (फ़्लोरलैट <= 2) 1
  और (1. फॉलोअर्सलीफ़)
        ।सूची बनाने के लिए()
        .minBy {maxThrows (फ़्लोरलैट, इट)} !!

ध्यान दें कि यह फ़ंक्शन अधिकतम थ्रेड फ़ंक्शन का उपयोग करता है, इसलिए हम पुनरावृत्ति से निपटते हैं। यह कोई समस्या नहीं है, क्योंकि जब bestNextStep maxThrows को कॉल करता है, तो वह इसे हमेशा छोटे मूल्य के साथ कहता है, फिर floorLeft (क्योंकि nextFloor हमेशा 0 से बड़ा होता है)। इससे पहले कि हम इसका उपयोग करें हम गणना में तेजी लाने के लिए बफरिंग जोड़ देंगे:

वैल बेस्टनेस्टेप: (इंट) -> इंट = मेमोराइज़ {फ़्लोरलैफ्ट ->
  if (फ़्लोरलैट <= 2) 1
  और (1. फॉलोअर्सलीफ़)
        ।सूची बनाने के लिए()
        .minBy {maxThrows (फ़्लोरलैट, इट)} !!
}

फन मैक्सहोट्स (फ़्लोरलेफ़्ट: इंट, नेक्स्ट फ़्लोर: इंट): इंट =
  if (फ़र्शलेफ़्ट <= 2) फ़्लोरलैट
  अन्य मैक्सओफ़ (नेक्स्ट फ़्लोर, बेस्टमैक्सट्रो (फ़्लोरलैफ्ट - नेक्स्ट फ़्लोर) + 1)


वैल बेस्टमैक्सट्रो: (इंट) -> इंट = मेमोराइज़ {फ़्लोरलैफ्ट ->
  maxThrows (फ़्लोरलैट, bestNextStep (फ़्लोरलफ़्ट))
}

मज़ा <वी, टी> याद (एफ: (वी) -> टी): (वी) -> टी {
    वैल मैप = mutableMapOf  ()
    {map.getOrPut (इसे) {f (यह)}} वापस करें
}

पहले, हम जाँच कर सकते हैं कि क्या यह उसी परिणाम देता है जैसा हमने गणना की है:

मज़ा मुख्य (आर्ग्स: ऐरे <स्ट्रिंग>) {
    प्रिंट (bestMaxThrows (100)) // प्रिंट: 14
}

उत्तर अच्छा है :) आइए हमारे अगले चरणों की जाँच करें:

मज़ा मुख्य (आर्ग्स: ऐरे <स्ट्रिंग>) {
    var मंजिल = ०
    जबकि (मंजिल <100) {
        वैल फ़्लोरलैफ्ट = 100 - फ़्लोर
        वैल नेक्स्टस्ट = bestNextStep (फ़्लोरलैफ्ट)
        फर्श + = अगला
        प्रिंट ("$ मंजिल,")
    }
}

परिणाम:

9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,

बस हमने कैसे गणना की! अच्छा: डी

बड़ा चित्र

अब हमारे पास एक अच्छा एल्गोरिथ्म है जिसका उपयोग हम बहुत सी समान समस्याओं के लिए कर सकते हैं। उदाहरण के लिए, हम सबसे अधिक संभावना परिदृश्य के लिए थ्रो की संख्या की गणना करने के लिए इसे थोड़ा बदल सकते हैं। हम यह भी जांच सकते हैं कि भवन की ऊंचाई के आधार पर यह न्यूनतम संख्या में भिन्नता कैसे होगी। यहाँ एक उत्तर दिया गया है कि ग्राफ:

निष्कर्ष

अब आप अपने Google साक्षात्कार के लिए बेहतर तरीके से तैयार हैं, लेकिन यह अधिक महत्वपूर्ण है कि आप अब सामान्य एल्गोरिदमिक सोच के लिए बेहतर तैयार हैं। इस एल्गोरिथ्म ने एक अच्छा, कार्यात्मक दृष्टिकोण प्रस्तुत किया। हमारी दैनिक नौकरियों में विभिन्न समस्याओं के लिए एक समान दृष्टिकोण का उपयोग किया जा सकता है।

मुझे उम्मीद है कि आपको यह पसंद आया होगा। ताली कहने के लिए धन्यवाद और दूसरों को इस लेख को खोजने में मदद करने के लिए। मेरे ट्विटर पर अधिक दिलचस्प सामग्री। मुझे @marcinmoskala का उपयोग करके संदर्भ दें। यदि आप कोटलिन में रुचि रखते हैं, तो कोटलिन गूढ़ व्यक्ति और उन्नत सामग्री के लिए कोटलिन अकादमी और कोटलिन अकादमी पोर्टल देखें।