जब आपको छत से अंडे फेंकने हों: दैनिक कोडिंग समस्या

दैनिक कोडिंग समस्या 24

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

हमेशा की तरह, आज की समस्या अद्भुत समाचार पत्र द्वारा प्रदान की गई है दैनिक कोडिंग समस्या , जिसे आप अपनी दैनिक कोडिंग चुनौती प्राप्त करने के लिए निःशुल्क सदस्यता ले सकते हैं। इसे जांचें, और अपनी समस्याओं को भी हल करने का प्रयास करें!

बहुत हो गई बातें तो; आइए समस्या देखें!

समस्या

यह समस्या गोल्डमैन सैक्स से एक नौकरी साक्षात्कार में पूछी गई थी। आइए समस्या देखें.

आपको N समान अंडे और k मंजिलों वाली इमारत तक पहुंच दी जाती है। आपका काम सबसे निचली मंजिल ढूंढना है जिस मंजिल से गिराए जाने पर अंडा टूट जाएगा। एक बार अंडा टूट जाए तो उसे दोबारा गिराया नहीं जा सकता। यदि एक अंडा xth मंजिल से गिराने पर टूट जाता है, तो आप मान सकते हैं कि x से अधिक किसी भी मंजिल से गिराने पर भी यह टूट जाएगा।

एक एल्गोरिदम लिखें जो इस मंजिल की पहचान करने के लिए, सबसे खराब स्थिति में, न्यूनतम संख्या में ट्रायल ड्रॉप्स का पता लगाएगा।

उदाहरण के लिए, यदि N = 1 और k = 5 , तो हमें पहली मंजिल से शुरू करके पांचवीं मंजिल तक पहुंचने तक हर मंजिल पर अंडे गिराने की कोशिश करनी होगी, इसलिए हमारा समाधान 5 होगा।

तो, हमें एक इमारत की विभिन्न मंजिलों से फेंकने के लिए कुछ अंडे दिए जाते हैं। हमें दुख है कि एक निश्चित मंजिल (जिसे हम targetFloor कहेंगे) से फेंके गए अंडे जमीन पर गिरने पर नहीं टूटते।

उस मंजिल से लेकर उसके नीचे की हर मंजिल तक, खिड़की से बाहर फेंकने पर अंडे नहीं टूटेंगे। हमें targetFloor खोजने के लिए एक कुशल तरीका खोजने के लिए कहा गया है।

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

यह हमें वास्तव में प्रसिद्ध और महत्वपूर्ण एल्गोरिदम के बारे में बात करने का मौका भी देगा; उनमें से एक जिसे करने के लिए आपको जानना आवश्यक है... मूलतः कुछ भी!

पर्यावरण की स्थापना

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

हम इस समस्या को एक बार फिर गो में लिखेंगे: पढ़ने योग्य होने के लिए पर्याप्त सरल, लेकिन आंतरिक यांत्रिकी को समझने के लिए पर्याप्त जटिल।

हम पहले सरणी बनाते हैं जो हमारी इमारत के रूप में काम करेगी: हम इसे वह आकार दे सकते हैं जो हम चाहते हैं, आकार जितना बड़ा होगा, इमारत उतनी ही ऊंची होगी। उसके बाद, हम गो में निर्मित math/rand मॉड्यूल का उपयोग करके targetFlor का एक उदाहरण बनाते हैं।

मूल रूप से, हम वर्तमान समय को स्रोत के रूप में उपयोग करके 0 और इमारत की ऊंचाई (... सरणी की लंबाई: डी) के बीच एक नया यादृच्छिक पूर्णांक बनाते हैं।

क्रूर बल समाधान

निःसंदेह, सबसे सरल उपाय यह होगा कि प्रत्येक मंजिल पर प्रत्येक अंडे को बाहर फेंक दिया जाए, ताकि यह देखा जा सके कि अंडे किस मंजिल पर टूटना शुरू करते हैं। चूँकि हमारे पास उस जानकारी वाला एक वेरिएबल है, कोई भी समस्या को हल करने के लिए बस एक लूप कर सकता है:

हालाँकि यह सबसे सरल समाधान है, दुर्भाग्य से यह अत्यधिक अक्षम है। कल्पना करें कि अगर सही मंजिल शीर्ष पर है: समस्या को हल करने के लिए 100,000 अंडे तोड़ने होंगे: यह एक बहुत बड़ा आमलेट होगा लेकिन काफी बेकार होगा!

सामान्यतया, इस समाधान की समय जटिलता O(n) है क्योंकि समाधान की जटिलता इनपुट समस्या की जटिलता तक रैखिक रूप से बढ़ती है। हालाँकि यह सबसे कारगर समाधान नहीं है जिसके बारे में हम सोच सकते हैं।

एक कुशल समाधान

आइए फिर एक कारगर समाधान के बारे में सोचें। प्रत्येक मंजिल पर एक-एक अंडा तोड़ने की बजाय, हम एक अनुमान लगा सकते हैं और उस अनुमान के परिणाम के आधार पर, अगले अनुमान को समायोजित कर सकते हैं।

यहां एक उदाहरण दिया गया है: मान लीजिए कि हमारे पास 10 मंजिलों वाली एक इमारत है, और targetFloor 7वीं मंजिल है (निश्चित रूप से हम यह नहीं जानते हैं)। हम निम्नलिखित अनुमान लगा सकते हैं:

मूल रूप से, हम अनुमान लगाते हैं कि targetFloor इमारत की मध्य मंजिल है। हम वहां से अंडा फेंकते हैं, और संभावित परिणाम दो हैं:

