कोडिंग इंटरव्यू: आप द्विदिशीय (Bidirectional) BFS के साथ Word Ladder को कैसे हल करते हैं?

प्रश्न और लागू संदर्भ

beginWord, endWord, और wordList दिए जाने पर, सबसे छोटे परिवर्तन अनुक्रम की लंबाई ज्ञात कीजिए। प्रत्येक आसन्न युग्म ठीक एक स्थिति में भिन्न होना चाहिए, और beginWord के बाद का प्रत्येक शब्द, जिसमें endWord भी शामिल है, शब्दकोश में उपस्थित होना चाहिए। लौटाई गई लंबाई शब्दों की गणना करती है, परिवर्तनों की नहीं।

beginWord = "hit"
endWord   = "cog"
wordList  = ["hot", "dot", "dog", "lot", "log", "cog"]

One shortest sequence:
hit -> hot -> dot -> dog -> cog

Return: 5

मानक अनुबंध का उपयोग करें: beginWord और endWord भिन्न हैं, सभी शब्दों में लोअरकेस अंग्रेजी अक्षर हैं, शब्दकोश के प्रत्येक शब्द की लंबाई समान L है, शब्दकोश की प्रविष्टियाँ अद्वितीय हैं, और अधिकतम N = 5,000 प्रविष्टियाँ हैं। यदि endWord अनुपस्थित या अगम्य (unreachable) है, तो 0 लौटाएं।

यह एक ग्राफ़ समस्या है जिसका ग्राफ़ स्ट्रिंग्स के अंदर छिपा हुआ है। प्रत्येक वैध शब्द एक शीर्ष (vertex) है; दो शब्द एक अदिष्‍ट (undirected) इकाई-लागत वाले किनारे (edge) को साझा करते हैं जब वे एक स्थिति में भिन्न होते हैं। इसलिए यह प्रश्न एक अभारित (unweighted) ग्राफ़ में एकल-युग्म सबसे छोटे पथ की मांग करता है। 2026 में सार्वजनिक ग्राफ़-इंटरव्यू सामग्री अभी भी Word Ladder को एक BFS रूपांतरण समस्या के रूप में सूचीबद्ध करती है, और जून 2026 का एक सार्वजनिक इंटरव्यू विवरण अधिक कठिन Word Ladder II संस्करण पर चर्चा करता है। वे रिकॉर्ड वर्तमान तैयारी मूल्य स्थापित करते हैं; वे किसी इंटरव्यू आवृत्ति या सत्यापित कंपनी आरोपण को स्थापित नहीं करते हैं, इसलिए यह लेख ऐसा कोई दावा नहीं करता है।

साक्षात्कारकर्ता क्या मूल्यांकन करता है

पहला संकेत यह है कि क्या उम्मीदवार एक अंतर्निहित (implicit) ग्राफ़ को देखता है। शब्दकोश के प्रत्येक युग्म की तुलना करने से सही ग्राफ़ बनता है, लेकिन इसमें O(N²L) वर्ण तुलनाएँ लगती हैं। एक बेहतर उत्तर केवल वर्तमान शब्द के संभावित पड़ोसियों को उत्पन्न करता है: इसके L वर्णों में से प्रत्येक को अन्य 25 अक्षरों से बदलें, फिर शब्दकोश की सदस्यता का परीक्षण करने के लिए हैश सेट का उपयोग करें।

दूसरा संकेत सबसे छोटे पथ का तर्क है। प्रत्येक रूपांतरण में एक चरण लगता है, इसलिए BFS गैर-घटती दूरी में स्थितियों का अन्वेषण करता है। DFS अंततः एक पथ पा सकता है लेकिन यह पहले पथ को सबसे छोटा नहीं बनाता है। Dijkstra इकाई भार के साथ सही है लेकिन बिना कोई अतिरिक्त जानकारी जोड़े केवल एक प्राथमिकता कतार (priority queue) जोड़ता है।

तीसरा संकेत विज़िट किए जाने का समय (visited timing) है। किसी शब्द को अनविज़िट किए गए सेट से तब निकलना चाहिए जब वह फ्रंटियर में प्रवेश करता है, न कि तब जब इसे बाद में विस्तारित किया जाता है। विलंबित अंकन कई मूल (parent) नोड्स को एक ही शब्द को कतारबद्ध करने की अनुमति देता है, जिससे कार्य और मेमोरी दोनों बढ़ जाते हैं। द्विदिशीय BFS के साथ, एक उत्पन्न पड़ोसी को अनविज़िट किए गए सेट के विरुद्ध जाँचे जाने से पहले विपरीत वर्तमान फ्रंटियर के विरुद्ध जाँचा जाना चाहिए।

