समस्या और दायरा
एक सीमित पूर्णांक यूनिवर्स [0, U) को देखते हुए, insert(x), remove(x), contains(x), clear(), और वर्तमान सदस्यों पर पुनरावृत्ति (iteration) के साथ एक सेट लागू करें। पहले चार ऑपरेशन्स सबसे खराब स्थिति (worst-case) में O(1) होने चाहिए; k वर्तमान सदस्यों के लिए इटरेशन में O(k) समय लगता है। डुप्लिकेट्स को अस्वीकार कर दिया जाता है, और अनुपस्थित मान को हटाना एक नो-ऑप (no-op) है।
सार्वजनिक साक्षात्कार रिकॉर्ड में Pure Storage की चर्चा में इस प्रकार का प्रश्न शामिल है। मुख्य परीक्षा dense/sparse-array इनवेरिएंट की है, न कि किसी लाइब्रेरी क्लास को रटने की।
इंटरव्यूअर क्या जांच रहा है
- क्या आप बताते हैं कि एक निश्चित यूनिवर्स की आवश्यकता है;
O(1)का दावा बिना किसी शर्त के मनमाने पूर्णांकों तक विस्तारित नहीं होता है। - क्या आप
dense[sparse[x]] == xबनाए रखते हैं और पुराने इंडेक्स के गलत सकारात्मक (false positives) परिणामों को रोकने के लिए इसका उपयोग करते हैं। - क्या विलोपन (deletion) अंतिम तत्व के साथ स्वैप करता है, जिससे dense प्रीफ़िक्स निरंतर बना रहता है और इटरेशन
O(k)पर रहता है। - क्या आप
O(U)स्पेस बताते हैं और यह पहचानते हैं कि कब हैश सेट या बिटमैप अधिक उपयुक्त होता है।
कोडिंग से पहले स्पष्टीकरण
- क्या
Uज्ञात है, और क्या समाधानUलंबाई के दो एरे आवंटित कर सकता है? यह संसाधन की पूर्व शर्त है। - क्या
iterate()सॉर्टेड होना चाहिए? यह डिज़ाइन सभी सदस्यों को लौटाता है लेकिन क्रम का वादा नहीं करता है। - क्या स्थिर इटरेटर या समवर्ती पहुँच (concurrent access) की आवश्यकता है? वे आवश्यकताएं स्वैप-डिलीट और सिंक्रोनाइज़ेशन सिमेंटिक्स को बदल देती हैं।
- क्या
clear()कोUको स्कैन करने से बचना चाहिए? प्रॉम्प्ट को निरंतर समय की आवश्यकता है, इसलिए यह केवलsizeको रीसेट करता है।
30-सेकंड का उत्तर
“मैं U लंबाई का एक sparse इंडेक्स एरे, U लंबाई का एक dense एरे और वर्तमान size रखता हूँ। एक तत्व x बिल्कुल तब मौजूद होता है जब sparse[x] < size और dense[sparse[x]] == x हो। Insert dense[size] पर x लिखता है और इंडेक्स रिकॉर्ड करता है; remove इसके स्लॉट को अंतिम तत्व से अधिलेखित (overwrite) करता है और उस तत्व के इंडेक्स को ठीक करता है; clear केवल size को शून्य पर सेट करता है। चार मुख्य ऑपरेशन्स सबसे खराब स्थिति में O(1) हैं, dense प्रीफ़िक्स पर इटरेशन O(k) है, और स्पेस O(U) है।”
चरण-दर-चरण गहन विश्लेषण
चरण 1: इनवेरिएंट बताएं।
dense[0..size) में प्रत्येक सदस्य ठीक एक बार होता है। एक सदस्य x के लिए, sparse[x] dense में उसकी स्थिति है और dense[sparse[x]] == x है। एक गैर-सदस्य एक पुराना sparse मान बनाए रख सकता है, इसलिए contains केवल यह जांच नहीं सकता कि इंडेक्स सीमा के भीतर है या नहीं।
चरण 2: लुकअप और इंसर्शन।
contains(x) 0 <= x < U की जांच करता है, फिर sparse[x] < size और रिवर्स लिंक को मान्य करता है। Insert पहले contains को कॉल करता है; यदि अनुपस्थित है, तो यह dense[size] में x लिखता है, sparse[x] = size सेट करता है, और size बढ़ाता है।
चरण 3: स्वैप-डिलीट।
यदि x स्थिति i पर है, तो last = dense[size - 1] मान लें। अंतिम तत्व को dense[i] पर लिखें, sparse[last] = i को अपडेट करें, और size घटाएं। sparse[x] को साफ़ करने की कोई आवश्यकता नहीं है: size बदलने के बाद, रिवर्स-लिंक जांच पुराने प्रविष्टि को अमान्य कर देती है। अंतिम तत्व को हटाना भी इसी तर्क का पालन करता है।
चरण 4: निरंतर समय में clear और रैखिक इटरेशन।
clear() size = 0 सेट करता है; पुरानी एरे सामग्री को अब सदस्यों के रूप में नहीं पढ़ा जाता है। इटरेशन केवल dense[0] से dense[size - 1] तक स्कैन करता है, इसलिए इसमें O(k) लगता है, O(U) नहीं।
चरण 5: जटिलता और सीमाएँ।
contains, insert, remove, और clear सबसे खराब स्थिति में O(1) हैं; इटरेशन O(k) है; स्पेस O(U) है। GCC इस निरूपण को एक निश्चित यूनिवर्स और कैश-अनुकूल गणना के लिए उपयोगी बताता है। यदि यूनिवर्स अज्ञात है, बढ़ना चाहिए, या मेमोरी के लिए बहुत बड़ा है, तो एक हैश सेट या बिटमैप बेहतर फिट हो सकता है।
चरण 6: इनवेरिएंट का परीक्षण करें।
प्रत्येक यादृच्छिक ऑपरेशन की तुलना संदर्भ Set से करें। एक खाली सेट, डुप्लिकेट इंसर्शन, अनुपस्थित मान को हटाना, मध्य और अंतिम तत्व को हटाना, clear के बाद पुन: उपयोग, और मान 0 और U-1 को कवर करें। प्रत्येक ऑपरेशन के बाद, सत्यापित करें कि dense प्रीफ़िक्स में कोई डुप्लिकेट नहीं है और प्रत्येक सदस्य का रिवर्स लिंक मान्य है।
उच्च-गुणवत्ता वाला नमूना उत्तर
“सीमित यूनिवर्स [0, U) मुझे नियतात्मक (deterministic) निरंतर समय के ऑपरेशन्स के लिए दो एरेज़ का उपयोग करने की अनुमति देता है। Dense वर्तमान सदस्यों का एक कॉम्पैक्ट प्रीफ़िक्स संग्रहीत करता है, जबकि sparse एक मान को उसके dense इंडेक्स पर वापस मैप करता है। सदस्यता को सीमाओं, इंडेक्स < size, और रिवर्स लिंक की जांच करनी चाहिए; केवल sparse संख्या की जांच करना असुरक्षित है। Remove अंतिम तत्व को स्वैप करता है और उसके sparse इंडेक्स को अपडेट करता है, जबकि clear केवल size को रीसेट करता है। अपडेट और लुकअप सबसे खराब स्थिति में O(1) हैं, इटरेशन O(k) है, और स्पेस O(U) है। यदि यूनिवर्स अनियंत्रित है, तो मैं इसके बजाय एक हैश सेट या बिटमैप चुनूंगा।”
सामान्य गलतियाँ
- केवल
sparse[x] < sizeकी जाँच करना → एक अनुपस्थित मान एक संभावित इंडेक्स बनाए रख सकता है →dense[sparse[x]] == xकी भी जाँच करें। - हटाने पर बाद के सभी तत्वों को स्थानांतरित (shift) करना → विलोपन
O(U)याO(k)बन जाता है → अंतिम तत्व के साथ स्वैप करें। - clear के दौरान एरेज़ को भरना → clear
O(U)बन जाता है → केवल size को रीसेट करें। - सीमित यूनिवर्स को अनदेखा करना → सीमा से बाहर एक्सेस या अस्वीकार्य मेमोरी खपत → पहले
[0, U)और क्षमता की पुष्टि करें। - इटरेशन को
O(1)कहना → एक व्यू प्राप्त करना निरंतर समय है, लेकिन सभी सदस्यों को प्रोसेस करनाO(k)है → दोनों लागतों को अलग करें।
अनुवर्ती प्रश्न और उत्तर
अनुवर्ती 1: आप मनमाने पूर्णांकों का समर्थन कैसे करेंगे?
पहले मानों को [0, U) में कोऑर्डिनेट-कंप्रेस करें। यदि मान डोमेन बढ़ता रहता है या इसे पहले से स्कैन नहीं किया जा सकता है, तो एक हैश सेट अधिक स्वाभाविक है, लेकिन इसका निरंतर समय का दावा इस प्रॉम्प्ट में सबसे खराब स्थिति की गारंटी के बजाय अमोर्टाइज़्ड या अपेक्षित है।
अनुवर्ती 2: आप इटरेशन क्रम को कैसे सुरक्षित रखेंगे?
स्वैप-डिलीट dense क्रम को बदल देता है। इंसर्शन क्रम को संरक्षित करने के लिए एक अतिरिक्त लिंक्ड सूची या स्थिर एरे की आवश्यकता होती है, जो विलोपन और स्पेस लागत को बदल देती है। इसे जोड़ने से पहले पुष्टि करें कि क्या क्रम इंटरफ़ेस अनुबंध का हिस्सा है।
अनुवर्ती 3: आप बिटमैप कब चुनेंगे?
बिटमैप तब चुनें जब सदस्यता ही एकमात्र ऑपरेशन हो, यूनिवर्स मध्यम हो, और प्रति मान एक बिट मायने रखता हो। जब तेज़ गणना (fast enumeration) भी महत्वपूर्ण हो तो एक sparse set चुनें; सही चुनाव U, कार्डिनैलिटी और एक्सेस पैटर्न पर निर्भर करता है।