दो पत्थर और एक 100 कहानी इमारत

उन क्लासिक प्रोग्रामिंग साक्षात्कार प्रश्नों में से एक ...

आपको दो पत्थर दिए जाते हैं, और कहा जाता है कि कुछ निश्चित ऊंचाई से गिराए जाने पर वे टूट जाएंगे (और उस ऊंचाई से नीचे गिरने पर संभावित रूप से कोई नुकसान नहीं होता है)। फिर आप 100 स्टोरी बिल्डिंग (निश्चित रूप से निश्चित ऊंचाई से अधिक) तक ले गए, और उच्चतम मंजिल को खोजने के लिए कहा, जिससे आप एक संगमरमर को जितना संभव हो उतना कुशलता से तोड़ने से रोक सकते हैं।

अधिक जानकारी

  • आपको सही मंजिल (संभव सीमा नहीं) मिलनी चाहिए
  • पत्थर दोनों एक ही मंजिल पर तोड़ने की गारंटी रखते हैं
  • मान लीजिए कि आपके लिए फर्श बदलने के लिए शून्य समय लगता है - केवल संगमरमर की बूंदों की संख्या गिना जाता है
  • मान लें कि सही मंजिल इमारत में यादृच्छिक रूप से वितरित की जाती है
0
ro fr bn
आपको मंजिल को कुशलतापूर्वक खोजने के लिए एक एल्गोरिदम की आवश्यकता है (जो आपको अपने दृष्टिकोण के लिए आवश्यक अधिकतम बूंदों और इसे कैसे करने के लिए चरणों का एक सेट) का नेतृत्व करना चाहिए।
जोड़ा लेखक Matt Sheppard, स्रोत
@ ब्रैड विल्सन: यह पूरी तरह साक्षात्कार पर निर्भर करता है ... तार्किक सोच और गणित सुलझाने के कौशल की जांच करना एक अच्छा सवाल है।
जोड़ा लेखक Karoly Horvath, स्रोत
यह संभवतः बेहतर नहीं है कि सही मंजिल को यादृच्छिक रूप से वितरित किया जाए, और इसके बजाय बस सबसे खराब मामले को कम करने के लिए एक समाधान के साथ आना।
जोड़ा लेखक Dave L., स्रोत
यह एक बहुत बड़ा "आह!" है किसी ऐसे व्यक्ति के लिए कारक जिसने गणित का अध्ययन नहीं किया है। "आह!" के साथ प्रश्न साक्षात्कार के लिए कारक असाधारण रूप से खराब हैं।
जोड़ा लेखक Brad Wilson, स्रोत
प्रश्न शीर्षक स्पष्ट रूप से स्पष्ट नहीं है: क्या हमें अधिकतम मंजिल को खोजने की ज़रूरत है जिससे हम संगमरमर को तोड़ सकते हैं या इसे तोड़ सकते हैं, जैसा कि उत्तर से पता चलता है, उस मंजिल पर आने की कोशिशों की न्यूनतम संख्या ...? !
जोड़ा लेखक KeyBrd Basher, स्रोत

9 उत्तर

मैं व्यक्तिगत रूप से ऐसे पहेली सवालों के प्रशंसक नहीं हूं, मैं साक्षात्कार में वास्तविक प्रोग्रामिंग अभ्यास पसंद करता हूं।

उस ने कहा, सबसे पहले यह इस बात पर निर्भर करेगा कि क्या मैं बता सकता हूं कि क्या वे टूट गए हैं या नहीं, मैं उन्हें छोड़ रहा हूं। मुझे लगता है कि मैं कर सकता हूँ।

मैं दूसरी मंजिल तक जाऊंगा, पहला संगमरमर छोड़ दूंगा। अगर यह टूट गया तो मैं पहली मंजिल की कोशिश करूंगा। अगर वह टूट गया तो मुझे पता चलेगा कि यह कोई मंजिल नहीं था।

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