चौथा संकेत यह है कि क्या अनुकूलन सिद्ध करने योग्य रहता है। द्विदिशीय BFS प्रत्येक समापन बिंदु से एक स्तर का फ्रंटियर रखता है और छोटे फ्रंटियर का विस्तार करता है। यह अक्सर एक ट्री-जैसी खोज को लगभग b^d स्थितियों से b^(d/2) के निकट दो खोजों तक कम कर देता है, जहाँ b प्रभावी शाखाकरण (branching) है और d किनारों में उत्तर है। यह सबसे खराब स्थिति वाली स्पर्शोन्मुख सीमा (worst-case asymptotic bound) में सुधार नहीं करता है: एक प्रतिकूल शब्दकोश फिर भी एल्गोरिदम से लगभग हर शब्द का निरीक्षण करवा सकता है।

अंत में, एक सशक्त उत्तर वास्तविक स्ट्रिंग लागत बताता है। प्रत्येक विस्तारित शब्द अधिकतम 25L म्यूटेशन का प्रयास करता है। Python में, एक उम्मीदवार स्ट्रिंग बनाने में O(L) की लागत आती है, इसलिए एक निश्चित 26-अक्षर वाले वर्णमाला के लिए कार्यान्वयन की अपेक्षित समय जटिलता O(NL²) है, जिसमें O(NL) वर्ण भंडारण है। इसे O(NL) कहना मौन रूप से स्ट्रिंग निर्माण को स्थिर समय मानता है।

उत्तर देने से पहले स्पष्टीकरण संबंधी सवाल

• वापसी मान (return value) वास्तव में क्या गिनता है? यह अनुबंध दोनों समापन बिंदुओं को गिनता है। इसलिए एक सीधा वैध

रूपांतरण 2 लौटाता है; एक किनारे-गणना (edge-count) API एक कम लौटाएगा।

• क्या endWord शब्दकोश में होना चाहिए? हाँ। यदि यह अनुपस्थित है, तो खोजने से पहले 0 लौटाएं। एक संस्करण

जो लक्ष्य को शब्दकोश के बाहर अनुमति देता है, इस प्रारंभिक-निकास नियम को बदल देता है।

• क्या सभी शब्द समान लंबाई और वर्णमाला के हैं? हाँ: लंबाई L, लोअरकेस अंग्रेजी अक्षर। यूनिकोड,

मिश्रित लंबाई, या एक बड़ा वर्णमाला पड़ोसी निर्माण और उसकी लागत को बदल देता है।

• क्या प्रविष्टियाँ अद्वितीय हैं? हाँ। इनपुट को एक सेट में बदलना अभी भी अपेक्षित स्थिर-समय

सदस्यता और विज़िट किए गए निष्कासन के लिए उपयोगी है। यदि डुप्लिकेट की अनुमति होती, तो वे अलग-अलग शीर्ष नहीं बनाते।

• क्या हमें एक लंबाई, एक पथ, या प्रत्येक सबसे छोटा पथ चाहिए? आधार समस्या को केवल लंबाई की आवश्यकता है।

एक पथ लौटाने के लिए पैरेंट मैप की आवश्यकता होती है; प्रत्येक सबसे छोटा पथ लौटाने के लिए समान BFS स्तर से सभी पैरेंट्स को संरक्षित करने की आवश्यकता होती है और एक ही उत्सुक विलोपन नियम (eager deletion rule) का अपरिवर्तित उपयोग नहीं किया जा सकता है।

• क्या यह एक स्थिर शब्दकोश पर एक क्वेरी है या कई क्वेरीज़ हैं? एक क्वेरी के लिए, ऑन-डिमांड म्यूटेशन

सरल है और एक पूर्ण इंडेक्स से बचाता है। बार-बार की जाने वाली क्वेरीज़ एक पुन: प्रयोज्य वाइल्डकार्ड-पैटर्न इंडेक्स को उचित ठहरा सकती हैं।

• क्या beginWord पहले से ही शब्दकोश में दिखाई दे सकता है? हाँ। यह अभी भी एक शीर्ष है और इसे इनिशियलाइज़ेशन के दौरान

