कोडिंग इंटरव्यू: आप K सॉर्टेड लिंक्ड लिस्ट्स को कैसे मर्ज करते हैं?

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

lists सिंग्ली लिंक्ड लिस्ट्स के हेड्स वाले एक ऐरे k को देखते हुए, प्रत्येक नोड को एक ऐसी लिस्ट में मर्ज करें जिसके मान गैर-घटते क्रम में हों। कोई भी इनपुट लिस्ट खाली हो सकती है, मान नकारात्मक या डुप्लिकेट हो सकते हैं, और सभी इनपुट में नोड्स की कुल संख्या N है।

मान लें कि प्रत्येक इनपुट अचक्रीय (acyclic) है, पहले से सॉर्टेड है, और किसी अन्य इनपुट के साथ कोई नोड साझा नहीं करता है। कार्यान्वयन मौजूदा नोड्स को फिर से लिंक कर सकता है और प्रत्येक मान के लिए एक नया नोड आवंटित नहीं करना चाहिए। विभिन्न इनपुट लिस्ट्स में समान मानों का कोई आवश्यक क्रम नहीं है। जब ऐरे खाली हो या प्रत्येक हेड None हो तो None लौटाएं। O(N log k) समय और O(k) सहायक स्पेस का लक्ष्य रखें।

Input:
  1 -> 4 -> 5
  1 -> 3 -> 4
  2 -> 6

Output:
  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

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

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

पहला संकेत यह है कि क्या उम्मीदवार सॉर्ट की गई संरचना का उपयोग करता है। सभी मानों को फ़्लैट करना और उन्हें सॉर्ट करना काम करता है, लेकिन इसमें O(N log N) समय और O(N) अतिरिक्त स्टोरेज खर्च होता है। प्रत्येक आउटपुट नोड के लिए सभी मौजूदा हेड्स को स्कैन करने से सॉर्ट किए गए गुण का उपयोग होता है लेकिन इसमें O(Nk) की लागत आती है। एक मजबूत उत्तर यह पूछता है कि कौन सा छोटा सेट अगला वैश्विक न्यूनतम (global minimum) रख सकता है।

दूसरा संकेत फ़्रंटियर इनवेरिएंट है। प्रत्येक गैर-समाप्त (non-exhausted) लिस्ट के लिए, केवल उसका पहला अनमर्ज्ड नोड ही अगला आउटपुट हो सकता है। प्रत्येक गहरा नोड कम से कम उतना ही बड़ा होता है क्योंकि वह लिस्ट सॉर्ट की गई होती है। इसलिए प्रति गैर-समाप्त लिस्ट में एक फ़्रंटियर नोड रखने वाला मिन-हीप अधिकतम k उम्मीदवारों पर स्कैन को अधिकतम k आकार के हीप पर न्यूनतम निष्कासन (removal) और सम्मिलन (insertion) में कम कर देता है।

तीसरा संकेत प्रमाण और लेखांकन है। उत्तर में यह बताया जाना चाहिए कि चयनित नोड विश्व स्तर पर न्यूनतम क्यों है, केवल इसके उत्तराधिकारी (successor) को पुश करने से इनवेरिएंट क्यों रीस्टोर होता है, प्रत्येक नोड को ठीक एक बार क्यों उत्सर्जित किया जाता है, और हीप कभी भी गैर-खाली लिस्ट्स की संख्या से अधिक क्यों नहीं होता है। उस तर्क के बिना "प्राथमिकता कतार (priority queue) का उपयोग करें" कहने से मुख्य तर्क अधूरा रह जाता है।

चौथा संकेत कार्यान्वयन अनुशासन है। Python में, समान संख्यात्मक प्राथमिकताओं वाले हीप प्रविष्टियों को ListNode ऑब्जेक्ट्स की तुलना करने के लिए आगे नहीं बढ़ना चाहिए। एक अद्वितीय अनुक्रम संख्या (sequence number) टाई-ब्रेकर प्रदान करती है। जब नोड्स का पुन: उपयोग किया जाता है, तो कोड नोड को अलग करने और जोड़ने से पहले मूल उत्तराधिकारी को सहेजता है, इसलिए निर्मित उपसर्ग का एक स्पष्ट स्वामी होता है और यह अनमर्ज्ड लिस्ट में एक अस्थायी पॉइंटर को बनाए नहीं रखता है।

