बेलमैन फोर्ड एल्गोरिथम: कोडिंग साक्षात्कार गाइड

टीएल;डीआर: बेलमैन फोर्ड एल्गोरिदम भारित निर्देशित ग्राफ़ में एकल-स्रोत सबसे छोटे पथ ढूंढता है, तब भी जब कुछ किनारों पर नकारात्मक भार होता है। स्रोत दूरी को शून्य से प्रारंभ करें, अन्य सभी को अनंत तक, प्रत्येक किनारे को V माइनस 1 बार तक शिथिल करें, फिर एक अतिरिक्त पास बनाएं: कोई भी और सुधार साबित करता है कि एक पहुंच योग्य नकारात्मक-भार चक्र मौजूद है।

बेलमैन फोर्ड एल्गोरिथम: कोडिंग साक्षात्कार गाइड

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

YesToTheOffer आज़माएं

बार-बार किनारे पर छूट के साथ बेलमैन फोर्ड सबसे छोटी पथ तालिका

बेलमैन फोर्ड एल्गोरिथम क्या है?

बेलमैन फोर्ड एक गतिशील-प्रोग्रामिंग-शैली सबसे छोटा-पथ एल्गोरिदम है। पहले पूर्ण मार्ग के बाद, सर्वोत्तम ज्ञात पथ अधिकतम एक किनारे का उपयोग करते हैं; दूसरे के बाद, अधिकतम दो किनारे। एक सरल पथ में अधिकतम V शून्य से 1 किनारा होता है, जो लूप गिनती और शुद्धता तर्क दोनों को समझाता है। डिज्क्स्ट्रा के एल्गोरिदम के विपरीत, बेलमैन फोर्ड गैर-नकारात्मक बढ़त भार नहीं मानता है।

आप एज रिलैक्सेशन की व्याख्या कैसे करते हैं?

भार w के साथ u से v तक के किनारे के लिए, विश्राम पूछता है कि क्या दूरी [u] + w दूरी [v] से छोटी है। केवल तभी जोड़ें जब आप पहुंच योग्य हों। यदि उम्मीदवार बेहतर है, तो दूरी[v] अपडेट करें और पूर्ववर्ती[v] को यू पर सेट करें। पूर्ववर्ती सरणी दूरियों के लिए वैकल्पिक है, लेकिन यह आपको वास्तविक पथ का पुनर्निर्माण करने और आपके परिणाम को स्पष्ट रूप से समझाने की सुविधा देती है।

दूरियों, पूर्ववर्तियों और नकारात्मक चक्रों के लिए बेलमैन फोर्ड साक्षात्कार चेकलिस्ट

आप एक साक्षात्कार में बेलमैन फोर्ड का पता कैसे लगाते हैं?

एक छोटे ग्राफ़ का उपयोग करें और प्रति पास एक दूरी पंक्ति लिखें। स्रोत A से 0 पर और हर दूसरे शीर्ष से अनंत पर प्रारंभ करें। प्रत्येक अद्यतन को रिकॉर्ड करते हुए, संपूर्ण एज सूची को एक सुसंगत क्रम में स्कैन करें। जब पूरे पास में कोई परिवर्तन न हो तो जल्दी रुकें। स्पष्ट रहें कि किनारे का क्रम मध्यवर्ती पंक्तियों को बदल सकता है लेकिन अंतिम सही दूरी को नहीं जब कोई पहुंच योग्य नकारात्मक चक्र मौजूद नहीं होता है।

आपको कौन सा छद्मकोड लिखना चाहिए?

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

समय और स्थान की जटिलताएँ क्या हैं?

मानक आसन्नता-किनारे-सूची कार्यान्वयन ओ (वीई) समय में चलता है क्योंकि यह प्रत्येक वी माइनस 1 पास, प्लस एक डिटेक्शन पास पर ई किनारों को स्कैन कर सकता है। यह दूरियों और पूर्ववर्तियों के लिए O(V) सहायक स्थान का उपयोग करता है। जल्दी रुकने से अनुकूल इनपुट में सुधार होता है, लेकिन सबसे खराब स्थिति O(VE) ही रहती है।