अनविज़िट किए गए सेट से हटा दिया जाना चाहिए।

30-सेकंड का उत्तर ढाँचा

"मैं प्रत्येक शब्द को एक शीर्ष के रूप में मॉडल करता हूँ और दो शब्दों को तब जोड़ता हूँ जब वे एक स्थिति में भिन्न होते हैं। प्रत्येक किनारे की लागत एक रूपांतरण है, इसलिए यह एक अभारित सबसे छोटे पथ की समस्या है। मैं beginWord और endWord से द्विदिशीय BFS चलाऊँगा, हमेशा छोटे पूर्ण-स्तर के फ्रंटियर का विस्तार करूँगा। प्रत्येक फ्रंटियर शब्द के लिए, मैं इसके अधिकतम 25L एक-अक्षर के म्यूटेशन उत्पन्न करता हूँ और हैश सेट में उनका परीक्षण करता हूँ। यदि कोई म्यूटेशन विपरीत फ्रंटियर में है, तो दो सबसे छोटे खोजे गए प्रीफिक्स सबसे छोटा अनुक्रम बनाते हैं, इसलिए मैं वर्तमान शब्द गणना प्लस एक लौटाता हूँ। अन्यथा मैं एक वैध अनदेखे शब्द को अगली फ्रंटियर में जोड़ते ही हटा देता हूँ। यदि endWord अनुपस्थित है या कोई फ्रंटियर खाली हो जाता है, तो मैं शून्य लौटाता हूँ। सबसे खराब स्थिति में अभी भी N शब्द विज़िट होते हैं; चूँकि Python उम्मीदवार निर्माण L वर्णों की प्रतिलिपि बनाता है, समय O(NL²) है और संग्रहीत स्ट्रिंग सामग्री O(NL) है। मैं प्रत्यक्ष, अगम्य, चक्रीय, डुप्लिकेट-खोज, और असममित-फ्रंटियर मामलों का परीक्षण करूँगा।"

चरण-दर-चरण गहन विश्लेषण

ग्राफ़ मॉडल से शुरुआत करें। मान लें कि शीर्ष सेट में शब्दकोश का प्रत्येक शब्द और beginWord शामिल है। किन्हीं दो समान लंबाई वाले शब्दों के लिए, ठीक तब एक किनारा जोड़ें जब उनकी हैमिंग दूरी (Hamming distance) एक हो। ग्राफ़ अदिष्‍ट है: यदि hot, dot में बदल सकता है, तो विपरीत परिवर्तन भी वैध है। यह अभारित है क्योंकि प्रत्येक कानूनी परिवर्तन एक किनारे का योगदान देता है।

एक स्पष्ट युग्मवार (pairwise) ग्राफ़ O(N²) युग्मों की तुलना करता है और प्रति तुलना O(L) खर्च करता है। वह O(N²L) प्रीप्रोसेसिंग है, भले ही अधिकांश युग्म असंबद्ध हों। इनपुट वर्णमाला एक छोटा उम्मीदवार स्थान देती है। एक शब्द में अधिकतम 25L भिन्न एक-अक्षर म्यूटेशन होते हैं; शब्दकोश की सदस्यता तय करती है कि कौन से वास्तविक शीर्ष हैं।

एकतरफा BFS पहले से ही सही है। इसका इनवेरिएंट है:

At the start of level k:
  the frontier contains exactly the discovered words at edge distance k;
  no undiscovered word has distance less than k;
  every word outside unvisited has already been assigned its minimum distance.

BFS स्तर k + 1 केवल स्तर k से बनाता है। इसलिए किसी शब्द की पहली खोज सबसे छोटे पथ का उपयोग करती है। खोज के समय unvisited से किसी शब्द को हटाना उस तथ्य को संरक्षित करता है और डुप्लिकेट फ्रंटियर प्रविष्टियों को रोकता है।

एकल ज्ञात लक्ष्य के लिए, दोनों समापन बिंदुओं से खोजें। front आरंभिक पक्ष से एक पूर्ण स्तर है, और back अंतिम पक्ष से एक पूर्ण स्तर है। sequence_length उनकी वर्तमान किनारे की गहराईयों के योग प्लस एक के बराबर है, क्योंकि यह अभी तक एक कनेक्टिंग किनारे के बिना दोनों सिरों पर फ्रंटियर शब्दों को गिनता है। किसी भी पूरे फ्रंटियर का विस्तार करने से वह गहराई योग एक से बढ़ जाता है। यदि कोई उत्पन्न शब्द विपरीत फ्रंटियर से संबंधित है, तो कनेक्टिंग किनारा उत्तर को sequence_length + 1 बना देता है।

