प्रॉम्प्ट और दायरा
एक स्टैटिक पूर्णांक ऐरे a दिए जाने पर, कई हाफ़-ओपन रेंज क्वेरीज़ [l, r) का उत्तर दें: k-वां सबसे छोटा मान, x की फ़्रीक्वेंसी, और [lo, hi) में तत्वों की संख्या लौटाएं। ऐरे कभी नहीं बदलता है और मान बड़े हो सकते हैं। प्रत्येक रेंज को सॉर्ट करने की तुलना में तेज़ संरचना डिज़ाइन और विश्लेषण करें।
एक वेवलेट मैट्रिक्स मानों को मोस्ट सिग्निफिकेंट बिट से लीस्ट सिग्निफिकेंट बिट तक बिट्स द्वारा स्टेबली पार्टिशन करती है, जो प्रत्येक स्तर पर एक बिटवेक्टर और प्रीफ़िक्स-वन काउंट स्टोर करती है। इसमें स्पष्ट ट्री पॉइंटर्स की आवश्यकता नहीं होती है; प्रत्येक क्वेरी अपने इंटरवल को अगले स्तर पर मैप करती है। स्पष्ट करें कि k ज़ीरो-बेस्ड है, कोऑर्डिनेट कम्प्रेशन और डुप्लिकेट्स को संभालें, और बाउंड्स प्रदान करें।
इंटरव्यूअर क्या मूल्यांकन करता है
- समझाएं कि स्टेबल पार्टिशनिंग, ज़ीरो-ब्लॉक स्टार्ट, और rank मैपिंग क्रम को क्यों बनाए रखते हैं।
[l, r)पर k-वें मान का चयन करें और बिट्स को सही ढंग से संचित करें।- डुप्लिकेट्स, खाली रेंज, आउट-ऑफ़-रेंज
k, और साइन्ड मानों को संभालें। - वैल्यू-डोमेन काउंट, पॉइंट फ़्रीक्वेंसी, और k-वें मान की क्वेरीज़ के लिए पाथ में अंतर करें।
O(B)क्वेरी,O(nB)निर्माण, और कम्प्रेशिबल-स्पेस बाउंड्स दें।- पहचानें कि स्टैटिक संरचना सस्ते अपडेट प्रदान नहीं करती है और इसके विकल्प जानें।
स्पष्टीकरण के लिए प्रश्न
- क्या
rएक्सक्लूसिव है, और क्याkज़ीरो-बेस्ड है या वन-बेस्ड? - क्या ऐरे वास्तव में इम्यूटेबल है? यदि नहीं, तो अपडेट और क्वेरी की दरें क्या हैं?
- क्या मान साइन्ड हैं, और उनकी अधिकतम चौड़ाई क्या है? क्या हम उन्हें कोऑर्डिनेट-कम्प्रेस कर सकते हैं?
- rank के लिए कितनी मेमोरी उपलब्ध है, और क्या बिटवेक्टर ब्लॉक किए जा सकते हैं या कम्प्रेस किए जा सकते हैं?
- क्या हमें केवल k-वें मान की आवश्यकता है, या फ़्रीक्वेंसी, प्रीडिसेसर, या रेंज सम की भी? ऑपरेशंस विकल्प को प्रभावित करते हैं।
30-सेकंड का उत्तर
मैं मानों को बिट चौड़ाई B वाले नॉन-नेगेटिव कोड में कोऑर्डिनेट-कम्प्रेस करूंगा। निर्माण के दौरान, उच्चतम बिट से नीचे की ओर वर्तमान अनुक्रम को स्टेबली पार्टिशन करें, प्रत्येक स्तर के बिटवेक्टर और प्रीफ़िक्स rank-one काउंट को स्टोर करें। k-वें के लिए, [l,r) बनाए रखें, स्तर पर शून्यों की गणना करें, और या तो शून्य ब्लॉक में मैप करें या शून्यों को घटाएं और उत्तर बिट सेट करते हुए वन ब्लॉक में मैप करें। फ़्रीक्वेंसी दो rank वॉक का उपयोग करती है; वैल्यू-डोमेन काउंट दो countLess कॉल्स का अंतर है। क्वेरी की लागत O(B) है और निर्माण की लागत O(nB) है।
चरण-दर-चरण समाधान
1. वैल्यू डोमेन को एनकोड करें
मनमाने साइन्ड पूर्णांकों के लिए, विशिष्ट मानों को सॉर्ट करें और उन्हें 0..m-1 पर मैप करें, एक कोड-टू-वैल्यू ऐरे को बनाए रखें। तब B ceil(log2(m)) है, जिसमें m=1 के लिए एक स्पष्ट केस होता है। यदि प्राकृतिक क्रम को सीधे संरक्षित किया जाना चाहिए, तो साइन्ड मानों को अनसाइन्ड के रूप में मानने से पहले साइन बिट को फ़्लिप करें।
2. एक स्टेबल स्तर का निर्माण करें
bit पर cur का निरीक्षण करें, सभी ज़ीरो-बिट मानों को next में जोड़ें, फिर सभी वन-बिट मानों को जोड़ें, दोनों समूहों के भीतर क्रम को बनाए रखें। bv[i] मूल स्थिति i पर बिट को रिकॉर्ड करता है, और zeroCount शून्यों की संख्या है। स्टेबिलिटी बाद के इंटरवल्स को उन्हीं मूल तत्वों से जोड़े रखती है।
rank1(i) = number of ones in bv[0..i)
zeroCount = n - rank1(n)
for interval [l, r):
zero interval = [l - rank1(l), r - rank1(r))
one interval = [zeroCount + rank1(l), zeroCount + rank1(r))3. रेंज k-वें मान को क्वेरी करें
प्रत्येक स्तर पर zeros = (r-l) - (rank1(r)-rank1(l)) की गणना करें। जब k शून्यों से छोटा हो, तो शून्य इंटरवल पर मैप करें। अन्यथा शून्यों को घटाएं, वन इंटरवल पर मैप करें, और वर्तमान उत्तर बिट सेट करें। B स्तरों के बाद, कोड को उसके मूल मान में वापस डिकोड करें।
4. सिंगल-वैल्यू फ़्रीक्वेंसी क्वेरी करें
प्रत्येक टार्गेट बिट को एक निश्चित ब्रांच के रूप में मानें और [l,r) को उसी तरह मैप करें। एक ज़ीरो टार्गेट शून्य इंटरवल का अनुसरण करता है; एक वन टार्गेट zeroCount का उपयोग करके वन इंटरवल का अनुसरण करता है। B स्तरों के बाद, इंटरवल की लंबाई फ़्रीक्वेंसी होती है। कम्प्रेश्ड डिक्शनरी से अनुपस्थित टार्गेट शून्य लौटाता है।
5. एक वैल्यू रेंज को क्वेरी करें
[l,r) में x से नीचे के मानों की संख्या के रूप में countLess(x, l, r) को परिभाषित करें। जिस स्तर पर x में बिट वन है, प्रत्येक शून्य ब्रांच छोटी होती है, इसलिए zeros जोड़ें और वन ब्रांच में जारी रखें। बिट शून्य के लिए, केवल शून्य ब्रांच में जारी रखें। [lo, hi) में काउंट countLess(hi)-countLess(lo) है।
6. सीमाएं और सत्यापन
खाली रेंज के लिए या जब बायां एंडपॉइंट दाएं एंडपॉइंट से छोटा न हो, व्यवहार को परिभाषित करें; rank ऐरे को उनकी सीमाओं से बाहर कभी इंडेक्स न करें। आवश्यकता रखें कि k वर्तमान रेंज की लंबाई के भीतर आए। सभी-समान, सॉर्टेड, इंटरलीव्ड डुप्लिकेट्स, नेगेटिव मान, एक-तत्व रेंज, अधिकतम बिट चौड़ाई, और डिक्शनरी से अनुपस्थित मानों का परीक्षण करें, प्रत्येक परिणाम की तुलना ब्रूट-फ़ोर्स सॉर्ट या काउंट से करें।
7. जटिलता और ट्रेड-ऑफ़
साधारण प्रीफ़िक्स काउंट के साथ, प्रत्येक स्तर O(n) काउंटर्स स्टोर करता है, इसलिए स्पेस और निर्माण O(nB) हैं और प्रत्येक ऑपरेशन O(B) है। एक rank-सपोर्टिंग कम्प्रेश्ड बिटवेक्टर स्पेस और कॉन्स्टेंट्स को कम करता है। यह संरचना इम्यूटेबल, क्वेरी-भारी वर्कलोड के अनुकूल है। अपडेट के लिए, ब्लॉक्ड रीबिल्ड, डायनामिक बिटवेक्टर, ऑर्डर्ड सेट्स का सेगमेंट ट्री, या ऑफ़लाइन प्रोसेसिंग पर विचार करें और मेमोरी तथा अपडेट लागतों का पुनर्मूल्यांकन करें।
नमूना सशक्त उत्तर
मैं स्पष्ट करूंगा कि रेंज हाफ़-ओपन हैं, k ज़ीरो-बेस्ड है, और ऐरे इम्यूटेबल है। मैं मानों को कोऑर्डिनेट-कम्प्रेस करूंगा और B बिट्स का उपयोग करूंगा। निर्माण उच्चतम बिट से नीचे की ओर स्टेबली पार्टिशन करता है, प्रत्येक स्तर पर प्रीफ़िक्स rank-one काउंट और ज़ीरो-ब्लॉक लंबाई बनाए रखता है।
k-वें के लिए, प्रत्येक स्तर वर्तमान इंटरवल में शून्यों की गणना करता है। यदि k शून्यों से संबंधित है, तो l-rank1(l) और r-rank1(r) के साथ मैप करें; अन्यथा शून्यों को घटाएं, zeroCount+rank1(l) और zeroCount+rank1(r) के साथ मैप करें, और उत्तर बिट सेट करें। फ़्रीक्वेंसी एक निश्चित मान पाथ का अनुसरण करती है, जबकि वैल्यू-डोमेन काउंट दो countLess कॉल्स हैं। निर्माण O(nB) है और प्रत्येक क्वेरी O(B) है, जिसमें अमान्य रेंज और अनुपस्थित कोड के लिए स्पष्ट त्रुटियां या शून्य हैं।
सामान्य गलतियां
- क्लोज्ड और हाफ़-ओपन रेंज को मिलाना → rank एक से शिफ्ट हो जाता है → लगातार
[l,r)का उपयोग करें और मैपिंग लिखें। - स्टेबल पार्टिशन भूल जाना → बाद के इंटरवल्स अब समान तत्वों की पहचान नहीं करते हैं → दोनों ब्लॉकों में क्रम बनाए रखें।
- शून्यों को घटाए बिना वन ब्लॉक में प्रवेश करना → k-वें मान बहुत बड़े हो जाते हैं → मैपिंग से पहले घटाएं।
- साइन्ड मानों की तुलना अनसाइन्ड बिट्स के रूप में करना → नेगेटिव गलत क्रम में आ जाते हैं → कम्प्रेस करें या साइन बिट को फ़्लिप करें।
- यह मान लेना कि अपडेट सस्ते हैं → अपडेट स्तर क्रमपरिवर्तन (permutations) को अमान्य कर देते हैं → स्टैटिक पूर्व शर्त और विकल्प बताएं।
- केवल विशिष्ट मानों का परीक्षण करना → डुप्लिकेट और सीमा त्रुटियां छिपी रहती हैं → समान, इंटरलीव्ड, खाली, और अमान्य मामलों का परीक्षण करें।
फ़ॉलो-अप प्रश्न और उत्तर
प्रत्येक रेंज को सॉर्ट क्यों न करें?
एक रेंज को सॉर्ट करने की लागत O((r-l) log(r-l)) है और यह सभी क्वेरीज़ में काम को दोहराता है। मैट्रिक्स ब्रांच की जानकारी की पहले से गणना करता है, इसलिए एक क्वेरी केवल B स्तरों पर जाती है और स्टैटिक, हाई-क्वेरी वर्कलोड के लिए उपयुक्त है।
rank1 इंटरवल्स को मैप क्यों करता है?
प्रीफ़िक्स rank बताता है कि प्रत्येक एंडपॉइंट से पहले कितने वन आते हैं, जो शून्य और वन ब्लॉक में इंटरवल की सापेक्ष स्थिति देता है। स्टेबल पार्टिशनिंग यह सुनिश्चित करती है कि वे स्थितियां समान तत्वों का प्रतिनिधित्व करती हैं।
आप k-वें सबसे बड़े मान का उत्तर कैसे देते हैं?
इसे length - 1 - k के साथ k-वें सबसे छोटे मान में बदलें, या प्रत्येक स्तर पर वन ब्रांच को प्राथमिकता दें और इसकी गणना को घटाएं। दोनों O(B) रहते हैं।
क्या होगा यदि वैल्यू डोमेन n से बहुत बड़ा है?
देखे गए मानों को कोऑर्डिनेट-कम्प्रेस करें और रिवर्स मैप बनाए रखें। एक अनदेखे क्वेरी मान के लिए, इसकी इंसर्शन बाउंड्री पर बाइनरी-सर्च करें या फ़्रीक्वेंसी शून्य लौटाएं।
क्या होगा यदि अपडेट की आवश्यकता है?
एक सादा वेवलेट मैट्रिक्स अपडेट-अनुकूल नहीं है। अपडेट/क्वेरी अनुपात, लेटेंसी लक्ष्यों और मेमोरी के आधार पर ब्लॉक्ड रीबिल्डिंग, डायनामिक बिटवेक्टर, ऑर्डर्ड स्ट्रक्चर्स का सेगमेंट ट्री, या ऑफ़लाइन प्रोसेसिंग का उपयोग करें।