साक्षात्कार का निर्णय	बेलमैन फोर्ड का प्रयोग कब करें	जब कोई अन्य दृष्टिकोण पसंद करें
किनारे का वजन	नकारात्मक किनारे हो सकते हैं	सभी किनारे गैर-नकारात्मक हैं और गति मायने रखती है
साइकिल की आवश्यकता	एक पहुंच योग्य नकारात्मक चक्र का पता लगाएं	चक्र का पता लगाने की आवश्यकता नहीं है
जटिलता	ओ(वीई) स्वीकार्य है	बार-बार स्कैन करने के लिए ग्राफ़ बहुत बड़ा या सघन है

आपको दिज्क्स्ट्रा के स्थान पर बेलमैन फोर्ड को कब चुनना चाहिए?

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

आपको किन गलतियों से बचना चाहिए?

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

आप स्पष्टीकरण का अभ्यास कैसे कर सकते हैं?

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

जिस सामग्री को आप पहले से समझते हैं उसे व्यवस्थित करने, स्पष्टीकरणों का पूर्वाभ्यास करने और अपने प्रदर्शन की समीक्षा करने के लिए एआई का उपयोग करें। नियोक्ता और मूल्यांकन प्रदाता के नियमों का पालन करें, और कभी भी अनुभव, संख्या या परिणाम का आविष्कार न करें।

एआई इंटरव्यू कोपायलट गाइड, रेज़्यूमे-आधारित तैयारी, और साक्षात्कार के बाद समीक्षा वर्कफ़्लो के साथ जारी रखें।

अक्सर पूछे जाने वाले प्रश्नों

FAQ

क्या बेलमैन फोर्ड नकारात्मक भार संभाल सकता है?

हाँ। यह नकारात्मक बढ़त भार को संभाल सकता है। यह पहुंच योग्य नकारात्मक-भार चक्र से प्रभावित शीर्षों के लिए सीमित सबसे छोटे रास्ते का निर्माण नहीं कर सकता है, यही कारण है कि अतिरिक्त विश्राम पास आवश्यक है।

बेलमैन फोर्ड 1 बार वी माइनस क्यों चलाता है?

किसी भी सरल पथ में अधिकतम V शून्य से 1 किनारा होता है। पास k के बाद, एल्गोरिदम ने अधिकतम k किनारों का उपयोग करते हुए सबसे छोटे पथ पर विचार किया है, इसलिए V माइनस 1 पास हर सरल सबसे छोटे पथ को कवर करता है।

बेलमैन फोर्ड नकारात्मक चक्र का पता कैसे लगाता है?

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

बेलमैन फोर्ड की जटिलता क्या है?

मानक एल्गोरिदम O(VE) समय और O(V) सहायक स्थान का उपयोग करता है। जब पूर्ण पास कोई अपडेट नहीं करता है तो एक प्रारंभिक-निकास ध्वज लूप को रोक सकता है, लेकिन यह सबसे खराब स्थिति में बदलाव नहीं करता है।

क्या बेलमैन फोर्ड दिज्क्स्ट्रा से बेहतर है?

कोई भी सार्वभौमिक रूप से बेहतर नहीं है। बेलमैन फोर्ड नकारात्मक वजन और चक्र का पता लगाने का समर्थन करता है; दिज्क्स्ट्रा आम तौर पर तब तेज़ होता है जब सभी किनारों का भार गैर-नकारात्मक होता है।

साक्ष्य के साथ अभ्यास करें, स्क्रिप्ट के साथ नहीं

YesToTheOffer आपके बायोडाटा, भूमिका विवरण और निजी नोट्स में तैयारी और वास्तविक समय की उत्तर संरचना को आधार बना सकता है, फिर साक्षात्कार के बाद की समीक्षा के लिए एक प्रतिलेख को संरक्षित कर सकता है।

साक्ष्य के साथ अभ्यास करें, स्क्रिप्ट के साथ नहीं

YesToTheOffer आज़माएं

बेलमैन फोर्ड एल्गोरिथम: कोडिंग साक्षात्कार गाइड