छोटे फ्रंटियर का विस्तार प्रदर्शन को बदलता है, शुद्धता को नहीं। दो सेटों की अदला-बदली केवल यह बदलती है कि कौन सी वैध BFS परत आगे बढ़ती है; प्रत्येक सेट अभी भी अपने स्वयं के मूल से एक सटीक गहराई का प्रतिनिधित्व करता है। विपरीत वर्तमान फ्रंटियर के विरुद्ध प्रतिच्छेदन (intersection) की जाँच करना आवश्यक है। एक एकल वैश्विक unvisited सेट सुरक्षित है क्योंकि जब कोई पक्ष किसी शब्द की खोज करता है तो वह तुरंत उस पर दावा करता है। यदि बाद के विस्तार में दूसरी खोज की पहले से विस्तारित परत के लिए कोई किनारा होता, तो वह पूर्व विस्तार उसी शब्द को पहले ही खोज लेता, इसलिए खोजें अपने वर्तमान फ्रंटियर के पीछे चुपचाप पार नहीं हो सकती हैं।

ALPHABET = "abcdefghijklmnopqrstuvwxyz"


def ladder_length(
    begin_word: str,
    end_word: str,
    word_list: list[str],
) -> int:
    unvisited = set(word_list)
    if end_word not in unvisited:
        return 0

    front = {begin_word}
    back = {end_word}
    unvisited.discard(begin_word)
    unvisited.remove(end_word)
    sequence_length = 1

    while front and back:
        if len(front) > len(back):
            front, back = back, front

        next_front: set[str] = set()

        for word in front:
            for index, original in enumerate(word):
                for letter in ALPHABET:
                    if letter == original:
                        continue

                    candidate = word[:index] + letter + word[index + 1 :]

                    if candidate in back:
                        return sequence_length + 1

                    if candidate in unvisited:
                        unvisited.remove(candidate)
                        next_front.add(candidate)

        front = next_front
        sequence_length += 1

    return 0

फ्रंटियर परतों द्वारा नमूने को ट्रेस करें:

एल्गोरिदम विस्तार 3 पर छोटे cog पक्ष का विस्तार करता है। विस्तार 4 पर, dot, dog तक पहुँचता है या lot, log तक पहुँचता है, इसलिए यह 5 लौटाता है। सेट पुनरावृत्ति क्रम एक अलग सबसे छोटा मीटिंग एज चुन सकता है; लंबाई अपरिवर्तित रहती है।

मान लें N शब्दकोश का आकार है और L शब्द की लंबाई है। प्रत्येक शब्द को एक फ्रंटियर में अधिकतम एक बार जोड़ा जाता है और यदि विस्तारित किया जाता है, तो 25L उम्मीदवारों का प्रयास करता है। हैश लुकअप अपेक्षित O(1) है, लेकिन प्रत्येक Python स्लाइस-एंड-कॉन्केटनेशन उम्मीदवार की लागत O(L) है, जो एक निश्चित वर्णमाला के साथ O(NL²) अपेक्षित सबसे खराब स्थिति का समय देती है। सेट अधिकतम O(N) संदर्भ संग्रहीत करते हैं और उनकी स्ट्रिंग्स में O(NL) वर्ण होते हैं। अस्थायी उम्मीदवार स्ट्रिंग्स एक समय में O(L) जोड़ती हैं। यदि कोई इंटरव्यू एक म्यूटेबल फिक्स्ड-चौड़ाई वाले वर्ण बफ़र का उपयोग करता है और उम्मीदवार को सामग्री में बदलने या हैश करने को O(L) मानता है, तब भी वही सटीक सीमा लागू होती है।

