कोडिंग इंटरव्यू: टोपोलॉजिकल सॉर्ट के साथ Alien Dictionary को हल करें

प्रॉम्प्ट और लागू संदर्भ

गैर-रिक्त लोअरकेस ASCII स्ट्रिंग्स की एक सरणी words दी गई है, मान लें कि यह सरणी किसी अज्ञात वर्णमाला द्वारा सॉर्ट की गई बताई गई है। कोई भी ऐसा क्रम लौटाएं जिसमें इनपुट का प्रत्येक अलग वर्ण ठीक एक बार हो और जो शब्द सूची को सॉर्टेड बनाए। जब ऐसा कोई क्रम मौजूद न हो तो एक खाली स्ट्रिंग लौटाएं। यदि कई वर्णमालाएं काम करती हैं, तो कोई भी स्वीकार्य है।

साक्षात्कार संस्करण के लिए, अधिकतम 10,000 शब्द और कुल मिलाकर अधिकतम 100,000 वर्ण मान लें। ये अभ्यास की सीमाएं हैं, किसी विशेष प्लेटफ़ॉर्म की सीमाएं नहीं। ["wrt", "wrf", "er", "ett", "rftt"] के लिए, एक उत्तर "wertf" है। सूची ["abc", "ab"] असंभव है क्योंकि एक लंबा शब्द अपने स्वयं के उपसर्ग से पहले आता है। सूची ["z", "x", "z"] असंभव है क्योंकि यह z < x और x < z दोनों को दर्शाती है।

कठिन भाग टोपोलॉजिकल सॉर्ट से पहले आता है। इनपुट सॉर्ट किए गए शब्द प्रदान करता है; ग्राफ़ किनारों का अनुमान लगाया जाना चाहिए। एक सही समाधान को लेक्सिकोग्राफिक तुलना द्वारा उचित बाधाओं का सटीक अनुमान लगाना चाहिए, उन वर्णों को बनाए रखना चाहिए जिनके पास कोई किनारा नहीं है, और एक अमान्य उपसर्ग को एक निर्देशित चक्र से अलग करना चाहिए।

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

पहला संकेत यह है कि क्या उम्मीदवार दो आसन्न शब्दों के पहले भिन्न वर्ण से एक किनारा प्राप्त करता है। यदि "wrt", "wrf" से पहले दिखाई देता है, तो तुलना t < f को साबित करती है। उस पहले अंतर के बाद के वर्ण इस युग्म के बारे में कुछ भी प्रकट नहीं करते हैं क्योंकि लेक्सिकोग्राफिक तुलना पहले ही तय हो चुकी है।

दूसरा संकेत उपसर्ग तर्क है। जब तुलना किए गए सभी वर्ण मेल खाते हैं, तो छोटा शब्द पहले आना चाहिए। "abc" से पहले "ab" कोई किनारा नहीं जोड़ता है और मान्य रहता है; "ab" से पहले "abc" प्रत्येक संभावित वर्णमाला का खंडन करता है। केवल टोपोलॉजिकल सॉर्टिंग इस विरोधाभास को नहीं खोज सकती क्योंकि यह कोई किनारा नहीं बनाता है।

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

