प्रांप्ट और संदर्भ
get, put, और निष्कासन (eviction) का समर्थन करने वाला एक सीमित LRU-K कैश लागू करें। प्रति कुंजी नवीनतम K एक्सेस रखें। K से कम एक्सेस वाली प्रविष्टियां एक इतिहास-अपूर्ण स्तर (history-incomplete tier) बनाती हैं और उन्हें हॉट प्रविष्टियों से पहले निष्कासित किया जाना चाहिए। K, क्षमता, मौजूदा कुंजियों के अपडेट, समवर्ती कॉल और अनुपलब्ध कुंजियों को स्पष्ट करें।
साक्षात्कारकर्ता क्या परीक्षण कर रहा है
- क्या आप एक्सेस इतिहास और दो उम्मीदवार स्तरों (candidate tiers) को सही ढंग से बनाए रखते हैं।
- क्या आप हीप (heap), हैश मैप, या क्रमित संरचना चुन सकते हैं और लागत का विश्लेषण कर सकते हैं।
- क्या आप ओवरराइट्स, शून्य क्षमता, अमान्य K और समवर्ती दृश्यता (concurrent visibility) को संभालते हैं।
- क्या आप समझते हैं कि LRU-K हर वर्कलोड पर जीतने के बजाय स्कैन प्रदूषण (scan pollution) को फ़िल्टर करता है।
उत्तर देने से पहले स्पष्ट करने वाले प्रश्न
थ्रेड सुरक्षा, अनुमानित निष्कासन, म्यूटेबल मान, TTL आवश्यकताएं और हिट-दर मेट्रिक्स की पुष्टि करें। सख्त क्रमबद्धता के लिए आमतौर पर एक लॉक या क्रमबद्ध अपडेट की आवश्यकता होती है; उच्च थ्रूपुट के लिए शार्डिंग और एक अनुमानित नीति की आवश्यकता हो सकती है।
30-सेकंड उत्तर रूपरेखा
मान, नवीनतम K लॉजिकल टाइमस्टैम्प और प्रति कुंजी एक संस्करण (version) संग्रहीत करें। उम्मीदवारों को इतिहास-अपूर्ण और हॉट स्तरों में विभाजित करें। क्षमता से अधिक होने पर, अपूर्ण स्तर में सबसे पुराने आइटम को निष्कासित करें; अन्यथा सबसे छोटे K-वें सबसे हालिया टाइमस्टैम्प वाले हॉट आइटम को निष्कासित करें। एक हैश मैप O(1) लुकअप प्रदान करता है और हीप उम्मीदवारों को बनाए रखते हैं; संस्करण पुराने (stale) हीप नोड्स को त्याग देते हैं। सख्त get और put की अपेक्षित जटिलता O(log n) है, जिसमें O(capacity·K) इतिहास स्थान (space) होता है।
चरण-दर-चरण गहन विश्लेषण
1. एक्सेस इतिहास रिकॉर्ड करना
प्रत्येक हिट या राइट पर एक लॉजिकल क्लॉक मान जोड़ें और केवल नवीनतम K मानों को बनाए रखें। एक लॉजिकल क्लॉक वॉल-क्लॉक जंप के बिना क्रम की तुलना करती है और एक ही मिलीसेकंड में एक्सेस के बीच अंतर करती है। एक ओवरराइट को एक एक्सेस के रूप में गिना जाता है जब तक कि प्रांप्ट यह न कहे कि राइट्स को नहीं गिना जाता है।
2. निष्कासन उम्मीदवारों को बनाए रखना
अपूर्ण स्तर को उसके नवीनतम एक्सेस द्वारा क्रमबद्ध किया जाता है; हॉट स्तर को उसके K-वें सबसे हालिया एक्सेस द्वारा क्रमबद्ध किया जाता है। (key, version, rank) के दो मिन-हीप (min-heaps) बनाए रखें। एक नया एक्सेस एक नया नोड पुश करता है और संस्करण को बढ़ाता है; निष्कासन संस्करण और वर्तमान रैंक को मान्य करता है, पुराने नोड्स को छोड़ देता है।
3. सीमाएं और समवर्तिता
जब क्षमता शून्य या ऋणात्मक हो तो कैश न करें; K शून्य या ऋणात्मक होने पर अस्वीकार करें। निष्कासन और मान अपडेट को एक महत्वपूर्ण खंड (critical section) साझा करना चाहिए ताकि समवर्ती put कॉल क्षमता से अधिक न हो सकें। शार्ड किए गए लॉक थ्रूपुट में सुधार करते हैं, लेकिन फिर वैश्विक क्षमता के लिए समन्वय की आवश्यकता होती है।
उच्च-गुणवत्ता वाला नमूना उत्तर
मैं प्रविष्टियों को इतिहास-अपूर्ण और हॉट स्तरों में अलग करता हूँ। प्रत्येक प्रविष्टि अपने मान, नवीनतम K लॉजिकल समय और संस्करण को संग्रहीत करती है; एक एक्सेस इतिहास को अपडेट करता है और प्रासंगिक मिन-हीप में एक नया रैंक नोड पुश करता है। निष्कासन पहले अपूर्ण हीप की जाँच करता है, फिर हॉट हीप की, पुराने नोड्स को छोड़ने के लिए संस्करणों को मान्य करता है। मैप के माध्यम से लुकअप O(1) है, हीप कार्य O(log n) है, और इतिहास स्थान O(capacity·K) है। परीक्षण K=1 के LRU की तरह व्यवहार करने, बार-बार एक्सेस के बाद पदोन्नति (promotion), एक बार के स्कैन, ओवरराइट्स, शून्य क्षमता, समवर्ती अधिक-क्षमता वाले राइट्स, पुराने हीप नोड्स और हिट दर को कवर करते हैं। LRU-K स्कैन प्रदूषण को लक्षित करता है; Redis नमूना-आधारित LRU सन्निकटन का उपयोग करता है और PostgreSQL क्लॉक-स्वीप का उपयोग करता है, इसलिए उनकी लागत और व्यवहार को एक समान नहीं माना जाना चाहिए।
सामान्य गलतियाँ
- एक टाइमस्टैम्प रखना और गलती से सामान्य LRU लागू करना।
- नवीनतम एक्सेस को K-वें सबसे हालिया एक्सेस के रूप में मानना।
- डुप्लिकेट पुराने नोड्स को संभाले बिना हीप रूट को हटाना।
- समवर्ती
putकॉल को क्षमता से अधिक होने देना या लॉक के बाहर इतिहास को अपडेट करना। - यह दावा करना कि LRU-K हमेशा LRU से बेहतर होता है।
अनुवर्ती प्रश्न और उत्तर
K बराबर 1 होने पर क्या होना चाहिए?
पहला एक्सेस एक प्रविष्टि को हॉट सिमेंटिक्स देता है, इसलिए निष्कासन को उसके नवीनतम एक्सेस द्वारा क्रमबद्ध किया जाता है और नीति सामान्य LRU क्रमबद्धता में बदल जाती है।
आप हीप-नोड मेमोरी को कैसे कम कर सकते हैं?
डुप्लिकेट नोड्स को कम करने के लिए इंडेक्स और म्यूटेबल हीप का उपयोग करें, या जेनरेशनल कतारों (generational queues) या नमूना-आधारित निष्कासन को चुनें। स्पष्ट करें कि क्रमबद्धता अनुमानित हो जाती है और हिट दर को फिर से मापें।
आप कम हुए स्कैन प्रदूषण को कैसे मापेंगे?
एक चक्रीय हॉट सेट बनाएं, फिर केवल एक बार एक्सेस की जाने वाली कई कुंजियां डालें। हॉट-सेट हिट दर, निष्कासन, विलंबता (latency) और मेमोरी पर LRU और LRU-K की तुलना करें, जिसमें क्षमता के करीब का हॉट सेट शामिल हो।