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

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

एक एसाइक्लिक सिंगली लिंक्ड लिस्ट का हेड दिया गया है, जिसमें प्रत्येक नोड में val, next और random होते हैं। random पॉइंटर या तो null होता है या लिस्ट की next चेन के माध्यम से पहुंच योग्य किसी भी नोड (स्वयं नोड सहित) को संदर्भित करता है। प्रत्येक मूल नोड के लिए ठीक एक नए नोड के साथ एक डीप कॉपी रिटर्न करें। यदि मूल नोड x किसी भी फ़ील्ड के माध्यम से मूल नोड y को पॉइंट करता है, तो x की कॉपी को उस फ़ील्ड के माध्यम से y की कॉपी को पॉइंट करना चाहिए।

नोड मान यूनीक नहीं होते हैं, इसलिए मान किसी नोड की पहचान नहीं कर सकता है। next चेन सीमित (finite) है, हालांकि random किनारे (edges) पीछे, आगे पॉइंट कर सकते हैं या चक्र (cycles) बना सकते हैं। रिटर्न की गई लिस्ट को इनपुट के साथ कोई भी नोड साझा नहीं करना चाहिए, और फ़ंक्शन के रिटर्न होने पर इनपुट की अपनी मूल संरचना होनी चाहिए।

यह एक डेटा-स्ट्रक्चर और ऑब्जेक्ट-आइडेंटिटी की समस्या है। बेसलाइन समाधान प्रत्येक मूल ऑब्जेक्ट से उसकी कॉपी के मैप का उपयोग करता है। एक फॉलो-अप प्रश्न में निरंतर सहायक स्पेस (constant auxiliary space) की आवश्यकता हो सकती है; वह वर्शन अस्थायी रूप से कॉपियों को मूल नोड्स के साथ इंटरलीव करता है और फिर इनपुट को पुनर्स्थापित करता है। आउटपुट नोड्स को सहायक स्पेस में नहीं गिना जाता है, लेकिन वे फिर भी कुल O(n) मेमोरी का उपभोग करते हैं।

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

पहला संकेत यह है कि उम्मीदवार डीप कॉपी को संरचनात्मक रूप से परिभाषित करता है या नहीं। केवल मानों का बराबर होना पर्याप्त नहीं है। उत्तर में मूल नोड्स से नए नोड्स के लिए एक-से-एक मैपिंग f की आवश्यकता होती है ताकि दोनों संबंध सुरक्षित रहें: x.next की कॉपी f(x).next हो, और x.random की कॉपी f(x).random हो।

दूसरा संकेत किसी संदर्भ को उसके लक्ष्य के कॉपी होने से पहले संभालना है। एक-पास वाला वैल्यू कॉपी समाधान फॉरवर्ड random किनारे को सुरक्षित रूप से कनेक्ट नहीं कर सकता है। सीधा समाधान आवंटन (allocation) को कनेक्शन (wiring) से अलग करता है: पहले प्रत्येक गंतव्य नोड बनाएं, फिर आइडेंटिटी मैप के माध्यम से पॉइंटर्स को कनेक्ट करें।

तीसरा संकेत स्पेस ऑप्टिमाइज़ेशन को रटने के बजाय उसे व्युत्पन्न (derive) करना है। प्रत्येक कॉपी को उसके मूल नोड के ठीक बाद रखने के बाद, किसी भी मूल नोड r की कॉपी बिल्कुल r.next होती है। यह स्थानीय इनवेरिएंट रैंडम-पॉइंट असाइनमेंट के दौरान मैप की जगह ले लेता है।

अंत में, इंटरव्यूअर म्यूटेशन अनुशासन की तलाश करता है। इंटरलीविंग विधि तब तक अधूरी है जब तक कि यह प्रत्येक मूल next पॉइंटर को पुनर्स्थापित नहीं करती, एक मान्य कॉपी की गई चेन नहीं निकालती, और यह नहीं बताती कि इनपुट को अस्थायी रूप से बदलना कब अस्वीकार्य है।

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