अंतिम संकेत प्रमाण और सत्यापन हैं। काह्न का एल्गोरिदम (Kahn's algorithm) केवल तभी एक पूर्ण क्रम लौटाता है जब वह प्रत्येक नोड को हटा देता है। एक छोटा आउटपुट यह साबित करता है कि एक चक्र शेष है। कई शून्य-इन-डिग्री विकल्पों का मतलब है कि साक्ष्य एक अद्वितीय वर्णमाला निर्धारित नहीं करता है; यह आधार अनुबंध के तहत मान्य है और इसे त्रुटि के रूप में गलत लेबल नहीं किया जाना चाहिए।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

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

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

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

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

मान लें कि C सभी शब्दों में वर्णों की कुल संख्या है, U अलग वर्णों की संख्या है, और E अलग-अलग पूर्वता किनारों की संख्या है। आने वाले प्रत्येक वर्ण के लिए graph[ch] को एक सेट के रूप में और indegree[ch] को शून्य के रूप में इनिशियलाइज़ करें। शब्दों की तुलना करने से पहले यह इनिशियलाइज़ेशन आवश्यक है: एक वर्ण मान्य और अबाधित हो सकता है, इसलिए केवल किनारे के अंतिम बिंदु नोड सेट को परिभाषित नहीं करते हैं।

केवल आसन्न शब्दों की तुलना करें। आसन्न तुलनाएं पर्याप्त हैं क्योंकि यह साबित करना कि प्रत्येक पड़ोसी युग्म क्रमित है, यह साबित करता है कि पूरी सूची संक्रामकता द्वारा क्रमित है। वे शब्द-युग्म तुलनाओं की द्विघात (quadratic) संख्या से भी बचते हैं। एक युग्म first और second के लिए, छोटी लंबाई तक मिलान करने वाले स्थानों का निरीक्षण करें:

1. पहले बेमेल first[i] != second[i] पर, first[i] -> second[i] जोड़ें और उस युग्म की तुलना करना बंद करें।
2. यदि प्रत्येक साझा स्थान मेल खाता है और first लंबा है, तो एक खाली स्ट्रिंग लौटाएं।
3. यदि प्रत्येक साझा स्थान मेल खाता है और first लंबा नहीं है, तो कोई किनारा न जोड़ें।

केवल एक नया सम्मिलित किनारा ही गंतव्य की इन-डिग्री को बढ़ाता है। मान लीजिए "za" < "zb" और "ca" < "cb" दोनों a -> b का संकेत देते हैं। उस किनारे को दो बार गिनने से a को हटाए जाने के बाद b धनात्मक इन-डिग्री के साथ रह जाएगा और गलत तरीके से एक चक्र की रिपोर्ट करेगा।

काह्न का एल्गोरिदम प्रत्येक शून्य-इन-डिग्री वर्ण को एक कतार (queue) में रखता है। इसका अपरिवर्तनीय (invariant) है: प्रत्येक असंसाधित वर्ण के लिए, इन-डिग्री अन्य असंसाधित वर्णों से आने वाले किनारों की संख्या के बराबर होती है; कतार में सटीक रूप से ऐसे वर्ण होते हैं जिनका कोई पूर्ववर्ती नहीं होता। कतारबद्ध वर्ण को हटाना सुरक्षित है। प्रत्येक आउटगोइंग पड़ोसी को घटाना उन किनारों को हटाने का मॉडल बनाता है, और एक पड़ोसी कतार में तब प्रवेश करता है जब उसका अंतिम अधूरा पूर्ववर्ती गायब हो जाता है।

from collections import deque


def alien_order(words: list[str]) -> str:
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for first, second in zip(words, words[1:]):
        limit = min(len(first), len(second))

        for index in range(limit):
            before = first[index]
            after = second[index]
            if before == after:
                continue

            if after not in graph[before]:
                graph[before].add(after)
                indegree[after] += 1
            break
        else:
            if len(first) > len(second):
                return ""

    ready = deque(
        char for char, degree in indegree.items() if degree == 0
    )
    order: list[str] = []

    while ready:
        char = ready.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)

    return "".join(order) if len(order) == len(indegree) else ""

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

यदि एल्गोरिदम U से कम वर्ण आउटपुट करता है, तो प्रत्येक शेष नोड की इन-डिग्री धनात्मक होती है। किसी भी शेष नोड से शुरू करके और बार-बार एक इनकमिंग किनारे का अनुसरण करने पर एक सीमित ग्राफ़ में एक नोड पर दोबारा आना होगा; दोहराया गया खंड एक निर्देशित चक्र है। कोई भी रैखिक वर्णमाला उस चक्र को संतुष्ट नहीं कर सकती है। इसके विपरीत, एक अचक्रीय (acyclic) ग्राफ़ में हमेशा एक शून्य-इन-डिग्री नोड होता है, इसलिए काह्न का एल्गोरिदम अंततः सभी नोड्स को हटा देता है और एक मान्य क्रम लौटाता है।

सभी नोड्स का निर्माण और आसन्न शब्दों को स्कैन करने में O(C) समय लगता है। काह्न के एल्गोरिदम द्वारा प्रत्येक अलग नोड और किनारे को एक बार संसाधित किया जाता है, इसलिए कुल समय O(C + U + E) है और अतिरिक्त स्थान O(U + E) है। लोअरकेस ASCII के साथ, U अधिकतम 26 है, लेकिन प्रतीकात्मक सीमा को बनाए रखने से तर्क पुन: प्रयोज्य हो जाता है।

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

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

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

"मुझे पहले सॉर्ट किए गए शब्दों से आंशिक क्रम का अनुमान लगाना होगा। मैं प्रत्येक वर्ण के लिए एक नोड बनाता हूँ, जिसमें वे वर्ण भी शामिल हैं जो कभी किसी किनारे में भाग नहीं लेते हैं। प्रत्येक पड़ोसी युग्म के लिए, मैं पहले बेमेल होने तक स्कैन करता हूँ। यदि युग्म wrt और wrf है, तो मैं t -> f जोड़ता हूँ और रुक जाता हूँ क्योंकि बाद के स्थान उस तुलना को प्रभावित नहीं कर सकते हैं। यदि कोई बेमेल नहीं है और पहला शब्द लंबा है, जैसे कि ab से पहले abc, तो इनपुट पहले से ही असंगत है।

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

यदि आउटपुट लंबाई अलग वर्णों की संख्या के बराबर है, तो प्रत्येक अनुमानित किनारे का सम्मान किया जाता है। वे किनारे और उपसर्ग जांच प्रत्येक आसन्न शब्द युग्म को क्रमित बनाते हैं, इसलिए पूरी सूची क्रमित होती है। यदि लंबाई कम है, तो शेष ग्राफ़ में एक चक्र होता है और कोई वर्णमाला काम नहीं करती है। रनटाइम O(U + E) स्थान के साथ O(C + U + E) है। मैं इसके उपसर्ग से पहले एक लंबे शब्द, दो-किनारे वाले चक्र, एक किनारे के लिए डुप्लिकेट साक्ष्य, एक एकल शब्द, और कई मान्य आउटपुट वाले मामले का परीक्षण करूंगा; अंतिम मामले के लिए मैं एक स्ट्रिंग की अपेक्षा करने के बजाय क्रमबद्ध गुणों को मान्य करूंगा।"

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