एक वाइल्डकार्ड इंडेक्स मुख्य विकल्प है। h*t, *ot, और ho* जैसे पैटर्न को मेल खाने वाले शब्दों पर मैप करें। इसे कई प्रश्नों में पुन: उपयोग किया जा सकता है और यह शब्दकोश से अनुपस्थित अक्षरों को आजमाने से बचाता है। Python में, N शब्दों के लिए L पैटर्न स्ट्रिंग्स बनाने में भी O(NL²) वर्ण कार्य की लागत आती है और यह O(NL) बकेट प्रविष्टियों को बनाए रख सकता है। BFS के दौरान, उपभोग की गई पैटर्न बकेट को साफ़ करें या इसे संसाधित के रूप में ट्रैक करें; कई शब्दों के लिए एक ही बड़ी बकेट को स्कैन करने से अन्यथा द्विघात कार्य (quadratic work) फिर से बन सकता है। बताई गई बाधाओं के तहत एकल क्वेरी के लिए, म्यूटेशन प्लस एक सेट में कम जटिलताएँ होती हैं।

केवल नमूने का नहीं, निष्पादन योग्य अनुबंध का परीक्षण करें:

cases = [
    (
        "hit",
        "cog",
        ["hot", "dot", "dog", "lot", "log", "cog"],
        5,
    ),
    ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
    ("a", "c", ["a", "b", "c"], 2),
    ("red", "tax", ["ted", "tex", "red", "tax", "tad", "den", "rex", "pee"], 4),
    ("aaa", "bbb", ["aab", "abb", "bbb", "aba", "baa"], 4),
]

for begin_word, end_word, words, expected in cases:
    actual = ladder_length(begin_word, end_word, words)
    assert actual == expected, (begin_word, end_word, actual, expected)

प्रॉपर्टी परीक्षण एक छोटा यादृच्छिक शब्दकोश उत्पन्न कर सकते हैं, एक विश्वसनीय ऑरेकल (oracle) के रूप में स्पष्ट युग्मवार ग्राफ़ बना सकते हैं, और इसके सामान्य BFS परिणाम की तुलना अनुकूलित फ़ंक्शन से कर सकते हैं। इनपुट सूची को भी अपरिवर्तित रखें, ऐसे शब्दकोशों का परीक्षण करें जहाँ एक फ्रंटियर दूसरे की तुलना में बहुत तेज़ी से बढ़ता है, और पुष्टि करें कि कई पैरेंट्स के माध्यम से पहुँचने योग्य शब्द का केवल एक बार विस्तार किया गया है।

उच्च-गुणवत्ता वाला नमूना उत्तर

"शब्द एक अंतर्निहित अदिष्‍ट ग्राफ़ बनाते हैं। एक शीर्ष एक वैध शब्द है, और एक किनारा हैमिंग दूरी एक वाले शब्दों को जोड़ता है। चूँकि सभी किनारों की लागत एक होती है, BFS न्यूनतम रूपांतरणों की संख्या देता है। मैं शब्दों की संख्या लौटाऊँगा, इसलिए hit -> hot की लंबाई दो है।

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

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

अधिकतम N शब्दों का विस्तार किया जाता है। प्रत्येक 25L म्यूटेशन का प्रयास करता है, और Python प्रत्येक उम्मीदवार के निर्माण में O(L) खर्च करता है, इसलिए मैं O(NL²) अपेक्षित समय और O(NL) संग्रहीत वर्ण बताता हूँ। द्विदिशीय खोज आमतौर पर अन्वेषण की गई स्थितियों को कम करती है लेकिन इसकी सबसे खराब स्थिति समान होती है। बार-बार की जाने वाली क्वेरीज़ के लिए मैं एक पुन: प्रयोज्य वाइल्डकार्ड इंडेक्स पर विचार करूँगा; इस एकमुश्त क्वेरी के लिए, म्यूटेशन सरल है। मैं आधिकारिक नमूने, अनुपस्थित लक्ष्य, प्रत्यक्ष परिवर्तन, कई सबसे छोटे मार्गों, चक्रों और एक यादृच्छिक स्पष्ट-ग्राफ़ ऑरेकल को सत्यापित करूँगा।"

सामान्य गलतियाँ

• DFS चलाना और उसका पहला पथ लौटाना → DFS रूपांतरण गणना द्वारा पथों पर नहीं जाता है →

BFS का उपयोग करें क्योंकि प्रत्येक किनारे की इकाई लागत होती है।

• प्रत्येक शब्दकोश युग्म की तुलना करना → ग्राफ़ निर्माण की लागत O(N²L) होती है → **प्रति विस्तारित शब्द अधिकतम 25L

उम्मीदवार पड़ोसी उत्पन्न करें।**

