समस्या और लागू होने वाले परिदृश्य
एक फिक्स्ड ऐरे का उपयोग करके get(index), set(index, value), और append(value) के साथ एक डायनेमिक ऐरे लागू करें। पूरा भरने पर आकार बदलें, वृद्धि नीति, सीमा व्यवहार, वर्स्ट-केस और परिशोधित append समय की व्याख्या करें, और लीनियर वृद्धि की तुलना ज्यामितीय वृद्धि से करें।
रेफरेंस या फिक्स्ड-साइज वैल्यूज, शून्य-आधारित इंडेक्स, रेंज से बाहर एक्सेस के लिए अपवाद (exceptions), और एक खाली ऐरे पर append मान लें। एक सार्वजनिक इंटरव्यू बैंक डायनेमिक-ऐरे/वेक्टर कार्यान्वयन को Microsoft, मेमोरी प्रबंधन और परिशोधित विश्लेषण से जोड़ता है; MIT 6.006 डायनेमिक-ऐरे append को परिशोधित Θ(1) के रूप में सूचीबद्ध करता है।
इंटरव्यूअर क्या मूल्यांकन कर रहा है
- क्या आप
sizeकोcapacityसे अलग करते हैं और इस इनवेरिएंट को बनाए रखते हैं कि मान्य आइटम पहलेsizeस्लॉट पर कब्जा करते हैं। - क्या आप एक बार में एक स्लॉट जोड़ने के बजाय ज्यामितीय वृद्धि चुनते हैं।
- क्या आप केवल O(1) का दावा करने के बजाय एग्रीगेट, एकाउंटिंग या पोटेंशियल विश्लेषण के साथ परिशोधित सीमा को सिद्ध कर सकते हैं।
- क्या आप शून्य क्षमता, पूर्णांक ओवरफ्लो, आवंटन विफलता, सिकुड़न (shrinking), और मध्य प्रविष्टि (middle insertion) को कवर करते हैं।
उत्तर देने से पहले स्पष्टीकरण प्रश्न
- क्या केवल टेल append आवश्यक है, या मध्य इंसर्ट, डिलीट और pop भी आवश्यक हैं? ये जटिलता के विश्लेषण को बदल देते हैं।
- क्या वैल्यूज फिक्स्ड-साइज हैं? क्या रेफरेंस सिमेंटिक्स, इटरेटर इनवैलिडेशन, या थ्रेड सुरक्षा की आवश्यकता है?
- क्या लक्ष्य कम प्रतियां (copies), कम मेमोरी ओवरहेड, या एक सख्त लेटेंसी सीमा है?
- क्या सिकुड़न (shrinking) की आवश्यकता है? यदि हां, तो क्या थ्रैशिंग से बचने के लिए इसकी सीमा (threshold) विकास सीमा से अलग होनी चाहिए?
30-सेकंड उत्तर फ्रेमवर्क
मैं एक बैकिंग ऐरे, size, और capacity को स्टोर करूँगा। जब कोई स्लॉट खाली होता है तो Append सीधे लिखता है। पूरा भरने पर, यह एक बड़ा ऐरे आवंटित करता है, पहले size तत्वों को कॉपी करता है, और नया मान लिखता है। ज्यामितीय वृद्धि जैसे कि दोगुना करना मुख्य बिंदु है: n appends पर कॉपी किए गए तत्वों की कुल संख्या 2n से नीचे एक ज्यामितीय श्रृंखला होती है, इसलिए कुल कार्य O(n) होता है और append परिशोधित रूप से O(1) होता है। रीसाइज कॉल स्वयं अभी भी O(n) है, इसलिए यह प्रति कॉल वर्स्ट-केस O(1) गारंटी नहीं है।
चरण-दर-चरण गहन विश्लेषण
स्थिति और इनवेरिएंट
तीन फील्ड्स बनाए रखें: बैकिंग ऐरे data, मान्य तत्वों की संख्या size, और आवंटित स्लॉट capacity। आकार को हमेशा कम से कम शून्य और क्षमता से अधिक नहीं रखें; मान्य तत्व [0, size) पर होते हैं। Append data[size] पर लिखता है और आकार बढ़ाता है। get और set केवल [0, size) स्वीकार करते हैं, कभी भी एक गैर-प्रारंभीकृत (uninitialized) क्षमता स्लॉट नहीं।
ज्यामितीय वृद्धि नीति
जब size == capacity हो, तो कम से कम max(1, capacity * 2) आवंटित करें, पुराने तत्वों को कॉपी करें, और बैकिंग संदर्भ को बदलें। शून्य क्षमता को एक विशेष स्थिति की आवश्यकता होती है, अन्यथा गुणनफल अभी भी शून्य ही रहेगा। दोगुना करने से वर्तमान आकार के बराबर सस्ते appends की एक श्रृंखला बनती है; एक बड़ा कारक कम बार कॉपी करता है लेकिन अधिक अप्रयुक्त स्थान छोड़ता है।
~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;
public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }
public int size() { return size; }
public Object get(int index) { check(index); return data[index]; }
public void set(int index, Object value) { check(index); data[index] = value; }
private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~
Object[] जेनेरिक टाइप इरेज़र के तहत कार्यान्वयन को स्पष्ट करने का एक सामान्य तरीका है; प्रोडक्शन कोड को अभी भी नल (nulls), आवंटन विफलता और समवर्तीता (concurrency) के लिए एक स्पष्ट नीति की आवश्यकता होती है। इनवेरिएंट और जटिलता Java पर निर्भर नहीं करते हैं।
परिशोधित प्रमाण
मान लें कि क्षमता 1 से शुरू होती है और दोगुनी हो जाती है। n appends में, सामान्य लेखन में n स्थिरांक लागत आती है; रीसाइज प्रतियां क्षमता 1, 2, 4, 8 आदि पर होती हैं, जिसका कुल योग 2n से कम होता है। इसलिए कुल कार्य आरंभीकरण के साथ 3n से कम है, जिससे प्रति ऑपरेशन O(1) परिशोधित लागत मिलती है।
यह एक वर्स्ट-केस अनुक्रम पर गारंटी है, यादृच्छिक इनपुट पर औसत नहीं। रीसाइज ट्रिगर करने वाला append अभी भी Θ(n) तत्वों को कॉपी करता है, इसलिए एक कॉल में O(n) वर्स्ट-केस समय होता है। get और set वर्स्ट केस में O(1) हैं, और बैकिंग स्टोरेज O(n) है।
लीनियर वृद्धि और सिकुड़न
एक बार में केवल c स्लॉट जोड़ने से कॉपी लागत लगभग c + 2c + ... हो जाती है; n तत्वों को सम्मिलित करने की लागत Θ(n²) होती है, इसलिए append घटकर परिशोधित Θ(n) हो जाता है। ज्यामितीय वृद्धि आमतौर पर बेहतर ट्रेड-ऑफ है, हालांकि एक बड़ा कारक पीक अप्रयुक्त स्थान को बढ़ाता है।
यदि pop समर्थित है, तो निम्न-जल स्तर (low-water mark) से नीचे जाने पर आकार घटाएं। वृद्धि और सिकुड़न सीमाओं को अलग रखें—उदाहरण के लिए, भरने पर दोगुना करें और एक चौथाई से कम होने पर आधा करें—ताकि append और pop के वैकल्पिक होने पर बार-बार डेटा स्थानांतरित न करना पड़े। सिकुड़न परिशोधित O(1) टेल संचालन को बनाए रखती है लेकिन रिलीज और कॉपी पॉज़ जोड़ती है।
परीक्षण योग्य सीमाएं
खाली ऐरे पर पहले append, सटीक क्षमता पर append, बार-बार वृद्धि, डुप्लिकेट संदर्भ, नकारात्मक इंडेक्स, index == size, विशाल क्षमताएं, ओवरफ्लो और आवंटन विफलता का परीक्षण करें। एक नियंत्रित कॉपी काउंटर यह सत्यापित कर सकता है कि n appends कुल Θ(n) प्रतियां करते हैं; केवल अंतिम सामग्री की जांच करने से एक द्विघात (quadratic) लीनियर-वृद्धि कार्यान्वयन भी पास हो जाएगा।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं बैकिंग ऐरे, size, और capacity को अलग रखूँगा, जिसमें मान्य तत्व हमेशा पहले size पदों पर होते हैं। Append मुक्त क्षमता में लिखता है; पूरा भरने पर, यह क्षमता से दोगुना आवंटित करता है, पुराने तत्वों को कॉपी करता है, और फिर मान लिखता है। प्रारंभिक शून्य क्षमता के लिए एक स्लॉट का विशेष केस होता है।
दोगुना करने का प्रमाण महत्वपूर्ण हिस्सा है: n appends पर, रीसाइज प्रतियां 2n से नीचे रहती हैं; n स्थिर लेखन जोड़ने से कुल कार्य O(n) और परिशोधित append O(1) हो जाता है। रीसाइज कॉल स्वयं O(n) बनी रहती है, इसलिए परिशोधित लागत प्रति-कॉल लेटेंसी सीमा नहीं है। लीनियर वृद्धि की कुल प्रतियों में लागत Θ(n²) होती है। यदि सिकुड़न की आवश्यकता है, तो मैं हिस्टैरिसीस का उपयोग करूँगा और खाली इनपुट, सीमाओं, ओवरफ्लो और आवंटन विफलता का परीक्षण करूँगा।
सामान्य गलतियाँ
- भरे होने पर हर बार एक स्लॉट जोड़ना → कुल कॉपी द्विघात हो जाती है → ज्यामितीय वृद्धि का उपयोग करें और श्रृंखला दिखाएं।
- append को वर्स्ट-केस O(1) कहना → रीसाइज कॉपी को अनदेखा करना → एक-कॉल O(n) और अनुक्रम परिशोधित O(1) के बीच अंतर स्पष्ट करें।
getको क्षमता के विरुद्ध मान्य करना → एक गैर-प्रारंभीकृत स्लॉट लौटाना → आवश्यक करें कि इंडेक्स कम से कम शून्य और आकार से कम हो।- शून्य क्षमता को दोगुना करना → ऐरे कभी नहीं बढ़ता → न्यूनतम क्षमता एक का उपयोग करें।
- कम उपयोग पर तुरंत सिकुड़ना → वैकल्पिक append/pop बार-बार चाल का कारण बनता है → वृद्धि और सिकुड़न थ्रेशोल्ड को अलग करें।
फॉलो-अप प्रश्न और उत्तर
क्या होगा यदि प्रत्येक append के लिए O(1) वर्स्ट-केस समय आवश्यक हो?
एक सन्निहित (contiguous) ऐरे रीसाइज O(n) माइग्रेशन करता है, इसलिए यह लिखे गए रूप में उस सख्त सीमा का वादा नहीं कर सकता है। एक खंडित ऐरे, वृद्धिशील माइग्रेशन, या ज्ञात ऊपरी-सीमा प्री-एलोकेशन लोकैलिटी, इंडेक्स स्थिरांक या स्पेस की कीमत पर ट्रेड-ऑफ को बदल सकते हैं। पहले पुष्टि करें कि क्या आवश्यकता वास्तव में वर्स्ट-केस की है।
क्या बदलता है यदि वृद्धि कारक 2 के बजाय 1.25 हो?
1 से सख्ती से बड़ा कोई भी कारक अभी भी परिशोधित O(1) टेल append देता है, लेकिन प्रतियां अधिक बार होती हैं और अतिरिक्त स्थान कम होता है। जैसे-जैसे कारक 1 के करीब पहुंचता है, स्थिरांक बढ़ते हैं; केवल Big-O के बजाय मेमोरी बजट, एलोकेटर व्यवहार और लेटेंसी लक्ष्यों का उपयोग करके चयन करें।
आप कैसे सिद्ध करते हैं कि लीनियर वृद्धि O(n²) है?
यदि प्रत्येक रीसाइज c स्लॉट जोड़ता है, तो j-वां रीसाइज लगभग jc तत्वों को कॉपी करता है। पहले n तत्व लगभग n/c रीसाइज ट्रिगर करते हैं, इसलिए कुल योग c + 2c + ... + (n/c)c = Θ(n²) है। इसलिए परिशोधित append Θ(n) है।
मध्य प्रविष्टि (middle insertion) जटिलता को कैसे बदलती है?
अतिरिक्त क्षमता होने पर भी, मध्य प्रविष्टि एक प्रत्यय (suffix) को स्थानांतरित करती है और वर्स्ट केस में O(n) होती है। रीसाइज कॉपी करना अतिरिक्त कार्य है; डायनेमिक ऐरे रैंडम एक्सेस और टेल संचालन के लिए अनुकूलित होते हैं, न कि हर प्रकार के इंसर्शन के लिए।
समवर्ती (concurrent) append कैसे काम करेगा?
एक लॉक, सिंगल-थ्रेड स्वामित्व, या समन्वित रीसाइजिंग के साथ एक परमाणु-इंडेक्स (atomic-index) प्रोटोकॉल का उपयोग करें। केवल size को परमाणु बनाना पूरी जांच-क्षमता, आवंटन, कॉपी और प्रकाशन अनुक्रम की रक्षा नहीं करता है। यदि समवर्तीता की आवश्यकता नहीं है, तो सिंगल-थ्रेड सीमा को स्पष्ट रूप से बताएं।