• शब्द युग्म में प्रत्येक भिन्न स्थान का उपयोग करना → एक बार जब पहला बेमेल लेक्सिकोग्राफिक क्रम तय कर लेता है तो बाद के स्थान भाग नहीं लेते हैं → केवल पहले-बेमेल किनारे को जोड़ें और रुकें।
• केवल टोपोलॉजिकल सॉर्ट चलाना → "ab" से पहले "abc" कोई किनारा नहीं बनाता है और छूट जाता है → युग्म तुलना के दौरान उपसर्ग-से-पहले-लंबे-शब्द के विरोधाभास की जांच करें।
• केवल किनारों को जोड़ते समय नोड बनाना → पृथक वर्ण उत्तर से गायब हो जाते हैं → प्रत्येक देखे गए वर्ण के लिए एक नोड इनिशियलाइज़ करें।
• डुप्लिकेट किनारों के लिए इन-डिग्री बढ़ाना → एक मान्य नोड कभी शून्य तक नहीं पहुंचता है → एक आसन्नता सेट का उपयोग करें और केवल पहले सम्मिलन पर बढ़ाएं।
• कतार खाली होने पर आंशिक परिणाम लौटाना → चक्रीय बाधाएं सफल दिखाई देती हैं → आउटपुट लंबाई को अलग-अलग वर्णों की संख्या के बराबर होना आवश्यक बनाएं।
• एक निश्चित उत्तर की मांग करना → मान्य आंशिक आदेशों में कई रैखिक विस्तार हो सकते हैं → वर्णों, किनारों और शब्द तुलनाओं के विरुद्ध लौटाए गए क्रम का परीक्षण करें।
• प्रत्येक शब्द युग्म की तुलना करना → शब्दों की संख्या में कार्य द्विघात हो सकता है → क्रमबद्ध क्रम स्थापित करने के लिए आसन्न तुलनाएं पर्याप्त हैं।
• यह दावा करना कि अस्पष्टता का अर्थ अमान्य इनपुट है → कई वर्णमालाएं एक ही साक्ष्य की व्याख्या कर सकती हैं → कोई भी मान्य क्रम लौटाएं जब तक कि विशिष्टता अनुबंध का हिस्सा न हो।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: आप कैसे निर्धारित करते हैं कि वर्णमाला अद्वितीय है या नहीं?

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

फॉलो-अप 2: आप सामान्य वर्ण क्रम के तहत सबसे छोटा मान्य परिणाम कैसे लौटाते हैं?

कतार को होस्ट भाषा के वर्ण क्रम द्वारा कुंजीकृत न्यूनतम हीप (min-heap) से बदलें। वर्तमान में मान्य सबसे छोटे वर्ण को चुनने से लालची विनिमय तर्क (greedy exchange argument) द्वारा सबसे छोटा रैखिक विस्तार उत्पन्न होता है। समय O(C + E + U log U) हो जाता है; स्पष्ट रूप से बताएं कि यह टाई-ब्रेकर एलियन वर्णमाला के लिए बाहरी है।

फॉलो-अप 3: आप अमान्य इनपुट के लिए एक उपयोगी स्पष्टीकरण कैसे लौटाएंगे?

उपसर्ग विरोधाभास के लिए, दो आसन्न शब्द और उनके सूचकांक लौटाएं। एक चक्र के लिए, काह्न के रुकने के बाद शेष ग्राफ़ पर तीन-रंग का DFS चलाएं, पैरेंट पॉइंटर्स रखें, और एक बैक-एज चक्र बनाने वाले वर्णों का पुनर्निर्माण करें। एक संरचित परिणाम खाली स्ट्रिंग को ओवरलोड किए बिना invalid_prefix, cycle, और valid के बीच अंतर कर सकता है।

फॉलो-अप 4: क्या आप शब्द सूची को एक स्ट्रीम के रूप में संसाधित कर सकते हैं?

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

फॉलो-अप 5: आप प्रत्येक मान्य वर्णमाला की गणना कैसे करेंगे?

सभी वर्तमान शून्य-इन-डिग्री वर्णों पर बैकट्रैक करें। एक चुनें, उसके आउटगोइंग किनारों को हटाएं, रिकर्स करें, फिर स्थिति को पुनर्स्थापित करें। यह केवल मान्य आदेशों की गणना करता है, लेकिन आउटपुट U! तक पहुंच सकता है; इसे लागू करने से पहले एक छोटी वर्णमाला या आउटपुट सीमा की पुष्टि करें।

फॉलो-अप 6: यूनिकोड शब्दों के लिए क्या बदलता है?

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