• क्या random लिस्ट के बाहर पॉइंट कर सकता है? यह प्रॉम्प्ट कहता है कि नहीं। यदि बाहरी नोड्स क्लोन से संबंधित हैं, तो दायरा एक सामान्य रीचेबल-ग्राफ़ कॉपी बन जाता है; यदि वे संबंधित नहीं हैं, तो आउटपुट अनुबंध में यह स्पष्ट होना चाहिए कि उन संदर्भों को बनाए रखना है, साफ़ करना है या अस्वीकार करना है।
• क्या next चेन में कोई चक्र (cycle) हो सकता है? नहीं। यदि ऐसा होता है, तो केवल next का अनुसरण करने वाला लूप बिना विजिटेड सेट के कभी समाप्त नहीं होगा, और इस समस्या को ग्राफ़ क्लोनिंग के रूप में बेहतर ढंग से संभाला जा सकता है।
• क्या एल्गोरिदम इनपुट को अस्थायी रूप से संशोधित (mutate) कर सकता है? मैप समाधान ऐसा नहीं करता है। इंटरलीविंग समाधान ऐसा करता है और केवल तभी उपयुक्त होता है जब फ़ंक्शन के पास विशेष म्यूटेबल एक्सेस हो और वह रिटर्न करने से पहले लिस्ट को पुनर्स्थापित करता हो।
• अतिरिक्त स्पेस के रूप में क्या गिना जाता है? कॉपी किए गए नोड्स आवश्यक आउटपुट हैं। मैप में O(n) सहायक स्पेस की लागत आती है; इंटरलीविंग आवश्यक O(n) आउटपुट के अलावा O(1) सहायक पॉइंटर्स का उपयोग करता है।
• क्या मान यूनीक हैं? नहीं। मान द्वारा कुंजीबद्ध (keyed) किया गया मैप अलग-अलग नोड्स को मर्ज कर देगा और संदर्भों को दूषित कर देगा; कुंजियाँ नोड की पहचान (identities) होनी चाहिए।
• खाली इनपुट पर क्या रिटर्न होना चाहिए? null रिटर्न करें।

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

“मैं पहले इसे ओरिजिनल-टू-कॉपी आइडेंटिटी मैप के साथ हल करूंगा। एक पास प्रत्येक कॉपी किए गए नोड को आवंटित करता है, और दूसरा पास संबंधित मूल लक्ष्यों को देखकर कॉपी किए गए next और random पॉइंटर्स को असाइन करता है। इसमें O(n) समय और O(n) सहायक स्पेस लगता है। यदि इंटरव्यूअर को निरंतर सहायक स्पेस की आवश्यकता है और अस्थायी म्यूटेशन की अनुमति है, तो मैं प्रत्येक कॉपी को उसके मूल नोड के ठीक बाद डाल सकता हूँ। तब किसी मूल रैंडम लक्ष्य की कॉपी उसका अगला नोड होती है। तीसरा पास इनपुट को पुनर्स्थापित करते हुए चेन्स को अलग करता है। दोनों तरीके लीनियर हैं; इंटरलीविंग वर्शन आवश्यक आउटपुट को छोड़कर O(1) सहायक स्पेस का उपयोग करता है।”

चरण-दर-चरण विस्तृत उत्तर

एक शैलो कॉपी (shallow copy) विफल हो जाती है क्योंकि यह मूल संदर्भों का पुनर्चक्रण करती है। केवल मानों को कॉपी करना भी विफल हो जाता है: दो अलग-अलग नोड्स का मान समान हो सकता है, और random उस नोड को पॉइंट कर सकता है जो अभी तक ट्रैवर्सल में दिखाई नहीं दिया है। random का पुनरावर्ती रूप से (recursively) अनुसरण करना कोई शॉर्टकट नहीं है क्योंकि रैंडम किनारे चक्र बना सकते हैं।

सबसे सुरक्षित बेसलाइन स्पष्ट रूप से एक बाइजेक्शन (bijection) बनाता है। पहला पास प्रति मूल नोड एक नया ऑब्जेक्ट आवंटित करता है। दूसरा पास उस मैप के माध्यम से दोनों आउटगोइंग किनारों का अनुवाद करता है। लुकअप में null -> null को शामिल करना वैकल्पिक है; इंटरव्यू में स्पष्ट नल चेक आमतौर पर अधिक स्पष्ट होते हैं।

class RandomListNode {
  val: number
  next: RandomListNode | null
  random: RandomListNode | null

  constructor(
    val: number,
    next: RandomListNode | null = null,
    random: RandomListNode | null = null,
  ) {
    this.val = val
    this.next = next
    this.random = random
  }
}

function copyWithMap(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  const copies = new Map<RandomListNode, RandomListNode>()

  let current: RandomListNode | null = head
  while (current !== null) {
    copies.set(current, new RandomListNode(current.val))
    current = current.next
  }

  current = head
  while (current !== null) {
    const copy = copies.get(current)!
    copy.next = current.next === null ? null : copies.get(current.next)!
    copy.random = current.random === null ? null : copies.get(current.random)!
    current = current.next
  }

  return copies.get(head)!
}

पहले पास के बाद का इनवेरिएंट सरल है: next के माध्यम से विज़िट किए गए प्रत्येक मूल नोड की मैप में ठीक एक अलग प्रविष्टि होती है, और किसी भी कॉपी किए गए पॉइंटर को अनअलोकेटेड नोड को लक्षित नहीं करना पड़ता है। दूसरे पास के दौरान, x से y तक के किनारे को f(x) से f(y) तक के किनारे में अनुवादित करने से ग्राफ़ सुरक्षित रहता है। इस विधि में दो लीनियर पास लगते हैं, इसलिए समय O(n) और सहायक स्पेस O(n) है।