अंतिम संकेत दो इष्टतम दृष्टिकोणों के बीच चयन करना है। एक मिन-हीप और संतुलित जोड़ीदार मर्जिंग (balanced pairwise merging) दोनों O(N log k) समय प्राप्त करते हैं। हीप फ़्रंटियर को स्पष्ट बनाता है और स्वाभाविक रूप से इटरेटर्स या स्ट्रीम्स तक विस्तारित होता है। डिवाइड-एंड-कॉन्कर साधारण दो-लिस्ट मर्जिंग का उपयोग करता है और हेड्स के ऐरे से परे स्थिर पॉइंटर वर्कस्पेस का उपयोग कर सकता है। इनपुट अनुबंध तय करता है कि कौन सा स्पष्टीकरण सरल है।

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

• क्या मैं इनपुट नोड्स को म्यूटेट और पुन: उपयोग कर सकता हूँ? यदि हाँ, तो उन्हें पुनः लिंक करें और केवल O(k) हीप स्टोरेज का उपयोग करें। यदि नहीं, तो आउटपुट आवंटित करें और इसके O(N) स्पेस को सहायक एल्गोरिथम स्थिति से अलग रिपोर्ट करें।
• क्या सभी इनपुट सॉर्टेड और अचक्रीय हैं? बताया गया एल्गोरिदम दोनों पर निर्भर करता है। सॉर्टेडनेस को मान्य करने में O(N) की लागत आती है; साइकिल का पता लगाने से भी कार्य बदल जाता है और इसे चुपचाप बेस समाधान में नहीं जोड़ा जाना चाहिए।
• k क्या गिनता है? मान लें कि m गैर-खाली लिस्ट्स की संख्या है। हीप में अधिकतम m होता है, इसलिए अधिक सटीक सीमा O(N log m) के लिए m >= 2 है, जिसमें शून्य या एक गैर-खाली लिस्ट के लिए रैखिक कार्य होता है।
• क्या समान मानों को क्रॉस-लिस्ट क्रम बनाए रखना चाहिए? बेस प्रश्न के लिए केवल सॉर्ट किए गए मानों की आवश्यकता होती है। एक स्थिर अनुबंध के लिए हीप कुंजी में एन्कोड किए गए एक परिभाषित स्रोत क्रम की आवश्यकता होती है।
• क्या मैं भाषा की प्राथमिकता कतार (priority queue) का उपयोग कर सकता हूँ? आमतौर पर हाँ, जब तक कि इंटरव्यूअर अलग से हीप कार्यान्वयन का परीक्षण नहीं कर रहा हो। स्क्रैच से बाइनरी हीप लिखने में इंटरव्यू का समय बिताने से पहले स्पष्ट करें।
• क्या ये पूरी तरह से मटेरियलाइज्ड लिंक्ड लिस्ट्स हैं या लेज़ी इटरेटर्स हैं? एक हीप दोनों को संभालता है, लेकिन एक इटरेटर संस्करण को स्रोत को तब तक आगे बढ़ाने से बचना चाहिए जब तक कि उसका वर्तमान मान हटा न दिया जाए।
• इनपुट हेड ऐरे का क्या होना चाहिए? नीचे दिया गया कोड ऐरे प्रविष्टियों को अछूता छोड़ देता है लेकिन उनके नोड्स को फिर से जोड़ता है। यदि कॉलर दोनों को देखता है, तो उस स्वामित्व हस्तांतरण का दस्तावेजीकरण करें।

30-सेकंड उत्तर फ्रेमवर्क

