प्रॉम्प्ट और दायरा
add(task, priority), update(task, priority), remove(task), और pop() के साथ एक प्रायोरिटी क्यू लागू करें। समान प्राथमिकताओं को इंसर्शन क्रम में वापस किया जाना चाहिए; update और remove अमोर्टाइज़्ड O(log n) होने चाहिए। बताएं कि बासी हीप प्रविष्टियों (stale heap entries) को कैसे संभाला जाता है।
यह एक म्यूटेबल प्रायोरिटी क्यू की शुद्धता का परीक्षण करता है, न कि केवल यह कि क्या आप हीप API को कॉल कर सकते हैं। Python का heapq दस्तावेज़ स्थिर क्रमबद्धता (stable ordering), गैर-तुलनीय टास्क, प्राथमिकता अपडेट और पेंडिंग निष्कासन को कठिन भागों के रूप में उजागर करता है। एक सामान्य डिज़ाइन टाई के लिए काउंटर, स्थान के लिए एक मैप और हीप इनवेरिएंट को बनाए रखने के लिए लेज़ी डिलीशन का उपयोग करता है।
इंटरव्यूअर क्या परीक्षण कर रहा है
पहला, क्या आप पूरी हीप कुंजी लिख सकते हैं: प्राथमिकता, इंसर्शन अनुक्रम (sequence), और टास्क? दूसरा, क्या अपडेट और निष्कासन हीप को सीधे दूषित करने से बच सकते हैं? तीसरा, क्या आप डुप्लिकेट टास्क, एक खाली क्यू, एक बासी रूट और लंबे समय तक चलने वाली कचरा प्रविष्टियों को संभाल सकते हैं?
उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न
- क्या प्राथमिकताएं संख्याएं हैं या तुलनीय ऑब्जेक्ट्स? तुलनीय पूर्णांक मान लें, जिसमें छोटे मान पहले आते हैं।
- क्या टास्क ID अद्वितीय हैं? मान लें कि हाँ; डुप्लिकेट
addया तो एक अपडेट है या एक स्पष्ट त्रुटि। - क्या स्थिर क्रमबद्धता आवश्यक है? मान लें कि समान प्राथमिकताएं प्रथम-इंसर्शन क्रम का उपयोग करती हैं।
- क्या लेज़ी डिलीशन अस्थायी रूप से मेमोरी बनाए रख सकता है? हाँ, एक सफाई और पुनर्निर्माण (rebuild) नीति के साथ।
- क्या कॉल्स समवर्ती (concurrent) हैं? एकल थ्रेड मान लें; समवर्तीता के लिए बाहरी लॉक या सुरक्षित कंटेनर की आवश्यकता होती है।
30-सेकंड का उत्तर ढांचा
"मैं एक न्यूनतम-हीप (min-heap) में [priority, sequence, task] संग्रहीत करूँगा और प्रत्येक टास्क ID को उसकी वर्तमान मान्य प्रविष्टि से मैप करूँगा। एक अपडेट पुरानी प्रविष्टि को हटाया गया चिह्नित करता है और एक नए अनुक्रम के साथ एक नई प्रविष्टि सम्मिलित करता है; remove भी एक प्रविष्टि को बासी चिह्नित करता है। pop तब तक बासी प्रविष्टियों को छोड़ता है जब तक कि उसे वर्तमान प्रविष्टि नहीं मिल जाती। अनुक्रम स्थिर संबंध (ties) देता है, मैप O(1) लुकअप देता है, हीप संचालन O(log n) होते हैं, और आवधिक पुनर्निर्माण लेज़ी-एंट्री स्पेस को सीमित करता है।"
चरण-दर-चरण गहन विश्लेषण
चरण 1: इनवेरिएंट और ऑपरेशन अनुबंधों को परिभाषित करें
रूट मान्य प्रविष्टियों के बीच सबसे छोटा (priority, sequence) होना चाहिए। मैप प्रत्येक टास्क के लिए वर्तमान प्रविष्टि संग्रहीत करता है। किसी टास्क की अधिकतम एक मान्य प्रविष्टि होती है; बासी प्रविष्टियाँ हीप में रह सकती हैं लेकिन उन्हें कभी वापस नहीं किया जा सकता है। परिभाषित करें कि क्या एक खाली pop त्रुटि उत्पन्न करता है या एक खाली मान लौटाता है।
चरण 2: तुलनीय हीप प्रविष्टियाँ चुनें
[priority, sequence, task] का उपयोग करें। मोनोटोनिक sequence टास्क ऑब्जेक्ट्स की तुलना किए बिना समान प्राथमिकताओं को तुलनीय बनाता है। यदि व्यावसायिक प्राथमिकता दिशा उलट दी जाती है, तो इसे नकारें या एक कम्पेरेटर को लगातार लपेटें; परिचालनों के बीच नियमों को मिश्रित न करें।
चरण 3: add और update लागू करें
पहला add एक अनुक्रम आवंटित करता है और मैप और हीप दोनों में प्रविष्टि लिखता है। update अस्तित्व की पुष्टि करता है, पुरानी प्रविष्टि को REMOVED के रूप में चिह्नित करता है, एक नई प्रविष्टि सम्मिलित करता है, और मैप पॉइंटर को प्रतिस्थापित करता है। कोई हीप खोज या मैन्युअल शिफ्ट नहीं है, इसलिए ऑपरेशन O(log n) बना रहता है।
add(task, priority):
if task is active: mark old entry removed
entry = [priority, next(sequence), task]
current[task] = entry
heappush(heap, entry)चरण 4: लेज़ी डिलीशन के साथ remove लागू करें
remove मैप से टास्क को हटा देता है और उसकी हीप प्रविष्टि में टास्क फ़ील्ड को REMOVED से बदल देता है। ऐरे से सीधे हटाने से हीप टूट जाएगा और अतिरिक्त मरम्मत की आवश्यकता होगी। लेज़ी डिलीशन अस्थायी कचरे की कीमत पर प्रति म्यूटेशन एक ज्ञात प्रविष्टि को छूता है।
चरण 5: pop को बासी प्रविष्टियों को छोड़ने लायक बनाएं
बार-बार रूट को पॉप करें। यदि इसे REMOVED के रूप में चिह्नित किया गया है, तो जारी रखें। यदि मैप ठीक उस प्रविष्टि की ओर इशारा नहीं करता है जिसे पॉप किया जा रहा है, तो इसे एक अपडेट द्वारा हटा दिया गया था, इसलिए इसे छोड़ दें। एक मान्य प्रविष्टि के लिए, मैप कुंजी को हटा दें और टास्क लौटाएं। हीप समाप्त होने के बाद ही खाली-क्यू त्रुटि उत्पन्न करें।
चरण 6: जटिलता और अमोर्टाइज़्ड सीमाओं को सिद्ध करें
add, update, और remove एक हीप इंसर्शन या एक स्थिर-समय का अंकन निष्पादित करते हैं, जिससे O(log n) या O(1) अंकन मिलता है। प्रत्येक बासी प्रविष्टि को अधिकतम एक बार पॉप किया जाता है, इसलिए छोड़ा गया कार्य उस अपडेट या निष्कासन के लिए अमोर्टाइज़ हो जाता है जिसने इसे बनाया था। यदि बिना पॉप के अपडेट जारी रहते हैं, तो स्पेस बढ़ता है और पुनर्निर्माण की आवश्यकता होती है।
चरण 7: पुनर्निर्माण और स्थान नियंत्रण डिज़ाइन करें
जब हीप की लंबाई मान्य प्रविष्टियों के एक निश्चित गुणक (जैसे 2x) से अधिक हो जाती है, या बासी प्रविष्टियाँ एक सीमा को पार कर जाती हैं, तो मैप से वर्तमान प्रविष्टियों को बनाए रखें और हीप का पुनर्निर्माण करें। पुनर्निर्माण में O(n) लागत आती है, लेकिन कम-आवृत्ति वाले ट्रिगर अमोर्टाइज़्ड लागत को सीमित रखते हैं। एक ज्ञात टास्क सीमा के साथ, अपडेट के बैच के बाद भी सफाई चलाई जा सकती है।
चरण 8: सीमा परीक्षणों को कवर करें
एक खाली क्यू, स्थिर समान प्राथमिकताएं, बार-बार अपडेट, निष्कासन-फिर-पॉप, रूट तक पहुँचने वाली एक पुरानी अपडेट की गई प्रविष्टि, सभी प्रविष्टियों का बासी होना, गैर-तुलनीय टास्क ऑब्जेक्ट्स, और पुनर्निर्माण से पहले और बाद में समान परिणामों का परीक्षण करें। एक साधारण डिक्शनरी और सॉर्ट की गई सूची मॉडल के विरुद्ध यादृच्छिक परिचालनों का विभेदक-परीक्षण (differential-test) करें।
ट्रेड-ऑफ और सीमाएं
ट्रेड-ऑफ 1: लेज़ी डिलीशन या इंडेक्स किया गया हीप
लेज़ी डिलीशन एक सामान्य कार्यान्वयन के लिए संक्षिप्त और कम जोखिम वाला है। एक इंडेक्स किया गया हीप तुरंत हटा देता है और स्पेस को नियंत्रित करता है, लेकिन स्वैप के दौरान स्थिति बनाए रखना अधिक बग-प्रवण होता है। इंडेक्स किए गए हीप को केवल तभी चुनें जब डिलीट दर और मेमोरी सीमाएं इसे उचित ठहराती हों।
ट्रेड-ऑफ 2: क्या अनुक्रम ओवरफ्लो हो सकता है?
निश्चित-चौड़ाई वाले पूर्णांक रैप कर सकते हैं और स्थिर क्रमबद्धता को तोड़ सकते हैं। एक अनबाउंड पूर्णांक का उपयोग करें या एक सुरक्षित पुनर्निर्माण के दौरान सभी सक्रिय प्रविष्टियों को पुन: क्रमांकित करें। जब तक सक्रिय प्रविष्टियाँ अभी भी पुराने मानों पर निर्भर हैं, काउंटर को कभी रीसेट न करें।
ट्रेड-ऑफ 3: त्रुटि या खाली मान
लाइब्रेरी आमतौर पर एक स्पष्ट खाली-क्यू अपवाद उत्पन्न करती हैं, जिससे कॉलर "कोई टास्क नहीं" को ऐसे टास्क से अलग कर सकते हैं जिसका मान शून्य (null) है। यदि कोई API एक खाली मान लौटाता है, तो अस्पष्टता का दस्तावेजीकरण करें और एक परस्पर विरोधी टास्क मान की अनुमति न दें।
विफलता अभ्यास और विकास योजना
अभ्यास 1: एक टास्क को बार-बार अपडेट करें
एक टास्क को 10,000 बार अपडेट करें, फिर पॉप करें और सत्यापित करें कि नवीनतम प्राथमिकता ठीक एक बार वापस आ गई है। बासी-प्रविष्टि वृद्धि का निरीक्षण करें, एक पुनर्निर्माण ट्रिगर करें, और हीप इनवेरिएंट की पुन: जाँच करें।
अभ्यास 2: यादृच्छिक मिश्रित संचालन
यादृच्छिक add, update, remove, और pop संचालन उत्पन्न करें और डिक्शनरी प्लस सॉर्टेड-लिस्ट मॉडल के साथ तुलना करें। समान-प्राथमिकता अनुक्रम क्रम पर ध्यान केंद्रित करें और सुनिश्चित करें कि पुरानी अपडेट की गई प्रविष्टियाँ कभी लीक न हों।
अभ्यास 3: त्रुटियाँ और संसाधन सीमाएं
लापता टास्क के लिए update/remove को कॉल करें, एक खाली क्यू पॉप करें, और मेमोरी सीमा पर पुनर्निर्माण ट्रिगर करें। स्थिर त्रुटि प्रकारों को सत्यापित करें, कोई खोया हुआ टास्क नहीं, और कॉल करने वालों के लिए कोई आंशिक रूप से पुनर्निर्मित स्थिति उजागर नहीं होती है।
सामान्य गलतियाँ और अनुवर्ती कार्रवाई
गलती 1: केवल प्राथमिकता और टास्क संग्रहीत करना
टास्क ऑब्जेक्ट तुलनीय नहीं हो सकते हैं, जिससे समान-प्राथमिकता तुलना विफल हो सकती है। एक स्थिर अनुक्रम या एक गैर-तुलनीय रैपर जोड़ें।
गलती 2: अपडेट के लिए हीप प्रविष्टि को इन-प्लेस म्यूटेट करना
प्रविष्टि अब सही स्थिति में नहीं हो सकती है, जो हीप इनवेरिएंट का उल्लंघन करती है। पुरानी प्रविष्टि को बासी चिह्नित करें और एक नई प्रविष्टि सम्मिलित करें।
गलती 3: हटाने के लिए ऐरे remove को कॉल करना
खोज O(n) है, जिसके बाद हीप मरम्मत होती है। प्रविष्टि का पता लगाने और उसे बासी चिह्नित करने के लिए मैप का उपयोग करें।
गलती 4: pop में केवल टास्क फ़ील्ड की जाँच करना
एक पुरानी अपडेट की गई प्रविष्टि अभी भी वही टास्क ID ले जा सकती है। पुष्टि करें कि पॉप किया गया ऑब्जेक्ट वर्तमान मैप प्रविष्टि है।
गलती 5: बासी-प्रविष्टि स्थान की अनदेखी करना
लेज़ी डिलीशन अभी भी मेमोरी की खपत करता है। एक पुनर्निर्माण सीमा निर्धारित करें और हीप की लंबाई, मान्य-प्रविष्टि गणना और बासी अनुपात की निगरानी करें।
गलती 6: प्राथमिकता दिशा को अंतर्निहित छोड़ना
एक न्यूनतम-हीप सबसे छोटा मान पहले लौटाता है। यदि बड़ी संख्याओं का अर्थ उच्च व्यावसायिक प्राथमिकता है, तो अनुबंध में रूपांतरण को परिभाषित करें ताकि add और pop सहमत हों।