मैप को हटाने के लिए, उसी पत्राचार (correspondence) को अस्थायी रूप से लिस्ट टोपोलॉजी में स्टोर करें। इस चेन को:

A -> B -> C -> null

इस इंटरलीव्ड चेन में बदलें:

A -> A' -> B -> B' -> C -> C' -> null

अब A' का मान A.next है, और यदि A.random, C को पॉइंट करता है, तो A'.random के लिए सही लक्ष्य A.random.next है, जो कि C' है। यह फॉरवर्ड किनारों, बैकवर्ड किनारों, सेल्फ़-रेफरेंस और बार-बार आने वाले लक्ष्यों के लिए काम करता है क्योंकि यह ऑब्जेक्ट की स्थिति पर निर्भर करता है, मानों पर नहीं।

function copyByInterleaving(head: RandomListNode | null): RandomListNode | null {
  if (head === null) return null

  let current: RandomListNode | null = head
  while (current !== null) {
    const copy: RandomListNode = new RandomListNode(current.val, current.next)
    current.next = copy
    current = copy.next
  }

  current = head
  while (current !== null) {
    const copy: RandomListNode = current.next!
    copy.random = current.random === null ? null : current.random.next
    current = copy.next
  }

  const copiedHead = head.next
  current = head

  while (current !== null) {
    const copy: RandomListNode = current.next!
    const nextOriginal: RandomListNode | null = copy.next

    current.next = nextOriginal
    copy.next = nextOriginal === null ? null : nextOriginal.next
    current = nextOriginal
  }

  return copiedHead
}

शुद्धता तीन पास इनवेरिएंट्स से सिद्ध होती है। पास एक के बाद, प्रत्येक मूल नोड के तुरंत बाद उसकी यूनीक कॉपी होती है। पास दो के दौरान, प्रत्येक कॉपी किया गया रैंडम किनारा मूल लक्ष्य के ठीक बाद वाली कॉपी पर जाता है। पास तीन के दौरान, प्रत्येक पुनरावृत्ति (iteration) एक मूल किनारे को पुनर्स्थापित करती है और एक कॉपी किए गए किनारे को अगले कॉपी किए गए नोड से जोड़ती है। जब लूप समाप्त होता है, तो मूल चेन पुनर्स्थापित हो जाती है और कॉपी किए गए हेड से पहुंच योग्य प्रत्येक पॉइंटर केवल कॉपी किए गए नोड्स को लक्षित करता है।

इंटरलीविंग विधि तीन लीनियर पास करती है, इसलिए समय O(n) ही रहता है। यह केवल निश्चित संख्या में वर्किंग पॉइंटर्स को संग्रहीत करता है, इसलिए आवश्यक n नए नोड्स को छोड़कर सहायक स्पेस O(1) है। यह स्वचालित रूप से प्रोडक्शन के लिए बेहतर विकल्प नहीं है: पहले दो पास के दौरान, अन्य पाठकों को इनपुट दूषित दिखाई देता है, और सेपरेशन से पहले एक अपवाद (exception) लिस्ट को इंटरलीव्ड स्थिति में छोड़ सकता है। मैप समाधान का ऑडिट करना आसान है और यह इम्यूटेबल या साझा किए गए इनपुट का समर्थन करता है।

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

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

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

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

यदि निरंतर सहायक स्पेस एक सख्त आवश्यकता है और मुझे अस्थायी रूप से म्यूटेट करने की अनुमति है, तो मैं प्रत्येक कॉपी को उसके मूल नोड के बाद सम्मिलित करूंगा। यह मैपिंग को अंतर्निहित (implicit) बना देता है: किसी भी मूल लक्ष्य की कॉपी target.next होती है। फिर मैं प्रत्येक कॉपी किए गए रैंडम पॉइंटर को असाइन करता हूँ और वैकल्पिक चेन को अलग (unzip) करता हूँ। अनज़िप पास को दोनों चेन्स को अपडेट करना चाहिए, ताकि मूल बिल्कुल पुनर्स्थापित हो जाए और कॉपी में इसके वापस संदर्भ न हों।

मैं वीविंग (weaving), रैंडम असाइनमेंट और सेपरेशन के बाद तीनों इनवेरिएंट्स को सिद्ध करूंगा, फिर सेल्फ़-रैंडम, डुप्लिकेट मान, क्रॉस्ड रैंडम किनारे, खाली इनपुट और कॉपी के बाद की स्वतंत्रता का परीक्षण करूंगा। दोनों वर्शन्स का समय O(n) है; दूसरा O(1) सहायक स्पेस लेता है लेकिन फिर भी O(n) आउटपुट आवंटित करता है और समवर्ती पाठकों (concurrent readers) के साथ असुरक्षित है।”

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