“प्रत्येक सॉर्टेड लिस्ट का केवल पहला अनमर्ज्ड नोड ही अगला वैश्विक न्यूनतम हो सकता है, इसलिए मैं उन फ़्रंटियर नोड्स को मिन-हीप में रखूँगा। मैं सबसे छोटे नोड को पॉप करता हूँ, इसे परिणाम में जोड़ता हूँ, फिर केवल इसके सहेजे गए उत्तराधिकारी को पुश करता हूँ। इनवेरिएंट यह है कि हीप में प्रत्येक गैर-समाप्त लिस्ट से ठीक एक फ़्रंटियर होता है; इसलिए पॉप किया गया नोड सुरक्षित है, और इसके स्रोत फ़्रंटियर को रीस्टोर करने से इनवेरिएंट बना रहता है। N नोड्स में से प्रत्येक को एक बार पॉप किया जाता है और अधिकतम एक उत्तराधिकारी को पुश किया जाता है, जिसमें अधिकतम हीप आकार k होता है, जो O(N log k) समय और O(k) सहायक स्पेस देता है। मैं नोड्स का पुन: उपयोग करूँगा, एक अद्वितीय टाई-ब्रेकर जोड़ूँगा ताकि समान मान कभी भी नोड ऑब्जेक्ट्स की तुलना न करें, और खाली इनपुट, डुप्लिकेट, नेगेटिव, असमान लंबाई और एक लिस्ट का परीक्षण करूँगा। संतुलित जोड़ीदार मर्जिंग समान समय सीमा के साथ मुख्य विकल्प है।”

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

सीधे विकल्पों के साथ शुरुआत करें और बार-बार होने वाले काम की पहचान करें:

अनुक्रमिक मर्जिंग (Sequential merging) को कम आंकना आसान है। यदि k लिस्ट्स की लंबाई L समान है, तो काम 2L + 3L + ... + kL की तरह बढ़ता है, जो कि O(Lk²) है। चूंकि N = Lk, वह O(Nk) है। जोड़ीदार मर्जिंग राउंड में लिस्ट्स को मिलाकर असंतुलित संचयक से बचाती है, इसलिए प्रत्येक नोड अधिकतम ceil(log₂ k) मर्ज स्तरों में भाग लेता है।

हीप समाधान के लिए, प्रत्येक निष्कासन से पहले इस इनवेरिएंट को बनाए रखें:

For each non-exhausted input list:
  the heap contains exactly its first unmerged node.

For each exhausted input list:
  the heap contains no node from that list.

The result contains every previously removed node exactly once,
in non-decreasing order.

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

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

निम्नलिखित Python कार्यान्वयन दूसरे टपल फ़ील्ड के रूप में मोनोटोनिक रूप से बढ़ती अनुक्रम संख्या का उपयोग करता है। वह संख्या अद्वितीय है, इसलिए समान मान कभी भी टपल तुलना को गैर-क्रमबद्ध (non-orderable) नोड ऑब्जेक्ट तक पहुँचने का कारण नहीं बनते हैं।

from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count


@dataclass
class ListNode:
    val: int
    next: ListNode | None = None


def merge_k_lists(lists: list[ListNode | None]) -> ListNode | None:
    heap: list[tuple[int, int, ListNode]] = []
    sequence = count()

    for head in lists:
        if head is not None:
            heappush(heap, (head.val, next(sequence), head))

    dummy = ListNode(0)
    tail = dummy

    while heap:
        _, _, node = heappop(heap)
        next_node = node.next
        node.next = None
        tail.next = node
        tail = node

        if next_node is not None:
            heappush(heap, (next_node.val, next(sequence), next_node))

    return dummy.next

यहाँ m प्रारंभिक सम्मिलन हैं, जहाँ m <= k गैर-खाली लिस्ट्स की संख्या है। प्रत्येक नोड को एक बार हटाया जाता है, और अंतिम टेल को छोड़कर प्रत्येक नोड एक सम्मिलन का कारण बन सकता है। हीप संचालन में O(log m) की लागत आती है जबकि हीप में अधिकतम m प्रविष्टियाँ होती हैं। m >= 2 के लिए, कुल समय O(N log m) है, जिसे पारंपरिक रूप से O(N log k) के रूप में कहा जाता है; m <= 1 के लिए, ट्रैवर्सल O(N) है। हीप, सीक्वेंस काउंटर, डमी और पॉइंटर्स O(m) सहायक स्पेस का उपयोग करते हैं। लौटाए गए नोड्स मूल नोड्स हैं, इसलिए वे नए एल्गोरिथम स्टोरेज के बजाय आउटपुट हैं।

node.next को अलग करना उत्तराधिकारी को खोजने के लिए आवश्यक नहीं है क्योंकि इसे पहले सहेजा गया था। यह स्वामित्व को स्पष्ट बनाता है: मर्ज किया गया उपसर्ग कभी भी अस्थायी रूप से ऐसे स्रोत लिस्ट की ओर इंगित नहीं करता है जिसने अभी तक हीप नहीं जीता है। अगला परिशिष्ट टेल के उत्तराधिकारी को असाइन करता है। एल्गोरिथ्म कभी भी मान नहीं बदलता है और अचक्रीय, असंयुक्त-इनपुट अनुबंध के तहत एक ही नोड को दो बार कभी सम्मिलित नहीं करता है।