यदि न तो तोड़ दिया, तो मैं दोनों को मिल जाएगा, और एक ही प्रक्रिया करूँगा, इस बार 6 वीं मंजिल से शुरू होगा।

इस तरह, मैं हर दूसरी मंजिल को तब तक छोड़ सकता हूं जब तक कि मुझे एक संगमरमर नहीं मिल जाता है।

अगर यह संगमरमर टूट जाता है तो यह अनुकूलित किया जाएगा ... मुझे लगता है कि शायद प्रत्येक छत के लिए सबसे अधिक पाने के लिए मैं फर्श की इष्टतम मात्रा रख सकता हूं ... लेकिन फिर यदि कोई टूट जाता है, तो मुझे प्रत्येक मंजिल को अलग-अलग जांचना होगा अंतिम ज्ञात मंजिल के ऊपर पहली मंजिल से ... निश्चित रूप से दर्द होगा यदि मैंने बहुत सारे फर्श छोड़े हैं (क्षमा करें, अभी इष्टतम समाधान को समझने के लिए नहीं जा रहे हैं)।

आदर्श रूप से, मैं पत्थर का पूरा बैग चाहता हूं, फिर मैं एक बाइनरी खोज एल्गोरिदम का उपयोग कर सकता हूं और प्रत्येक बूंद के साथ आधे में फर्श की संख्या विभाजित कर सकता हूं ... लेकिन फिर, यह सवाल नहीं था, है ना?

0
जोड़ा
कभी ब्रूट फोर्स दृष्टिकोण माइक ........ के बारे में सुना
जोड़ा लेखक KeyBrd Basher, स्रोत

वे एक ही ऊंचाई से गिराए जाने पर प्रत्येक तोड़ते हैं, या वे अलग हैं?

यदि वे वही हैं, तो मैं 50 वीं मंजिल पर जाता हूं और पहला संगमरमर छोड़ देता हूं। यदि यह तोड़ता नहीं है, तो मैं 75 वीं मंजिल पर जाता हूं और वही करता हूं, जब तक यह टूटना नहीं रहता है, तब तक मैं 50% तक छोड़ता रहता हूं। जब यह टूट जाता है, तो मैं पहले की तुलना में एक उच्च स्तर पर वापस जाता हूं (इसलिए यदि यह 75 वीं मंजिल पर टूट गया तो मैं 51 वीं मंजिल पर वापस जाता हूं) और दूसरा संगमरमर छोड़ देता हूं और एक बार फर्श तक टूट जाता है, जिस बिंदु पर मैं उच्चतम मंजिल को जानता हूं जिसे मैं बिना संगमरमर के टूटने से छोड़ सकता हूं।

शायद सबसे अच्छा जवाब नहीं है, मैं यह देखने के लिए उत्सुक हूं कि दूसरों का जवाब कैसे दिया जाता है।

0
जोड़ा

तीसरी मंजिल से पहला संगमरमर ड्रॉप करें। यदि यह टूट जाता है, तो आप जानते हैं कि यह मंजिल 1 या 2 है, इसलिए अन्य संगमरमर को फर्श 2 से छोड़ दें। यदि यह तोड़ता नहीं है तो आपको पता चला है कि फर्श 2 उच्चतम है। यदि यह टूट जाता है, तो आप पाएंगे कि मंजिल 1 सबसे अधिक है। 2 बूंदें

यदि तीसरी मंजिल से गिरना संगमरमर को तोड़ता नहीं है, तो फर्श 6 से गिरें। यदि यह टूट जाता है, तो आप जानते हैं कि फर्श 4 या 5 उच्चतम है। दूसरे संगमरमर को फर्श से 5 छोड़ दें। यदि यह तोड़ता नहीं है तो आपको पता चला है कि 5 सबसे ज्यादा है। यदि ऐसा होता है, तो फर्श 4 उच्चतम है। 4 बूंदें

जारी रहना।

3 मंजिल - अधिकतम 2 बूंदें