• अंडा टूट जाता है, इसका मतलब है कि हम बहुत ऊपर हैं। हम इसमें शामिल, इससे ऊंची मंजिल को त्याग सकते हैं और अपने अनुमानों के साथ आगे बढ़ सकते हैं।

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

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

यदि आप इस दृष्टिकोण को पहचानते हैं, तो आप बिल्कुल सही हैं: यह केवल "वास्तविक दुनिया" समस्या पर लागू एक द्विआधारी खोज है। बाइनरी सर्च एक सरल और साफ -सुथरा विभाजन और जीत एल्गोरिथ्म है, जिसका अर्थ है कि प्रत्येक चरण पर, समस्या का आकार तब तक आधा हो जाता है जब तक हम समाधान नहीं ढूंढ लेते।

इसका मतलब यह है कि यह एल्गोरिथम, पिछले वाले की तुलना में, बहुत तेज़ है। आइए कोड देखें!

आइए गहराई से देखें. बाइनरी खोज फ़ंक्शन 4 तर्क लेता है:

• overArray , पूर्णांकों की एक सरणी, जो वह इमारत है जिस पर हम लूपिंग कर रहे हैं;

• bottom , इमारत का निचला सूचकांक;

• top , इमारत का शीर्ष मंजिल सूचकांक;

• breakFloor , वेरिएबल targetFloor यह जांचने के लिए रखता है कि क्या हम इसे बिल्डिंग में पा सकते हैं।

उसके बाद, हम इमारत पर लूप करते हैं जबकि bottom top से नीचे होता है: बाइनरी खोज में, जब दो स्थितीय तर्क आपस में जुड़ते हैं और स्वैप करते हैं, तो इसका मतलब है कि खोजा गया तत्व नहीं मिला।

इसलिए, यदि एल्गोरिथ्म इस स्थिति में समाप्त होता है, तो लूप समाप्त हो जाता है और हम -1 लौटते हैं, जिसका अर्थ है कि जिस तत्व को हम ढूंढ रहे हैं वह सरणी में मौजूद नहीं था। यदि हम अभी भी तत्व की खोज कर रहे हैं, तो हम ऊपर की छवि में जो दिखाया गया है उसे लागू करते हैं।

हम middlePoint तत्व की गणना bottom और top के बीच के फर्श के रूप में करते हैं और हम जांचते हैं कि middlePoint == breakFloor । यदि ऐसा है, तो हम परिणाम के रूप में middlePoint लौटाते हैं।

यदि ऐसा नहीं है, तो हम bottom या top तदनुसार समायोजित करते हैं: यदि middlePoint breakFloor से बड़ा है, तो इसका मतलब है कि हम इमारत पर बहुत ऊंचे हैं इसलिए हम top संभावित मंजिल को middlePoint — 1 पर सेट करके अपनी भविष्यवाणी को कम करते हैं।

यदि middlePoint breakFloor से छोटा है, तो हम middlePoint+1 के रूप में सेटिंग करके अपने bottom समायोजित करते हैं।

अब सब कुछ जांचने के लिए, main फ़ंक्शन में, हम पहले की तरह पर्यावरण उत्पन्न करते हैं, और bsFloor नामक एक नया वेरिएबल बनाते हैं जो हमारे परिणाम को रखेगा।

यह पुष्टि करने के लिए कि हमारा एल्गोरिदम हमें सही परिणाम पर लाया है, हम bsFloor और targetFloor दोनों का प्रिंट आउट लेते हैं, जो पहले यादृच्छिक रूप से उत्पन्न हुआ था।

समय की जटिलता

जैसा कि हमने पहले अनुमान लगाया था, यह एल्गोरिदम रैखिक एल्गोरिदम से कहीं अधिक तेज़ है। चूँकि हम प्रत्येक चरण में इमारत को आधा करते हैं, हम log₂(n) में सही मंजिल पा सकते हैं जहाँ n len(building) के बराबर है।

इसका मतलब है कि इस एल्गोरिदम की समय जटिलता O(log(n)) है। आपको रैखिक समाधान और इस अंतिम समाधान के बीच कुछ तुलना देने के लिए, यदि इमारत में 100 मंजिलें हैं, तो रैखिक एल्गोरिदम सबसे खराब स्थिति में 100 पुनरावृत्तियों को लेता है, जबकि बाइनरी खोज एल्गोरिदम लॉग₂100 = 6.64 लेता है, इसलिए 7 पुनरावृत्तियों को लेता है।

इसके अलावा, यह अंतिम खोज रैखिक खोज की तुलना में अधिक कुशल है क्योंकि जितनी अधिक इमारत बढ़ती है, बाइनरी खोज उतनी ही अधिक कुशल होती है। 1.000.000.000 मंजिलों वाली एक इमारत के लिए, रैखिक एक 1.000.000.000 कदम उठाता है, जबकि बाइनरी एक लॉग₂1.000.000.000 = 29.9 लेता है, इसलिए 30 कदम। बहुत बड़ा सुधार!

निष्कर्ष

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

अंत में, यदि आपको यह लेख रोचक या उपयोगी लगा और आप कॉफ़ी की पेशकश करके अपना योगदान देना चाहते हैं, तो बेझिझक मेरी ओर से ऐसा करें को-फाई पृष्ठ!

और, हमेशा की तरह, पढ़ने के लिए धन्यवाद!

निकॉला

यहाँ भी प्रकाशित किया गया