ऐसे परीक्षण चलाएँ जो संरचना को लक्षित करते हैं, केवल एक हैप्पी-पाथ ऐरे को नहीं:

def build(values: list[int]) -> ListNode | None:
    dummy = ListNode(0)
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next


def values(head: ListNode | None) -> list[int]:
    result: list[int] = []
    while head is not None:
        result.append(head.val)
        head = head.next
    return result


cases = [
    ([], []),
    ([[]], []),
    ([[1, 4, 5], [1, 3, 4], [2, 6]], [1, 1, 2, 3, 4, 4, 5, 6]),
    ([[], [-3, -1, 2], [], [-3, 7]], [-3, -3, -1, 2, 7]),
    ([[5]], [5]),
]

for raw_lists, expected in cases:
    actual = values(merge_k_lists([build(items) for items in raw_lists]))
    assert actual == expected, (raw_lists, expected, actual)

प्रोडक्शन-ग्रेड सत्यापन के लिए, सभी इनपुट नोड्स की पहचान भी रिकॉर्ड करें, विज़िट किए गए सेट के साथ आउटपुट को ट्रैक करें, और तीन गुणों को साबित करें: कोई साइकिल नहीं, ठीक N अद्वितीय नोड पहचान, और गैर-घटते मान। यह डुप्लिकेट सम्मिलन, नोड हानि और पॉइंटर साइकिल को पकड़ता है जो केवल-मान वाला दावा छोड़ सकता है।

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

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

“मैं इनपुट नोड्स का पुन: उपयोग करूँगा और मानूँगा कि प्रत्येक लिस्ट सॉर्ट की गई, अचक्रीय और असंयुक्त (disjoint) है। मान लें कि N कुल नोड्स हैं और m गैर-खाली लिस्ट्स हैं। अगला आउटपुट केवल m वर्तमान हेड्स में से एक हो सकता है: कोई भी गहरा नोड कम से कम अपने हेड जितना बड़ा होता है। इसलिए मैं मिन-हीप में प्रति गैर-खाली लिस्ट में एक हेड रखूँगा।

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

Python में, प्रविष्टियाँ (value, sequence, node) हैं। अद्वितीय अनुक्रम मान समान प्राथमिकताओं को नोड ऑब्जेक्ट्स की तुलना करने की कोशिश करने से रोकता है; यह क्रॉस-लिस्ट स्थिर क्रम का दावा नहीं करता है क्योंकि प्रॉम्प्ट को इसकी आवश्यकता नहीं है। प्रत्येक नोड को एक बार पॉप किया जाता है और अधिकतम एक बार डाला जाता है, जिसमें अधिकतम m हीप प्रविष्टियाँ होती हैं। वह O(N log m) है, जिसे सामान्य रूप से O(N log k) लिखा जाता है, और O(m) सहायक स्पेस है; शून्य या एक गैर-खाली लिस्ट रैखिक है।

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

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