6 मंजिलें - अधिकतम 4 बूंदें

9 मंजिल - अधिकतम 6 बूंदें

12 मंजिलें - अधिकतम 8 बूंदें

आदि।

3 एक्स फर्श - अधिकतम 2x बूंदें

तो 99 मंजिल के निर्माण के लिए आपके पास अधिकतम 66 बूंदें होंगी। और वह अधिकतम है। आप की तुलना में कम बूंदों की संभावना है। ओह, और 66 एक 100 कहानी इमारत के लिए भी अधिकतम है। यदि ब्रेक फ्लोर मंजिल 98 या 9 7 था तो आपको केवल 66 बूंदों की आवश्यकता होगी। यदि ब्रेक फ्लोर 100 थी तो आप 34 बूंदों का उपयोग करेंगे।

भले ही आपने कहा कि इससे कोई फर्क नहीं पड़ता है, इसके लिए शायद कम से कम चलने की आवश्यकता होगी और आपको यह नहीं पता कि इमारत कितनी अधिक है।

Part of the problem is how you define efficiency. Is it more "efficient" to always have a solution in less than x drops, or is it it more efficient to have a good chance at having a solution in y drops where y < x with the caveat that you could have more than x drops?

0
जोड़ा

पहले संगमरमर को फर्श 10, 20, 30, आदि पर छोड़ दें जब तक कि यह टूट न जाए, फिर अंतिम ज्ञात अच्छा मंजिल पर वापस जाएं और एक समय में एक मंजिल से पत्थर छोड़ना शुरू करें। सबसे खराब मामला 99 जादू का तल है और आप इसे हमेशा 1 9 बूंदों या उससे कम में ढूंढ सकते हैं।

0
जोड़ा

यह समस्या पुस्तक से समस्या 6.5 में शामिल है " कोडिंग साक्षात्कार को क्रैक करना (5 वां) " , निम्नानुसार संक्षेप में समाधान के साथ:

निरीक्षण:

भले ही हम मार्बल 1 को कैसे छोड़ें, मार्बल 2 को रैखिक खोज करना चाहिए। उदाहरण के लिए, अगर मार्बल 1 फर्श 10 और 15 के बीच ब्रेक, हमें मार्बल 2 के बीच में प्रत्येक मंजिल की जांच करनी है


पहुंच:

A First Try: Suppose we drop an Marble from the 10th floor, then the 20th, ?

  • पहले ड्रॉप (फ़्लोर 10) पर पहले मार्बल ब्रेक में, तो हमारे पास कुल 10 बूंदें हैं।
  • यदि पहली संगमरमर आखिरी बूंद (तल 100) पर टूट जाती है, तो हमारे पास कुल 19 बूंदें हैं (फर्श 1 से 100, फिर 91 से 99)।
  • यह बहुत अच्छा है, लेकिन हम सभी के बारे में माना जाता है कि यह सबसे खराब मामला है। हमें कुछ करो? भार संतुलन? उन दो मामलों को और भी बनाने के लिए।

Goal: Create a system for dropping Marble1 so that the most drops required is consistent, whether Marble1 breaks on the first drop or the last drop.

  1. A perfectly load balanced system would be one in which Drops of Marble1 + Drops of Marble2 is always the same, regardless of where Marble1 broke.
  2. For that to be the case, since each drop of Marble1 takes one more step, Marble2 is allowed one fewer step.
  3. We must, therefore, reduce the number of steps potentially required by Marble2 by one drop each time. For example, if Marble1 is dropped on Floor 20 and then Floor 30, Marble2 is potentially required to take 9 steps. When we drop Marble1 again, we must reduce potential Marble2 steps to only 8. eg, we must drop Marble1 at floor 39.
  4. We know, therefore, Marble1 must start at Floor X, then go up by X-1 floors, then X-2, ?, until it gets to 100.
  5. Solve for X+(X-1)+(X-2)+?+1 = 100. X(X+1)/2 = 100 -> X = 14