• किसी शब्द को पॉप किए जाने पर ही विज़िट किया गया चिह्नित करना → कई पैरेंट्स इसे कतारबद्ध कर सकते हैं → **इसे फ्रंटियर में जोड़ते समय

unvisited से हटा दें।**

• विपरीत फ्रंटियर से पहले केवल unvisited की जाँच करना → मिलने वाला शब्द दूसरी खोज द्वारा पहले ही हटाया जा चुका होता है → पहले विपरीत वर्तमान फ्रंटियर का परीक्षण करें।
• जिस भी पक्ष का नाम front है उसका विस्तार करना → एक पक्ष में विस्फोट हो सकता है जबकि दूसरा छोटा रहता है →

अदला-बदली करें और छोटे पूर्ण-स्तर के फ्रंटियर का विस्तार करें।

• किनारे की गणना को शब्द गणना के साथ मिलाना → नमूना पाँच के बजाय चार लौटाता है → **अनुक्रम

गणना को एक पर इनिशियलाइज़ करें और मीटिंग एज पर कनेक्टिंग शब्द जोड़ें।**

• यह दावा करना कि द्विदिशीय BFS सबसे खराब स्थिति की जटिलता को बदलता है → एक सघन प्रतिकूल शब्दकोश अभी भी

लगभग हर शब्द को उजागर कर सकता है → शाखाकरण-कारक लाभ को विशिष्ट बताएं, गारंटीकृत नहीं।

• Python म्यूटेशन को O(NL) कहना → प्रत्येक उम्मीदवार L वर्णों को कॉपी या हैश करता है → **स्ट्रिंग-ऑपरेशन

मॉडल बताएं और इस कार्यान्वयन के लिए O(NL²) का उपयोग करें।**

• वाइल्डकार्ड बकेट का उपभोग किए बिना उनका पुन: उपयोग करना → वही बड़ी सूची बार-बार स्कैन की जाती है →

प्रत्येक संसाधित पैटर्न बकेट को साफ़ करें या इसे उपभोग के रूप में चिह्नित करें।

• एक वैश्विक विज़िट किए गए सेट का उपयोग करना लेकिन आंशिक-स्तर के विस्तार की अनुमति देना → मीटिंग क्रम और दूरी

लेखांकन को सिद्ध करना कठिन हो जाता है → एक समय में एक पूर्ण फ्रंटियर स्तर आगे बढ़ाएं।

• स्व-रिपोर्ट किए गए कंपनी अनुभव को सत्यापित आरोपण के रूप में उद्धृत करना → एक सार्वजनिक पोस्ट एक

नियोक्ता रिकॉर्ड नहीं है → companyName को शून्य रखें और रिकॉर्ड का उपयोग केवल वर्तमान सार्वजनिक साक्ष्य के रूप में करें।

फॉलो-अप और उन्हें कैसे संभालें

फॉलो-अप 1: आप एक वास्तविक सबसे छोटा अनुक्रम कैसे लौटाएंगे?

प्रत्येक दिशा के लिए एक पैरेंट मैप रखें। जब किसी उम्मीदवार की खोज की जाती है, तो उस शब्द को रिकॉर्ड करें जिसने इसे उत्पन्न किया। मीटिंग एज पर, आरंभिक-पक्ष पैरेंट मैप को वापस beginWord तक ले जाएं, उस प्रीफिक्स को उलट दें, फिर अंतिम-पक्ष पैरेंट मैप को endWord की ओर ले जाएं। चूँकि कार्यान्वयन फ्रंटियर चर की अदला-बदली कर सकता है, इसलिए यह मानने के बजाय कि वर्तमान front हमेशा आरंभिक पक्ष है, पैरेंट मैप को अर्थ संबंधी दिशा (semantic direction) द्वारा संग्रहीत करें। पैरेंट स्टोरेज शब्दकोश स्ट्रिंग्स के अतिरिक्त O(N) संदर्भ है।

फॉलो-अप 2: Word Ladder II के लिए क्या बदलता है, जो प्रत्येक सबसे छोटा अनुक्रम लौटाता है?

