कोडिंग इंटरव्यू: मैक्स हीप के साथ न्यूनतम रीफ्यूलिंग स्टॉप्स

प्रॉम्प्ट और संदर्भ

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

इंटरव्यूअर क्या मूल्यांकन करता है

• क्या आप "केवल आवश्यक होने पर रीफ्यूल करें" को एक लेज़ी ग्रीडी रणनीति में बदलते हैं।
• क्या आप यह सिद्ध करते हैं कि सबसे बड़ा पार किया गया ईंधन लेने से इष्टतम (optimal) स्टॉप गणना नहीं बढ़ सकती है।
• क्या आप शुरुआत, लक्ष्य, डुप्लिकेट स्थितियों और अगम्य मामलों को संभालते हैं।
• क्या आप O(n log n) समय और O(n) स्पेस कार्यान्वयन प्रदान करते हैं।

स्पष्टीकरण के प्रश्न

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

30-सेकंड उत्तर रूपरेखा

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

चरण-दर-चरण समाधान

1. पहुँच योग्यता इन्वेरिएंट स्थापित करें

स्थिति p पर, हीप में p पर या उससे पहले के प्रत्येक स्टेशन का ईंधन होता है, जबकि fuel अप्रयुक्त मात्रा है। यदि ईंधन की मात्रा ऋणात्मक है, तो उन स्टेशनों में से किसी एक का उपयोग किए बिना आगे बढ़ना असंभव है। प्रत्येक पॉप पहुँच योग्य सीमा का विस्तार करता है जब तक कि ईंधन की मात्रा फिर से गैर-ऋणात्मक न हो जाए।

2. लेज़ी ग्रीडी विकल्प को सिद्ध करें

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

3. लक्ष्य को एक सीमा के रूप में मानें

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

4. हीप को लागू करें

Python का heapq एक मिन हीप है, इसलिए ऋणात्मक ईंधन मान एक मैक्स हीप का अनुकरण करते हैं। प्रत्येक स्टेशन को एक बार पुश किया जाता है और केवल तभी पॉप किया जाता है जब स्टॉप की आवश्यकता होती है:

import heapq

def min_refuel_stops(target, start_fuel, stations):
    fuel = start_fuel
    previous = 0
    max_heap = []
    stops = 0

    for position, station_fuel in [*stations, (target, 0)]:
        fuel -= position - previous
        while fuel < 0 and max_heap:
            fuel += -heapq.heappop(max_heap)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(max_heap, -station_fuel)
        previous = position
    return stops

5. जटिलता और सीमाओं का विश्लेषण करें

n स्टेशनों के साथ, प्रत्येक ईंधन मान हीप में अधिकतम एक बार प्रवेश करता है और बाहर निकलता है, जिससे O(n log n) समय और O(n) हीप स्पेस मिलता है। पर्याप्त प्रारंभिक ईंधन, एक अगम्य पहला स्टेशन, अंतिम स्टेशन के बाद आवश्यक स्टॉप, शून्य ईंधन, डुप्लिकेट स्थितियाँ, एक सटीक लक्ष्य आगमन, और एक अगम्य लक्ष्य का परीक्षण करें।

मॉडल उच्च-गुणवत्ता वाला उत्तर

मैं लक्ष्य को शून्य-ईंधन वाले वर्चुअल स्टेशन के रूप में जोड़ूँगा। स्कैन के दौरान, यात्रा की दूरी घटाएँ और पहले से पहुँचे जा चुके स्टेशनों से ईंधन पुश करें। जब भी शेष ईंधन ऋणात्मक हो, एक स्टॉप अनिवार्य हो जाता है; जब तक वर्तमान स्थिति तक पहुँचना संभव न हो जाए, बार-बार सबसे बड़ा ऐतिहासिक ईंधन लें। एक खाली हीप का अर्थ -1 है। विनिमय प्रमाण किसी भी चुने गए छोटे पार किए गए ईंधन को स्टॉप्स बढ़ाए बिना या भविष्य की पहुँच योग्यता को कम किए बिना एक बड़े उपलब्ध ईंधन से बदल देता है। प्रत्येक स्टेशन को अधिकतम एक बार पुश और पॉप किया जाता है, इसलिए जटिलता O(n log n) समय और O(n) स्पेस है।

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

• निर्णय में देरी करने के बजाय प्रत्येक स्टेशन पर तुरंत रीफ्यूल करना।
• केवल स्टेशन-से-स्टेशन अंतराल की जाँच करना और अंतिम लक्ष्य अंतराल को भूल जाना।
• वर्तमान अप्रयुक्त ईंधन को हीप में उपलब्ध ईंधन के साथ मिलाना।
• मिन हीप का उपयोग करना और सबसे छोटी मात्रा लेना।
• किसी स्टेशन पर पहुँचने से पहले उसे जोड़ना और भविष्य के ईंधन का पहले ही उपयोग करना।
• केवल पहुँच योग्य उदाहरणों का परीक्षण करना और खाली-हीप या संख्यात्मक सीमाओं को छोड़ देना।

फॉलो-अप प्रश्न

प्रत्येक स्टेशन पर अधिकतम क्यों न लें?

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

यदि आंशिक रीफ्यूलिंग की अनुमति हो तो क्या बदलता है?

स्थिति और लागत फलन (cost function) बदल जाते हैं। कीमतें या टैंक क्षमता मायने रख सकती है, इसलिए किसी स्टेशन का पूरा ईंधन लेने का प्रमाण अब सीधे लागू नहीं होता है।

डुप्लिकेट स्थितियाँ क्यों काम करती हैं?

उनकी दूरी शून्य है, इसलिए उन्हें किसी भी क्रम में पुश किया जा सकता है। जब बाद के खंड को वास्तव में ईंधन की आवश्यकता होती है, तो हीप अभी भी सबसे बड़ी उपलब्ध मात्रा प्रस्तुत करता है।

आप वास्तविक स्टॉप्स कैसे लौटाएँगे?

प्रत्येक हीप मान के साथ स्टेशन इंडेक्स संग्रहीत करें और जब भी इसे पॉप किया जाए तो इंडेक्स रिकॉर्ड करें। मार्ग के पुनर्निर्माण के लिए रिकॉर्ड किए गए इंडेक्स को स्थिति या चयन क्रम के अनुसार सॉर्ट करें।