हम तल 14 पर जाते हैं, फिर 27, फिर 39,? इसमें अधिकतम 14 कदम लगते हैं।


Code & Extension:

0
जोड़ा
क्या आप ऊपर चरण 5 में समीकरण के पीछे तर्क पर टिप्पणी कर सकते हैं?
जोड़ा लेखक Geek, स्रोत
@ गीक आपको केवल घटिया श्रेणियों के साथ सभी 100 रेंज को कवर करने की आवश्यकता है। हम इसे संतुलित बनाना चाहते थे ताकि कूदें फर्श में हों: 14, 27,39, 50, 60, 69, 77, 84, 9 0, 95. हर बार एक मंजिल कम हो जाता है। इस तरह अगर हम पहले 10 बार छोड़ देते हैं तो हमें केवल 4 बूंदों की आवश्यकता होती है। 10 +4 = 14 जैसे कि यह पहली मंजिल में टूट जाता है।
जोड़ा लेखक borjab, स्रोत
@Dinaiz Totaldrops = Marble1Drops + Marble2Drops। यदि आप कुल ड्रेप्स का मूल्य वही (सबसे खराब मामला) रखना चाहते हैं, तो मार्बल 1 ड्रॉप्स बढ़ता है, मार्बल 2 ड्रॉप्स को कम करना पड़ता है। जैसे कुल ड्रॉप्स = 10. मान लें। यदि मार्बल 1 ड्रॉप्स = 1 तो मार्बल 2 ड्रॉप्स = 9। यदि मार्बल 1 ड्रॉप्स = 2, तो मार्बल 2 ड्रॉप्स = 8 और इसी तरह।
जोड़ा लेखक Davos, स्रोत
@ गीक आप सबसे खराब x = 100 मानते हुए शुरू कर सकते हैं, यानी आप 100 बूंदें करने जा रहे हैं। यह 100 से भी बदतर नहीं हो सकता है, क्योंकि परीक्षण के लिए केवल 100 मंजिल हैं। अगला कदम आधे में जगह को आजमाने और विभाजित करना है। यानी लगभग आधा रास्ता छोड़ दें। तो यह 2x = 100 जैसा है, लेकिन काफी नहीं है। यह वास्तव में x + (x-1) = 100 है, दूसरा खंड x-1 है क्योंकि फर्श दो सेगमेंट हैं जिन्हें नीचे-नीचे परीक्षण किया जाएगा। यदि संगमरमर पहले सेगमेंट के लिए अखंड है, तो आपने 1 ड्रॉप का उपयोग किया है, इसलिए ऊपरी सेगमेंट के लिए एक कम है। अधिक सेगमेंट, अधिक बूंदों का इस्
जोड़ा लेखक Davos, स्रोत
"इसके लिए मामला होना, क्योंकि मार्बल 1 की प्रत्येक बूंद एक और कदम उठाती है, मार्बल 2 को एक कम कदम की अनुमति है।" । मैं इस हिस्से को समझ नहीं पा रहा हूं। क्या आप कृपया समझा सकते हैं?
जोड़ा लेखक Dinaiz, स्रोत

सबसे पहले मैं जो करता हूं वह मृत साधारण एल्गोरिदम का उपयोग करता है जो फर्श 1 से शुरू होता है जब तक यह 100 या संगमरमर के ब्रेक तक पहुंचने तक संगमरमर एक मंजिल को छोड़ देता है।

तब मैं पूछूंगा कि मुझे इसे अनुकूलित करने में समय क्यों व्यतीत करना चाहिए जब तक कोई यह दिखा न सके कि यह एक समस्या होगी। जब लोग एक बहुत ही सरल समस्या को हल करेंगे तो कई बार लोग जटिल जटिल एल्गोरिदम खोजने पर लटकाएंगे। दूसरे शब्दों में जब तक इसकी आवश्यकता न हो, चीजों को अनुकूलित न करें।