प्रति शब्द एक पैरेंट अपर्याप्त है। साधारण स्तर-क्रम BFS के बारे में तर्क करना अक्सर आसान होता है: प्रत्येक पूर्ववर्ती (predecessor) को इकट्ठा करें जो किसी शब्द तक उसके न्यूनतम स्तर पर पहुँचता है, और पूरे स्तर के समाप्त होने के बाद ही वैश्विक शब्दकोश से नए खोजे गए शब्दों को हटा दें। यह लंबे पथों को बाद में पैरेंट्स जोड़ने की अनुमति दिए बिना कई समान-स्तर के पैरेंट्स की अनुमति देता है। endWord तक पहुँचने वाले पहले स्तर को पूरा करने के बाद रुकें, फिर पूर्ववर्ती DAG के माध्यम से बैकट्रैक करें। आउटपुट आकार घातीय (exponential) हो सकता है, इसलिए जटिलता में लौटाए गए अनुक्रमों की कुल संख्या और लंबाई शामिल होनी चाहिए।

फॉलो-अप 3: साधारण एकतरफा BFS कब बेहतर होता है?

इसका उपयोग तब करें जब शब्दकोश छोटा हो, केवल एक समापन बिंदु ज्ञात हो, ग्राफ़ निर्देशित हो और रिवर्स पड़ोसी महंगे हों, या फ्रंटियर को कम करने की तुलना में कोड सरलता अधिक मायने रखती हो। एकतरफा BFS में कम इनवेरिएंट होते हैं और यह पैरेंट पुनर्निर्माण को सीधा बनाता है। यह इस Python प्रतिनिधित्व के लिए समान पड़ोसी जनरेटर और समान O(NL²) सीमा बनाए रखता है।

फॉलो-अप 4: आप वाइल्डकार्ड-पैटर्न बकेट कब बनाएंगे?

उन्हें तब बनाएं जब कई क्वेरीज़ एक स्थिर शब्दकोश साझा करती हैं, वर्णमाला बड़ी होती है, या प्रत्येक वर्णमाला प्रतिस्थापन उत्पन्न करने से कार्य बर्बाद होता है। शब्दकोश के साथ इंडेक्स को संस्करणित करें, अनुक्रमित नहीं होने पर प्रति क्वेरी beginWord पैटर्न शामिल करें, और प्रत्येक बकेट का प्रति खोज अधिकतम एक बार उपभोग करें। ट्रेड-ऑफ़ प्रीप्रोसेसिंग समय, बकेट मेमोरी और शब्द बदलने पर अमान्यकरण (invalidation) है।

फॉलो-अप 5: क्या होगा यदि विभिन्न अक्षर परिवर्तनों की लागत अलग-अलग हो?

ग्राफ़ भारित (weighted) हो जाता है, इसलिए BFS परतें अब न्यूनतम लागत का प्रतिनिधित्व नहीं करती हैं। गैर-नकारात्मक लागतों के लिए Dijkstra का उपयोग करें, समान अंतर्निहित पड़ोसियों को उत्पन्न करें लेकिन संचित लागत द्वारा फ्रंटियर को क्रमबद्ध करें। एक वैध स्वीकार्य अनुमानी (admissible heuristic) A* का समर्थन कर सकता है, लेकिन हैमिंग दूरी किसी भी शेष वर्ण परिवर्तन की लागत पर एक सिद्ध निचली सीमा द्वारा स्केल करने के बाद ही स्वीकार्य है।

फॉलो-अप 6: क्या होगा यदि वर्णमाला यूनिकोड हो या शब्दों की लंबाई अलग हो?

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

फॉलो-अप 7: आप एक इंटरव्यू में द्विदिशीय स्टॉप स्थिति को कैसे सिद्ध करेंगे?

प्रत्येक वर्तमान फ्रंटियर को उसके अपने समापन बिंदु से एक गहराई निर्दिष्ट करें। एल्गोरिदम प्रति पुनरावृत्ति ठीक एक पूर्ण गहराई परत को आगे बढ़ाता है। विस्तार से पहले, sequence_length दो फ्रंटियर गहराईयों का योग प्लस एक होता है। इसलिए विपरीत फ्रंटियर में उत्पन्न एक किनारा sequence_length + 1 शब्दों के साथ एक पथ बनाता है। यदि कोई छोटा पथ मौजूद होता, तो इसमें छोटे गहराई योग वाली दो परतों के बीच एक किनारा होता, और वे परतें पहले ही विस्तारित और जुड़ी होतीं। यह इस पहली फ्रंटियर मीटिंग होने का खंडन करता है।

फॉलो-अप 8: आप उदाहरणों से परे अनुकूलित खोज को कैसे मान्य करेंगे?

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