• मैप को नोड मान द्वारा कुंजीबद्ध करना -> डुप्लिकेट मान अलग-अलग पहचानों को मिला देते हैं -> मूल नोड ऑब्जेक्ट द्वारा कुंजीबद्ध करें।
• random को सीधे कॉपी करना -> आउटपुट अभी भी इनपुट में पॉइंट करता है -> प्रत्येक गैर-शून्य लक्ष्य को उसके कॉपी किए गए नोड में अनुवादित करें।
• एक ही आसान फॉरवर्ड पास में आवंटित और कनेक्ट करना -> एक फॉरवर्ड रैंडम लक्ष्य अभी मौजूद नहीं हो सकता है -> पहले सभी नोड्स आवंटित करें या संपूर्ण आइडेंटिटी मैप के माध्यम से अनुपलब्ध कॉपियां बनाएं।
• विज़िट की गई स्थिति के बिना रैंडम पॉइंटर्स का पुनरावर्ती रूप से अनुसरण करना -> रैंडम चक्र अनंत पुनरावृत्ति (infinite recursion) या डुप्लिकेट नोड्स का कारण बनते हैं -> इस अनुबंध के लिए सीमित next चेन का उपयोग करें या सामान्य ग्राफ़ के लिए एक विज़िटेड मैप का उपयोग करें।
• बिना शर्त के इंटरलीविंग विधि को O(1) स्पेस कहना -> रिटर्न की गई लिस्ट में अभी भी n नए नोड्स होते हैं -> आवश्यक आउटपुट को छोड़कर O(1) सहायक स्पेस कहें।
• नल चेक के बिना copy.random = current.random.next असाइन करना -> एक नल रैंडम पॉइंटर क्रैश का कारण बनता है -> स्पष्ट रूप से नल को बनाए रखें।
• केवल कॉपी की गई चेन को अलग करना -> मूल नोड्स कॉपियों के माध्यम से जुड़े रहते हैं -> मूल को पुनर्स्थापित करें और उसी सेपरेशन पास में कॉपी की गई चेन का निर्माण करें।
• साझा इनपुट पर इंटरलीविंग का उपयोग करना -> समवर्ती पाठक इन्सर्ट की गई कॉपियों को देखते हैं -> मैप समाधान का उपयोग करें जब तक कि अनन्य अस्थायी म्यूटेशन की गारंटी न हो।
• केवल मानों का परीक्षण करना -> एक शैलो कॉपी मान तुलना पास कर सकती है -> अलग पहचान, अनुवादित किनारे, मूल बहाली और म्यूटेशन स्वतंत्रता का परीक्षण करें।

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

फॉलो-अप 1: क्या होगा यदि इनपुट को कभी भी संशोधित नहीं किया जाना चाहिए, अस्थायी रूप से भी नहीं?

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

फॉलो-अप 2: क्या होगा यदि random next चेन के बाहर किसी नोड को पॉइंट कर सकता है?

पहले क्लोन के स्वामित्व (ownership) को परिभाषित करें। यदि बाहरी नोड्स को भी कॉपी किया जाना चाहिए, तो इनपुट एक ग्राफ़ है जिसके आउटगोइंग किनारे next और random हैं; आइडेंटिटी मैप के साथ DFS या BFS का उपयोग करें और प्रत्येक पहुंच योग्य नोड को एक बार क्लोन करें। यदि बाहरी नोड्स जानबूझकर साझा किए गए हैं, तो अनुबंध में बनाए रखे गए बाहरी संदर्भों की अनुमति होनी चाहिए। इंटरलीविंग मनमाने बाहरी लक्ष्यों के लिए कॉपियों को खोज या व्यवस्थित नहीं कर सकता है।

फॉलो-अप 3: क्या होगा यदि next पॉइंटर्स एक चक्र बना सकते हैं?

एक सामान्य while current !== null ट्रैवर्सल समाप्त नहीं होगा। दोनों फ़ील्ड्स को ग्राफ़ किनारों के रूप में मानें और एक विज़िटेड आइडेंटिटी मैप रखें। किसी नोड के पहली बार खोजे जाने पर उसकी कॉपी बनाएं, फिर अनदेखे पड़ोसियों को कतारबद्ध (enqueue) करें। इस मॉडल में प्रति नोड अधिकतम दो आउटगोइंग किनारों के साथ, पहुंच योग्य ग्राफ़ के लिए समय और स्पेस O(V + E) हो जाता है।

फॉलो-अप 4: आप कैसे सत्यापित करेंगे कि कॉपी वास्तव में डीप कॉपी है?

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

फॉलो-अप 5: आप कौन सा समाधान प्रोडक्शन में भेजेंगे?

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