यह देखने के लिए यह मुश्किल सवाल हो सकता है कि क्या आप उन लोगों में से एक हैं जो एक तिल पहाड़ी से पहाड़ बना सकते हैं।

0
जोड़ा
यहां तक ​​कि यदि आप एक मृत साधारण एल्गोरिदम का उपयोग करना चाहते हैं, तो कम से कम प्रश्न में दी गई सभी जानकारी का उपयोग करें। आपके पास 2 पत्थर हैं लेकिन अभी भी केवल 1 का उपयोग कर रहे हैं। अन्य संगमरमर को बैठने और रोने दो "मैं इस दुनिया में एक अंतर लाने आया हूं और आप मेरा अस्तित्व बर्बाद कर रहे हैं :("
जोड़ा लेखक Vikram Singh, स्रोत

The interesting thing here is how you can do it in the least amount of drops possible. Going to the 50th floor and dropping the first would be disastrous if the breaking floor is the 49th, resulting in us having to do 50 drops. We should drop the first marble at floor n, where n is the max amount of drops required. If the marble breaks at floor n, we may have to make n-1 drops after that. If the marble doesn't break we go up to floor 2n-1 and if it breaks here we have to drop the second marble n-2 times in the worst case. We continue like this up to the 100th floor and try to break it at 3n-2, 4n-3....
and n+(n-1)+(n-2)+...1 <=100
n=14 Is the maximum drops required

0
जोड़ा
क्या आप समीकरण n + (n-1) + (n-2) + ... 1 <= 100 के कारण के बारे में बता सकते हैं?
जोड़ा लेखक Geek, स्रोत
@ गीक ने कहा कि एन सबसे खराब परिणाम है। तो आप कोशिश करते हैं और उस सबसे खराब मामले को कई सेगमेंट के लिए सबसे खराब बनाते हैं। परीक्षण किए गए प्रत्येक सेगमेंट के लिए अधिकतम सबसे खराब केस बनाए रखने के लिए, आपको परीक्षण किए गए प्रत्येक सेगमेंट के लिए 1 कम ड्रॉप का उपयोग करना होगा। एन के उस मान पर पहले सेगमेंट का परीक्षण करें, यदि यह आपको तोड़ देता है तो 1 से लेकर एन -1 तक परीक्षण करें। तो आपकी अंतिम अधिकतम बूंद 1 + (एन -1) = एन है। अगर यह एन पर नहीं टूट गया, लेकिन 2 एन पर, तो आप पहले से ही 1 बूंद पर एन कर चुके हैं, इसलिए एन बूंदों के सबसे बुरे मामले में चिपकने के लिए, आपको केवल एन -1 शेष मिला है।
जोड़ा लेखक Davos, स्रोत
तार्किक रूप से संगमरमर जितना ऊंचा हो उतना कठिन जमीन पर हिट करता है, इसलिए आप कम शुरू करते हैं और अपना रास्ता बनाते हैं। तो सेगमेंट कम शुरू हो जाते हैं और साथ ही साथ जाते हैं। आपके द्वारा परीक्षण किए जाने वाले अधिक सेगमेंट, कम बूँदें शेष हैं, इसलिए उच्च सेगमेंट छोटे और छोटे होने के लिए मजबूर होते हैं। निचला खंड सबसे बड़ा है, एन के बराबर है। प्रत्येक चरण एक कम है, क्योंकि आप अपना रास्ता काम कर रहे हैं।
जोड़ा लेखक Davos, स्रोत
लक्ष्य तो कम करने के लिए है। आप इनमें से प्रत्येक के परिणामों को चार्ट करके मैन्युअल रूप से चला सकते हैं: n = 100 , n + (n-1) = 100 , n + (n-1 ) + (एन -2) = 100 </कोड>, <�कोड> एन + (एन -1) + (एन -2) + (एन -3) = 100 </कोड> इत्यादि। उन समीकरणों में से प्रत्येक का पुनर्व्यवस्थित करें n = 100 , n = 101/2 , n = 103/3 , n = 106/4 । आगे बढ़ते रहें, एन का मान कम हो जाएगा, जब तक कि यह न्यूनतम तक न पहुंच जाए, और तब उसके बाद उच्च हो जाएगा। वह न्यूनतम समाधान इष्टतम है। समाधान 13.64 है, लेकिन 13.64 मंजिल नहीं है, इसल
जोड़ा लेखक Davos, स्रोत
मैं उस पहली टिप्पणी को संपादित नहीं कर सकता। यह हिस्सा गलत है: "अगर यह एन पर नहीं टूट गया, लेकिन 2 एन पर"। क्षमा करें 2 एन सही नहीं है, यह होना चाहिए "लेकिन एन + (एन -1)"
जोड़ा लेखक Davos, स्रोत