• तुरंत फ़्लैट और सॉर्ट करना → समाधान सॉर्ट किए गए इनपुट को अनदेखा करता है और O(N log N) प्लस आउटपुट स्टोरेज खर्च करता है → प्रति सॉर्ट किए गए स्रोत पर एक फ़्रंटियर बनाए रखें।
• प्रत्येक नोड के लिए सभी k हेड्स को स्कैन करना → न्यूनतम चयन O(Nk) बन जाता है → आकार-k मिन-हीप या संतुलित जोड़ीदार मर्जिंग का उपयोग करें।
• एक लिस्ट को बार-बार बढ़ते परिणाम में मर्ज करना → शुरुआती नोड्स को बाद के कई मर्जों में पार किया जाता है → संतुलित राउंड में लिस्ट्स को संयोजित करें।
• प्रत्येक नोड को हीप में पुश करना → हीप का आकार N तक बढ़ जाता है, जिससे O(N log N) कार्य उत्पन्न होता है → प्रत्येक स्रोत से केवल एक वर्तमान नोड पुश करें।
• Python हीप में (value, node) स्टोर करना → समान मान गैर-क्रमबद्ध नोड ऑब्जेक्ट्स की तुलना करने का प्रयास करते हैं → एक अद्वितीय संख्यात्मक टाई-ब्रेकर जोड़ें।
• उत्तराधिकारी को सहेजने से पहले स्रोत को आगे बढ़ाना → पॉइंटर रीवायरिंग शेष लिस्ट को खो सकती है → पहले उत्तराधिकारी को सहेजें, फिर अलग करें और जोड़ें।
• नोड्स का पुन: उपयोग होने के कारण O(1) स्पेस का दावा करना → हीप में अभी भी k प्रविष्टियाँ तक होती हैं → आउटपुट आवंटन को सहायक स्थिति से अलग करें।
• केवल आउटपुट मानों को मान्य करना → एक साइकिल, डुप्लिकेट नोड, या खोया हुआ नोड पहचान से बच सकता है → नोड पहचान, गणना, क्रम और साइकिल-मुक्तता की जाँच करें।
• स्पष्ट किए बिना सॉर्टिंग और साइकिल सत्यापन जोड़ना → कार्यान्वयन एक बड़े अनुबंध को हल करता है और लागत बदलता है → मान्यताओं को बताएं और केवल अनुरोध किए जाने पर सत्यापन जोड़ें।

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

हीप न्यूनतम अगला वैश्विक न्यूनतम क्यों है?

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

यदि इनपुट-लिस्ट क्रम द्वारा समान मान स्थिर होने चाहिए तो क्या बदलता है?

स्थिरता को सटीक रूप से परिभाषित करें, फिर स्रोत-लिस्ट इंडेक्स के बाद मान जैसी हीप कुंजी का उपयोग करें। चूँकि प्रति स्रोत केवल एक नोड मौजूद होता है, स्रोत इंडेक्स क्रॉस-लिस्ट संबंधों को हल करता है जबकि प्रत्येक लिस्ट का अपना क्रम स्वाभाविक रूप से संरक्षित होता है। बेस सीक्वेंस टाई-ब्रेकर तुलनीयता की गारंटी देता है, उस मजबूत नीति की नहीं।

डिवाइड-एंड-कॉन्कर हीप से बेहतर कब है?

संतुलित जोड़ीदार मर्जिंग का उपयोग तब करें जब दो-लिस्ट मर्ज पहले से उपलब्ध हो, इंटरव्यू पॉइंटर हेरफेर पर जोर देता हो, या प्राथमिकता कतार अनुपलब्ध हो। प्रत्येक राउंड शेष प्रत्येक नोड को एक बार छूता है और O(log k) राउंड होते हैं। लेज़ी स्रोतों और बदलते सक्रिय-स्रोत गणनाओं के लिए एक हीप अधिक स्पष्ट है।

क्या होगा यदि इनपुट लिस्ट्स को अपरिवर्तित रहना चाहिए?

समान चयन तर्क रखें लेकिन प्रत्येक हटाए गए मान के लिए एक नया नोड आवंटित करें। समय O(N log k) रहता है। सहायक चयन स्थिति O(k) बनी रहती है, जबकि आवश्यक आउटपुट आवंटन O(N) है। स्पेस दावे के अंदर आउटपुट मेमोरी को छिपाने के बजाय दोनों को बताएं।

क्या होगा यदि दस हज़ार लिस्ट स्लॉट हैं लेकिन केवल पाँच गैर-खाली हैं?

प्रारंभीकरण k स्लॉट्स को एक बार स्कैन करता है, फिर हीप में अधिकतम m = 5 प्रविष्टियाँ होती हैं। सटीक समय O(k + N log m) है और सहायक स्पेस O(m) है। केवल O(N log k) रिपोर्ट करना ऊपरी सीमा के रूप में सुरक्षित है लेकिन खाली हेड्स को छोड़ने के लाभ को छुपाता है।

आप लिंक्ड लिस्ट्स के बजाय सॉर्ट किए गए इटरेटर्स को कैसे मर्ज करेंगे?

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

क्या उत्तराधिकारी वाले नोड को हटाने के बाद कोड heapreplace का उपयोग कर सकता है?

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

आप उदाहरणों से परे पॉइंटर शुद्धता का परीक्षण कैसे करेंगे?

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