प्रॉम्प्ट और लागू संदर्भ
एक सिंगली लिंक्ड लिस्ट का head head और एक धनात्मक पूर्णांक k दिया गया है, k क्रमिक नोड्स के प्रत्येक कम्प्लीट ग्रुप को in-place रिवर्स करें। यदि अंत में k से कम नोड्स बचते हैं, तो उनके मूल क्रम को बनाए रखें। value फ़ील्ड्स की अदला-बदली करने के बजाय नोड्स के पॉइंटर्स को फिर से कनेक्ट (rewire) करें।
उदाहरण के लिए, k = 2 होने पर 1 → 2 → 3 → 4 → 5 बदलकर 2 → 1 → 4 → 3 → 5 हो जाता है, और k = 3 होने पर 3 → 2 → 1 → 4 → 5 हो जाता है। मान लें कि 1 ≤ k ≤ n ≤ 5000 है, इनपुट चक्रीय नहीं है (acyclic), और लक्ष्य O(1) अतिरिक्त स्पेस के साथ O(n) समय है।
यह एल्गोरिदम, बैकएंड, इंफ्रास्ट्रक्चर और सामान्य सॉफ्टवेयर इंजीनियरिंग भूमिकाओं के कोडिंग इंटरव्यू के लिए उपयुक्त है। कठिन हिस्सा बेसिक लिस्ट रिवर्सल नहीं है। यह म्यूटेशन से पहले साबित करना है कि एक कम्प्लीट ग्रुप मौजूद है, अगले ग्रुप की एंट्री को सुरक्षित रखना, दोनों सीमाओं को फिर से जोड़ना, और यह दिखाना कि कोई भी नोड खो नहीं गया है या साइकिल में नहीं फंसा है।
इंटरव्यूअर क्या मूल्यांकन करता है
पहला संकेत यह है कि क्या उम्मीदवार बाउंड्री डिस्कवरी, सेगमेंट रिवर्सल और रीकनेक्शन को अलग करता है। यह जानने से पहले रिवर्स करना शुरू करना कि k नोड्स बचे हैं, अतिरिक्त स्टोरेज के बिना अधूरे टेल को रिस्टोर करना मुश्किल बना देता है। एक मजबूत समाधान किसी भी पॉइंटर को बदलने से पहले केवल पढ़ने के लिए (read-only) लुकअहेड करता है।
दूसरा संकेत स्पष्ट पॉइंटर ओनरशिप है। groupPrev वर्तमान ग्रुप से पहले स्थित होता है, kth एक कम्प्लीट ग्रुप का अंतिम नोड है, groupNext अगले सेगमेंट की एंट्री है, और पुराना ग्रुप हेड नया टेल बन जाता है। प्रत्येक पुनरावृत्ति (iteration) के अंत में, तैयार प्रीफ़िक्स सुलभ (reachable) रहना चाहिए और groupPrev.next पहला अनप्रोसेस्ड नोड होना चाहिए।
तीसरा संकेत रटे हुए कोड के बजाय एक इन्वेरिएंट (invariant) है। prev को groupNext पर इनिशियलाइज़ करने से पुराना ग्रुप हेड टेल बनने पर सफ़िक्स की ओर पॉइंट करने लगता है। एक बार रिवर्सल समाप्त हो जाने के बाद, केवल पिछले प्रीफ़िक्स को kth से जोड़ा जाना चाहिए; ग्रुप-से-सफ़िक्स कनेक्शन पहले से ही सही होता है।
चौथा संकेत कॉम्प्लेक्सिटी अनुशासन है। प्रत्येक नोड को कम्प्लीट-ग्रुप लुकअहेड द्वारा अधिकतम एक बार और रिवर्सल द्वारा एक बार विज़िट किया जाता है, इसलिए कुल कार्य O(n) है, जबकि संदर्भों (references) की एक निश्चित संख्या O(1) अतिरिक्त स्पेस देती है। एक रिकर्सिव वर्जन की समान समय सीमा होती है लेकिन वह ग्रुप्स की संख्या के अनुपात में स्टैक स्पेस की खपत करता है।
उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न
kसे छोटे अंतिम ग्रुप का क्या होता है? यह यहाँ अपरिवर्तित रहता है। कुछ प्रकार इसे रिवर्स करते हैं, जिससे
एक अलग परिणाम प्राप्त होता है।
- क्या नोड मानों (values) की अदला-बदली की जा सकती है? नहीं। नोड्स में वैल्यू के अलावा पहचान (identity), बाहरी संदर्भ या अन्य फ़ील्ड हो सकते हैं,
इसलिए वैल्यू स्वैपिंग नोड रिवर्सल नहीं है।
kके कौन से मान मान्य हैं? प्रॉम्प्ट1 ≤ k ≤ nकी गारंटी देता है। एक पुन: प्रयोज्य (reusable) फ़ंक्शन अभी भी एक
गैर-पूर्णांक या एक से कम मान को अस्वीकार कर सकता है।
- क्या इनपुट में साइकिल हो सकती है? यह प्रॉम्प्ट मना करता है। यदि साइकिल संभव हैं, तो अनुबंध (contract) में यह स्पष्ट होना चाहिए कि उन्हें
अस्वीकार करना है या बदलना है; अन्यथा लुकअहेड कभी समाप्त नहीं हो सकता है।
- क्या एल्गोरिदम in-place होना चाहिए? हाँ।
O(k)स्पेस की अनुमति होने पर स्टैक सरल होता है, लेकिन यह इस लक्ष्य को पूरा नहीं करता। - क्या नोड ऑब्जेक्ट्स का पुन: उपयोग किया जाना चाहिए? हाँ। केवल मानों को कॉपी करने वाली एक नई लिस्ट बनाना अनुबंध का उल्लंघन करता है।
30-सेकंड उत्तर रूपरेखा (Framework)
"मैं head से पहले एक डमी नोड जोड़ूँगा और groupPrev को वर्तमान ग्रुप के ठीक पहले रखूँगा। प्रत्येक पुनरावृत्ति kth खोजने के लिए groupPrev से k कदम चलती है। यदि यह विफल हो जाता है, तो मैं तुरंत वापस लौट जाता हूँ क्योंकि टेल में कोई संशोधन नहीं हुआ है। groupNext = kth.next को सेव करने के बाद, मैं prev को groupNext पर इनिशियलाइज़ करता हूँ और वर्तमान ग्रुप को एक समय में एक पॉइंटर रिवर्स करता हूँ। इससे पुराना ग्रुप हेड नया टेल बन जाता है जो पहले से ही groupNext को पॉइंट कर रहा होता है। मैं groupPrev.next को kth से जोड़ता हूँ, फिर groupPrev को पुराने ग्रुप हेड पर ले जाता हूँ। प्रत्येक नोड को लुकअहेड के लिए एक बार और रिवर्सल के लिए एक बार विज़िट किया जाता है, जिससे O(n) समय और O(1) अतिरिक्त स्पेस मिलता है।"
चरण-दर-चरण गहन विश्लेषण
डमी नोड के साथ शुरुआत करें। पहला ग्रुप रिवर्स होने पर लिस्ट का हेड बदल जाता है। डमी नोड नए ग्रुप हेड से प्रीफ़िक्स को जोड़ना पहले और बाद के प्रत्येक ग्रुप के लिए समान बना देता है, जिससे एक विशेष हेड केस से बचा जा सकता है।
प्रत्येक पुनरावृत्ति पहले कम्प्लीट-ग्रुप लुकअहेड करती है। kth प्राप्त करने के लिए groupPrev से ठीक k बार आगे बढ़ें। यदि वॉक null तक पहुँच जाती है, तो k से कम नोड्स बचते हैं, इसलिए dummy.next लौटाएँ। लुकअहेड ने किसी भी पॉइंटर पर राइट नहीं किया है, यही वजह है कि अधूरा टेल अपने आप अपरिवर्तित रहता है।
कार्यान्वयन (Implementation) इस प्रकार है:
class ListNode {
constructor(value, next = null) {
this.value = value
this.next = next
}
}
function reverseKGroup(head, k) {
if (!Number.isInteger(k) || k < 1) {
throw new RangeError('k must be a positive integer')
}
const dummy = new ListNode(0, head)
let groupPrev = dummy
while (true) {
let kth = groupPrev
for (let step = 0; step < k; step += 1) {
kth = kth.next
if (kth === null) {
return dummy.next
}
}
const groupNext = kth.next
let prev = groupNext
let current = groupPrev.next
while (current !== groupNext) {
const nextNode = current.next
current.next = prev
prev = current
current = nextNode
}
const oldGroupHead = groupPrev.next
groupPrev.next = kth
groupPrev = oldGroupHead
}
}k = 3 के साथ 1 → 2 → 3 → 4 → 5 को ट्रेस करें। लुकअहेड kth = 3 पाता है, और groupNext = 4 सेव हो जाता है। prev = 4 सेट करें, फिर 1.next = 4, 2.next = 1, और 3.next = 2 लिखें। नोड 3 अब ग्रुप हेड है, जबकि नोड 1 टेल है और पहले से ही नोड 4 तक पहुँचता है। डमी नोड को 3 से जोड़ें और groupPrev को नोड 1 पर ले जाएँ। अगला लुकअहेड तीन नोड्स नहीं ढूंढ पाता है, इसलिए यह 4 → 5 को छुए बिना लौट जाता है।
लूप इन्वेरिएंट के तीन भाग होते हैं। लूप प्रविष्टि पर, groupPrev तक का प्रीफ़िक्स कम्प्लीट ग्रुप्स में सही ढंग से बदल दिया गया है; groupPrev.next पहला अनप्रोसेस्ड नोड है; और सभी अनप्रोसेस्ड नोड्स इनपुट क्रम में सुलभ रहते हैं। विफल लुकअहेड कोई राइट ऑपरेशन नहीं करता है, इसलिए इन्वेरिएंट सीधे साबित करता है कि अधूरा टेल संरक्षित है। सफल लुकअहेड रिवर्सल को ठीक k नोड्स तक सीमित करता है, जबकि groupNext सफ़िक्स एंट्री को सुरक्षित रखता है। पुनः जुड़ने के बाद, तैयार प्रीफ़िक्स एक ग्रुप बढ़ जाता है और इन्वेरिएंट बहाल हो जाता है। प्रत्येक सफल पुनरावृत्ति k नए नोड्स की खपत करती है, इसलिए एल्गोरिदम समाप्त हो जाता है।
लुकअहेड और रिवर्सल प्रत्येक सभी पुनरावृत्तियों में किसी नोड को अधिकतम एक बार छूते हैं। इसलिए कुल कार्य अधिकतम लगभग 2n नोड विज़िट है: O(n), न कि O(nk)। डमी नोड और पॉइंटर काउंट इनपुट के साथ नहीं बढ़ते हैं, इसलिए ऑक्सिलरी स्पेस O(1) है।
यदि अतिरिक्त स्पेस की अनुमति है, तो एक ग्रुप को स्टैक पर पुश करना और उसे पॉप करना लिखना आसान है लेकिन O(k) स्पेस का उपयोग करता है। एक रिकर्सिव समाधान एक कम्प्लीट ग्रुप की पुष्टि कर सकता है, उसे रिवर्स कर सकता है, और O(n / k) स्टैक स्पेस का उपयोग करके सफ़िक्स पर रिकर्सन कर सकता है। निरंतर-स्पेस (constant-space) लक्ष्य के लिए पुनरावृत्त (iterative) वर्जन सही सिफारिश है। एक छोटे इनपुट के लिए जहाँ प्राथमिकता जल्दी से समीक्षा योग्य पहला वर्जन है, स्टैक दृष्टिकोण एक उचित स्पष्ट रूप से उल्लिखित ट्रेड-ऑफ हो सकता है।
परीक्षणों को केवल वैल्यू ऐरे की तुलना करने से अधिक करना चाहिए। मूल नोड संदर्भों के सेट को सहेजें, परिणाम को ट्रैवर्स करें, और क्रम की जाँच करने से पहले पुष्टि करें कि यह चक्रीय नहीं है (acyclic), नोड काउंट समान है, और इसमें ठीक वही संदर्भ शामिल हैं। एक सुरक्षात्मक खाली इनपुट, एक नोड, k = 1, n = k, एक समान रूप से विभाज्य लंबाई, एक अधूरा टेल, डुप्लिकेट मान और अधिकतम आकार को कवर करें। डुप्लिकेट मान विशेष रूप से उपयोगी होते हैं क्योंकि केवल-वैल्यू परीक्षण यह साबित नहीं कर सकते कि नोड ऑब्जेक्ट्स का पुन: उपयोग किया गया था।
उच्च गुणवत्ता वाला नमूना उत्तर
"मैं पहले यह पुष्टि करूँगा कि k से कम ट्रेलिंग नोड्स क्रम में रहें और वैल्यूज को स्वैप न किया जा सके। मेरी इटेरेटिव स्टेट एक डमी नोड और संदर्भों की एक निश्चित संख्या है। groupPrev हमेशा वर्तमान ग्रुप के ठीक पहले स्थित होता है। मैं इससे k कदम चलता हूँ, और यदि kth मौजूद नहीं है, तो किसी भी टेल पॉइंटर को बदलने से पहले वापस लौट जाता हूँ।
एक कम्प्लीट ग्रुप के लिए, मैं groupNext को सेव करता हूँ। मैं prev को groupNext पर इनिशियलाइज़ करता हूँ, फिर पुराने ग्रुप हेड से groupNext तक पहुँचने तक मानक तीन-पॉइंटर रिवर्सल लागू करता हूँ। वह इनिशियलाइज़ेशन मायने रखता है: जब पुराना हेड टेल बन जाता है, तो उसका next पहले से ही अगले सेगमेंट तक पहुँचता है। रिवर्सल के बाद, kth नया हेड होता है। मैं groupPrev.next को इससे जोड़ता हूँ और groupPrev को पुराने हेड पर ले जाता हूँ।
इन्वेरिएंट यह है कि प्रोसेस्ड प्रीफ़िक्स सही और जुड़ा हुआ है, groupPrev.next पहला अनप्रोसेस्ड नोड है, और सफ़िक्स इनपुट क्रम में रहता है। एक पूर्ण रिवर्सल प्रीफ़िक्स को बढ़ाता है; एक अधूरा ग्रुप कोई राइट ऑपरेशन नहीं करता है, जिससे टेल सुरक्षित रहता है। प्रत्येक नोड को लुकअहेड के लिए अधिकतम एक बार और रिवर्सल के लिए एक बार विज़िट किया जाता है, इसलिए समय O(n) है और अतिरिक्त स्पेस O(1) है। मैं केवल वैल्यू सीक्वेंस ही नहीं, बल्कि नोड पहचान और नॉन-साइक्लिसिटी को भी सत्यापित करूँगा।"
सामान्य गलतियाँ
- पूर्ण ग्रुप की पुष्टि करने से पहले रिवर्स करना → एक अधूरा टेल म्यूटेट हो जाता है और उसे रिस्टोर करना कठिन हो जाता है →
पहले केवल-पढ़ने के लिए लुकअहेड करें।
prev = nullके साथ रिवर्सल शुरू करना → ग्रुप अस्थायी रूप से सफ़िक्स से अलग हो जाता है और आसानी से डिस्कनेक्टेड रह जाता है →
prev = groupNext से शुरू करें।
- केवल नए ग्रुप हेड को जोड़ना → हो सकता है कि नया टेल सफ़िक्स तक न पहुँचे → **
groupNextको सुरक्षित रखें और
सत्यापित करें कि नया टेल इसे पॉइंट करता है।**
kthको अगले प्रीडिसेसर के रूप में रखना → अगला ग्रुप बाउंड्री गलत हो जाता है → **groupPrevको पुराने
ग्रुप हेड पर ले जाएँ।**
- नोड मानों की अदला-बदली करना → नोड पहचान और संलग्न-फ़ील्ड सिमेंटिक्स टूट जाते हैं → केवल
nextबदलें। - दावा करना कि रिकर्सिव ऑक्सिलरी स्पेस
O(1)है → कॉल स्टैक ग्रुप काउंट के साथ बढ़ता है → **कांस्टेंट एक्स्ट्रा स्पेस के लिए
इटरेशन का उपयोग करें।**
- केवल वैल्यू सीक्वेंस का परीक्षण करना → खोए हुए, कॉपी किए गए, या चक्रीय नोड्स का पता नहीं चल सकता है → **संदर्भ
पहचान, काउंट, और नॉन-साइक्लिसिटी को भी सत्यापित करें।**
- लुकअहेड और रिवर्सल को
O(nk)में गुणा करना → ग्रुप्स पुनरावृत्तियों में अलग-अलग (disjoint) होते हैं → **प्रति नोड कुल विज़िट्स
का योग करें।**
फॉलो-अप प्रश्न और उत्तर
फॉलो-अप 1: क्या होगा यदि k से छोटे अंतिम ग्रुप को भी रिवर्स करना पड़े?
विफल लुकअहेड अब तुरंत वापस नहीं लौट सकता। यह शेष नोड्स की वास्तविक संख्या की गणना भी कर सकता है और उस छोटे सेगमेंट को रिवर्स कर सकता है, या एल्गोरिदम पहले लिस्ट की लंबाई की गणना कर सकता है और ग्रुप साइज़ के रूप में min(k, remaining) का उपयोग कर सकता है। इन्वेरिएंट का समाप्ति भाग बदल जाता है, और n < k वाला केस अनिवार्य हो जाता है।
फॉलो-अप 2: आप एकांतर (alternating) ग्रुप्स को कैसे रिवर्स करेंगे?
कम्प्लीट k-नोड ग्रुप्स द्वारा लुकअहेड जारी रखें और एक बूलियन फ्लैग रखें। एक रिवर्स ग्रुप मूल लॉजिक का उपयोग करता है; एक स्किप किया गया ग्रुप पॉइंटर्स को अछूता छोड़ देता है और groupPrev को k नोड्स आगे बढ़ाता है। अधूरे-टेल नियम को फिर से स्पष्ट करें, क्योंकि इसे स्किप्ड या रिवर्स ग्रुप के रूप में गिनने से परिणाम बदल जाता है।
फॉलो-अप 3: आप कैसे साबित कर सकते हैं कि एल्गोरिदम कोई साइकिल नहीं बनाता है?
स्थानीय प्रमाण दो सीमाओं का उपयोग करता है: groupNext को सहेजें, जो वर्तमान ग्रुप के बाहर है, और prev = groupNext से current === groupNext तक रिवर्स करें। प्रत्येक रीराइट किया गया किनारा (edge) वर्तमान नोड से पहले से प्रोसेस्ड प्रीडिसेसर या सफ़िक्स एंट्री की ओर पॉइंट करता है, वर्तमान ग्रुप के अभी भी अनप्रोसेस्ड हिस्से में वापस कभी नहीं जाता है। टेस्ट्स को एक फास्ट-स्लो साइकिल चेक भी चलाना चाहिए और पुष्टि करनी चाहिए कि ट्रैवर्स किए गए नोड्स की संख्या इनपुट संख्या के बराबर है।
फॉलो-अप 4: सौ मिलियन नोड्स वाली लिस्ट के लिए क्या बदलता है?
एसिम्प्टोटिक सीमाएँ समान रहती हैं, लेकिन रिकर्सन से बचा जाना चाहिए, नोड्स को कॉपी नहीं किया जाना चाहिए, और एक लंबे ऑपरेशन के लिए टाइमआउट और कैंसिलेशन व्यवहार मायने रखता है। यदि लिस्ट बाहरी स्टोरेज में रहती है या मशीनों में फैली हुई है, तो रैंडम रीवायरिंग और एटॉमिक विजिबिलिटी समस्या पर हावी हो जाती है। इन-मेमोरी एल्गोरिदम को सीधे स्थानांतरित नहीं किया जा सकता है; डेटा लेआउट, ट्रांजैक्शन बाउंड्रीज़ और रिकवरेबल चेकपॉइंट्स को पहले परिभाषित किया जाना चाहिए।