मुझे लगता है कि असली प्रश्न यह है कि आप उत्तर को कितना सटीक चाहते हैं। क्योंकि आपकी दक्षता वास्तव में उस पर निर्भर होने जा रही है।

मैं जस्टिन से सहमत होने जा रहा हूं यदि आप पत्थरों पर 100% सटीकता चाहते हैं तो एक बार जब पहली संगमरमर टूट जाती है तो आपको अंतिम ज्ञात "अच्छी" मंजिल से एक समय में 1 मंजिल तक जाना होगा जब तक आप यह पता न लें कि कौन सी मंजिल है विजेता।" हो सकता है कि कुछ आंकड़ों में भी फेंक दें और 50 वीं मंजिल की जगह 25 वीं मंजिल पर शुरू करें ताकि आप सबसे खराब स्थिति परिदृश्य 49 के बजाय 24 हों।

यदि आप उत्तर दे रहे हैं तो एक या दो मंजिल या कम हो सकता है तो कुछ अनुकूलन हो सकते हैं।

दूसरा, सीढ़ियों को ऊपर या नीचे अपनी दक्षता के खिलाफ गिनती है? उस मामले में हमेशा दोनों पत्थरों को छोड़ दें और प्रत्येक ऊपर / नीचे यात्रा पर दोनों पत्थर उठाएं।

0
जोड़ा

यह सिर्फ 7 पत्थरों के साथ बेहतर किया जा सकता है।

तो मतदान के जवाब के बाद, कम से कम 49 वीं मंजिल पर संगमरमर तोड़ें।

  1. 50th floor -> breaks (answer is between 1 to 50 inclusive)
  2. 25th floor -> doesn't break (26 to 50)
  3. 37th floor -> doesn't break (38 to 50)
  4. 43rd floor -> doesn't break (44 to 50)
  5. 46th floor -> doesn't break (47 to 50)
  6. 48th floor -> doesn't break (49 or 50)
  7. 49th floor -> breaks (49th, this step is actually needed because it might have been the min floor for marble to break is at 50th)

यह कुछ के लिए एक क्रमबद्ध सेट में बाइनरी खोज करने के रूप में कल्पना की जा सकती है, जहां हम प्रत्येक प्रयास के साथ समाधान स्थान आधे हैं। 100 मंजिलों के लिए, हमें लॉग 2 100 = 6.644 (7 कोशिश) की आवश्यकता है। 7 पत्थर के साथ हम सुनिश्चित कर सकते हैं कि न्यूनतम मंजिल कौन सा है जो संगमरमर 128 मंजिलों तक टूट जाएगी।

0
जोड़ा
यह एक बहुत ही अलग समस्या होगी।
जोड़ा लेखक borjab, स्रोत
आपके उत्तर में समस्या यह है कि यह गारंटी नहीं देगा कि अगर अंडा 43 वें तल से टूट जाता है, तो आपको पता नहीं चलेगा कि थ्रेसहोल्ड मंजिल 38 वां था, 39 वें ... 42 वां। साथ ही, इसे देखें
जोड़ा लेखक ABcDexter, स्रोत