1. समस्या और संदर्भ
एक सिंगल-कर्सर टेक्स्ट एडिटर के लिए कोर बफर लागू करें। लॉजिकल टेक्स्ट वर्णों (characters) का एक क्रम है; कर्सर दो वर्णों के बीच बैठता है। left(), right(), insert(ch), delete(), और text() का समर्थन करें।
स्टोरेज को एक ऐरे के रूप में दर्शाएं जिसमें एक अप्रयुक्त अंतराल होता है जिसे गैप कहा जाता है। gapStart को इनक्लूसिव और gapEnd को एक्सक्लूसिव मानें। दिखाई देने वाला टेक्स्ट gapStart से पहले का प्रीफिक्स और उसके बाद gapEnd पर और उसके बाद का सफिक्स है। ETH Zurich का अभ्यास इस प्रतिनिधित्व का उपयोग करता है और उम्मीदवारों से व्यवहार तथा सीमाओं दोनों को सत्यापित करने के लिए कहता है। एक सार्वजनिक Google L4 इंटरव्यू रिपोर्ट भी एक टेक्स्ट-एडिटर/बुककीपिंग कार्यान्वयन राउंड का वर्णन करती है जिसमें डेटा-स्ट्रक्चर ट्रेड-ऑफ, ड्राई रन और सटीक जटिलता पर जोर दिया गया था।
2. इंटरव्यूअर क्या मूल्यांकन करता है
- स्टेट मॉडलिंग: क्या आप लॉजिकल लंबाई और ऐरे क्षमता को भ्रमित किए बिना बता सकते हैं कि दो इंडेक्स का क्या अर्थ है?
- इनवेरिएंट्स: क्या प्रत्येक ऑपरेशन और रीसाइज़ वैध सीमाओं और समान लॉजिकल टेक्स्ट को बनाए रखते हैं?
- सीमा अनुशासन (Boundary discipline): क्या खाली, भरे हुए, बाएं किनारे, दाएं किनारे और एकल-वर्ण वाले बफ़र्स स्पष्ट हैं?
- जटिलता का तर्क: क्या आप समझा सकते हैं कि पास के संपादन सस्ते क्यों हैं और कर्सर की लंबी छलांग दूरी के अनुपात में लीनियर क्यों है?
- डिज़ाइन निर्णय: क्या आप बता सकते हैं कि बड़ी फ़ाइलों, कई कर्सर, या सहयोगी संपादन (collaborative editing) के लिए गैप बफर कब उपयुक्त नहीं रह जाता है?
एक कमजोर उत्तर पहले ऐरे मूव्स लिखता है और बाद में ऑफ-बाय-वन त्रुटियों की खोज करता है। एक मजबूत उत्तर प्रतिनिधित्व से प्रत्येक चाल प्राप्त करता है और एक साधारण स्ट्रिंग मॉडल के विरुद्ध इसका परीक्षण करता है।
3. पहले स्पष्ट करने योग्य प्रश्न
क्या कर्सर एक कैरेक्टर इंडेक्स है या एक सीमा (boundary)?
एक सीमा का उपयोग करें: cursor इसके बाईं ओर के लॉजिकल वर्णों की संख्या के बराबर है। यह cursor=0 को बायां किनारा और cursor=length को दायां किनारा बनाता है, और यह delete() को कर्सर के ठीक पहले वाले वर्ण को हटाने के रूप में परिभाषित करता है।
कर्सर पर delete का क्या अर्थ है?
पुष्टि करें कि Backspace या Delete में से किसका आशय है। यह लेख Backspace सिमेंटिक्स का उपयोग करता है: गैप को एक स्थान बाईं ओर ले जाएं और इसे बड़ा करें। एक फॉरवर्ड-डिलीट ऑपरेशन इसके बजाय गैप के बाद के पहले वर्ण को हटाएगा।
कौन से स्टोरेज और टेक्स्ट मॉडल की आवश्यकता है?
बाइट्स बनाम यूनिकोड स्केलर मान, अधिकतम दस्तावेज़ आकार, और क्या अनडू, रैंडम लाइन लुकअप, कई कर्सर, या समवर्ती संपादन की आवश्यकता है, इसे स्पष्ट करें। ये आवश्यकताएं केवल मेथड जोड़ने के बजाय डेटा संरचना को बदल सकती हैं।
4. 30-सेकंड उत्तर रूपरेखा
"मैं दस्तावेज़ को कर्सर पर एक गैप के साथ एक ऐरे में संग्रहीत करूंगा। gapStart कर्सर की सीमा है और gapEnd पहले सफिक्स वर्ण को चिह्नित करता है; लॉजिकल टेक्स्ट प्रीफिक्स और सफिक्स का योग है। इंसर्शन gapStart पर लिखता है और इसे आगे बढ़ाता है। Backspace प्रीफिक्स से एक वर्ण को गैप के पार ले जाता है और दोनों इंडेक्स को घटाता है। दाईं ओर ले जाना सफिक्स के एक वर्ण को प्रीफिक्स की तरफ कॉपी करता है और दोनों इंडेक्स को आगे बढ़ाता है। यदि गैप खाली है, तो ऐरे का आकार बढ़ाएं और एक बड़ा गैप बनाएं। मैं प्रत्येक ऑपरेशन के बाद सीमाओं और स्ट्रिंग-मॉडल तुल्यता का दावा (assert) करूंगा। पास के संपादन एमॉर्टाइज़्ड कांस्टेंट समय लेते हैं; गैप को स्थानांतरित करना दूरी के हिसाब से लीनियर है, इसलिए बड़ी फ़ाइलों या कई कर्सर के लिए पीस टेबल या रोप की आवश्यकता हो सकती है।"
5. चरण-दर-चरण समाधान
चरण 1: प्रतिनिधित्व इनवेरिएंट बताएं
क्षमता n के लिए, 0 ≤ gapStart ≤ gapEnd ≤ n की आवश्यकता होती है। लॉजिकल लंबाई n - (gapEnd - gapStart) है। लॉजिकल अनुक्रम buffer[0:gapStart] के साथ buffer[gapEnd:n] का संयोजन है। गैप के अंदर के मानों को नजरअंदाज कर दिया जाता है और उन्हें इनिशियलाइज़ करने की आवश्यकता नहीं होती है।
चरण 2: बाईं ओर जाएं (Move left)
यदि gapStart == 0 है, तो कर्सर पहले से ही बाएं किनारे पर है। अन्यथा gapStart और gapEnd को घटाएं, फिर कर्सर के ठीक पहले वाले वर्ण को गैप की नई अंतिम स्थिति में कॉपी करें। प्रीफिक्स एक वर्ण खो देता है और सफिक्स में कोई वृद्धि नहीं होती है; कॉपी किया गया वर्ण अब तार्किक रूप से गैप से पहले है।
चरण 3: दाईं ओर जाएं (Move right)
यदि gapEnd == n है, तो कर्सर दाएं किनारे पर है। अन्यथा buffer[gapEnd] को buffer[gapStart] में कॉपी करें, फिर दोनों इंडेक्स को बढ़ाएं। पहला सफिक्स वर्ण गैप को पार करता है, जिससे अनुक्रम क्रम सुरक्षित रहता है। जब गैप में केवल एक स्लॉट होता है, तो कॉपी और इंडेक्स अपडेट का क्रम मायने रखता है।
चरण 4: इन्सर्ट करें (Insert)
यदि gapStart == gapEnd है, तो लिखने से पहले grow() को कॉल करें। वर्ण को buffer[gapStart] पर संग्रहीत करें और gapStart को बढ़ाएं। नया वर्ण प्रीफिक्स में अंतिम आइटम बन जाता है, ठीक कर्सर की पूर्व सीमा पर।
चरण 5: पीछे की ओर हटाएं (Delete backward)
यदि gapStart == 0 है, तो बाईं ओर कोई वर्ण नहीं है। अन्यथा gapStart को घटाएं; गैप में अब हटाया गया वर्ण शामिल है। किसी ऐरे शिफ्ट की आवश्यकता नहीं है। लॉजिकल अनुक्रम अपना अंतिम प्रीफिक्स वर्ण खो देता है।
चरण 6: टेक्स्ट बदले बिना आकार बढ़ाएं (Grow)
एक बड़े ऐरे को आवंटित करें, प्रीफिक्स को समान इंडेक्स पर कॉपी करें, और सफिक्स को नए ऐरे के अंत में कॉपी करें। gapStart को अपरिवर्तित रखें और नया gapEnd सेट करें ताकि सफिक्स की लंबाई स्थिर रहे। एक ज्यामितीय क्षमता नीति जैसे कि दोगुना करना तब एमॉर्टाइज़्ड कांस्टेंट इंसर्शन देती है जब संपादन गैप के पास रहते हैं, लेकिन मेमोरी सीमाएं एक छोटे विकास कारक (growth factor) को उचित ठहरा सकती हैं।
चरण 7: अगली संरचना का सोच-समझकर चयन करें
एक सक्रिय कर्सर और स्थानीय संपादनों के लिए गैप बफर आकर्षक है क्योंकि हॉट क्षेत्र सन्निहित (contiguous) रहता है। एक पीस टेबल मूल और केवल-जोड़ने (append-only) वाले बफ़र्स को संरक्षित करती है और अनडू-उन्मुख संपादकों के लिए उपयोगी है। एक रोप या विखंडित टुकड़ों (chunks) का पेड़ बड़े दस्तावेज़ों और दूर के स्थानों पर फैले संपादनों को संभालता है। एक सहयोगी संपादक ऑपरेशनल ट्रांसफॉर्मेशन या CRDT आवश्यकताओं को जोड़ता है जिन्हें एक गैप बफर हल नहीं करता है।
6. उच्च-गुणवत्ता वाला नमूना उत्तर
"मैं कर्सर को एक सीमा के रूप में मॉडल करता हूं और एक अप्रयुक्त गैप के आसपास दो इंडेक्स रखता हूं। इनवेरिएंट 0 ≤ gapStart ≤ gapEnd ≤ capacity है; लॉजिकल टेक्स्ट गैप से पहले का प्रीफिक्स और उसके बाद का सफिक्स है। इंसर्शन एक गैप स्लॉट का उपभोग करता है। Backspace gapStart को घटाता है, और दायां तीर दोनों इंडेक्स को बढ़ाते हुए सफिक्स के एक वर्ण को प्रीफिक्स की तरफ कॉपी करता है। बायां तीर विपरीत दिशा में सममित कॉपी करता है। जब गैप खाली होता है तो मैं सफिक्स को नए टेल में कॉपी करके स्टोरेज का आकार बढ़ाता हूं, जो लॉजिकल अनुक्रम को बनाए रखता है।
मैं खाली बफर, भरे हुए गैप, दोनों किनारों, एक-वर्ण वाले टेक्स्ट, बार-बार रिवर्सल और ग्रोथ सहित एक साधारण स्ट्रिंग प्लस कर्सर मॉडल के खिलाफ ऑपरेशनों का परीक्षण करूंगा। स्थानीय संपादन एमॉर्टाइज़्ड O(1) हैं; कर्सर को स्थानांतरित करने की लागत प्रति पार किए गए वर्ण O(1) है, और रीसाइज़ की लागत O(n) है। बड़ी फ़ाइलों, कई कर्सर, या सहयोगी संपादनों के लिए मैं पीस टेबल या रोप पर स्विच करूंगा क्योंकि एकल सन्निहित गैप बाधा (bottleneck) बन जाता है।"
7. सामान्य गलतियाँ
gapEndको इनक्लूसिव मानना → एक सेल बहुत दूर तक कॉपी या सीमा जांच करता है → गैप को[gapStart, gapEnd)के रूप में परिभाषित करें और एक खाली गैप का परीक्षण करें।- पहले इंडेक्स बढ़ाने के बाद दाईं ओर ले जाना → गलत सफिक्स सेल को पढ़ता है → किसी भी इंडेक्स को बदलने से पहले
buffer[gapEnd]कोbuffer[gapStart]में कॉपी करें। - ऐरे सेल को साफ़ करके डिलीट करना → लॉजिकल लंबाई और कर्सर को अपरिवर्तित छोड़ देता है →
gapStartको घटाकर गैप का विस्तार करें। - केवल गैप को स्थानांतरित करके आकार बढ़ाना → सफिक्स को पुनर्व्यवस्थित करता है या खो देता है → सफिक्स को एक ब्लॉक के रूप में नए ऐरे के अंत में कॉपी करें।
- बिना अनुबंध के बाइट्स का उपयोग करना → मल्टी-बाइट वर्ण को विभाजित कर सकता है → कर्सर मूवमेंट लागू करने से पहले बाइट या स्केलर सिमेंटिक्स घोषित करें।
- दावा करना कि प्रत्येक संपादन
O(1)है → कर्सर की लंबी यात्रा और रीसाइज़ की उपेक्षा करता है → एमॉर्टाइज़्ड स्थानीय-संपादन लागत और लीनियर मूवमेंट/ग्रोथ मामलों को बताएं। - सहयोग के लिए गैप बफर का उपयोग करना → मर्ज सिमेंटिक्स के साथ स्थानीय स्टोरेज को भ्रमित करता है → सहयोग आवश्यकताओं के आधार पर पीस टेबल, रोप या CRDT आर्किटेक्चर चुनें।
8. फॉलो-अप प्रश्न
आप फॉरवर्ड Delete कैसे लागू करेंगे?
यदि gapEnd == capacity है, तो कर्सर के बाद कोई वर्ण नहीं है। अन्यथा gapEnd को बढ़ाएं; पहला सफिक्स वर्ण गैप में प्रवेश करता है और लॉजिकल अनुक्रम से गायब हो जाता है। यह Backspace का दर्पण है और समान इनवेरिएंट को बनाए रखता है।
कर्सर को स्थानांतरित करने के लिए सबसे खराब स्थिति क्या है?
k वर्णों के पार जाने पर k कांस्टेंट-टाइम प्रतियां बनती हैं, इसलिए यह O(k) है। एक छोर से दूसरे छोर पर कूदना O(length) है। जब एडिटर अक्सर दूर के स्थानों पर जाता है, तो एक लाइन इंडेक्स या चंक्ड संरचना नेविगेशन कार्य को कम कर सकती है।
आप अनडू (undo) कैसे जोड़ेंगे?
पूरे ऐरे के स्नैपशॉट के बजाय संपादन कमांड या उलटी सीमाओं (inverse ranges) को रिकॉर्ड करें। एक पीस टेबल सम्मिलित टेक्स्ट को केवल-जोड़ने योग्य बना सकती है और ऐतिहासिक संदर्भों को सरल बना सकती है, जबकि गैप बफर को एक स्पष्ट ऑपरेशन लॉग और कर्सर स्थितियों की आवश्यकता होती है।
आप कार्यान्वयन को कैसे सत्यापित करते हैं?
एक संदर्भ जोड़ी (string, cursor) के विरुद्ध यादृच्छिक ऑपरेशन ट्रेस चलाएं। प्रत्येक ऑपरेशन के बाद, text(), कर्सर स्थिति और सीमाओं की तुलना करें। यह दावा जोड़ें कि प्रत्येक ऐरे एक्सेस क्षमता के भीतर है; ETH Zurich अभ्यास स्पष्ट रूप से व्यवहार और सीमाओं के सत्यापन के लिए कहता है।