प्रश्न और लागू संदर्भ
धनात्मक पूर्णांक capacity के लिए LRUCache(capacity) लागू करें। कीज़ (keys) और मान (values) गैर-ऋणात्मक पूर्णांक हैं। get(key) संग्रहीत मान लौटाता है या की अनुपस्थित होने पर -1 लौटाता है। put(key, value) किसी की को इन्सर्ट या अपडेट करता है। एक सफल get और प्रत्येक put उस की को सबसे हाल ही में उपयोग किया गया (most recently used) बना देते हैं। जब कैश भरा हो, तब एक नई की इन्सर्ट करने से ठीक एक सबसे कम हाल ही में उपयोग की गई (least recently used) की निष्कासित हो जाती है। दोनों सार्वजनिक ऑपरेशन्स में अपेक्षित O(1) समय लगना चाहिए।
यह डेटा-स्ट्रक्चर कोडिंग का सवाल है, वितरित-कैश (distributed-cache) डिज़ाइन नहीं। यह कार्यान्वयन सिंगल-प्रोसेस और सिंगल-थ्रेडेड है; इसमें TTL, पर्सिस्टेंस, आकार-आधारित वेट या समवर्ती (concurrent) एक्सेस शामिल नहीं है। "अपेक्षित O(1)" हैश-टेबल ऑपरेशन्स के सामान्य औसत-प्रदर्शन धारणा पर निर्भर करता है। लिंक्ड लिस्ट में पॉइंटर परिवर्तन वर्स्ट-केस O(1) होते हैं।
महत्वपूर्ण परिणाम केवल "हैश मैप प्लस डबली लिंक्ड लिस्ट" वाक्यांश नहीं है। एक संपूर्ण उत्तर यह स्पष्ट करता है कि दोनों संरचनाएँ क्यों आवश्यक हैं, मैप-लिस्ट इनवेरिएंट बताता है, बिना किसी आकस्मिक एविक्शन के मौजूदा-की अपडेट को संभालता है, और प्रत्येक ऑपरेशन के बाद क्रम की पुष्टि करता है।
साक्षात्कारकर्ता क्या मूल्यांकन करता है
पहला संकेत आवश्यकताओं को ऑपरेशन्स में बदलना है। बिना स्कैन किए किसी की को खोजना आवश्यक है, जिसके लिए हैश मैप की आवश्यकता होती है। रीसेंसी (recency) को किसी भी हिट को सबसे हालिया छोर पर ले जाने और सबसे पुराने छोर को हटाने का समर्थन करना चाहिए। जब मैप पहले से ही नोड प्रदान करता है, तो एक डबली लिंक्ड लिस्ट दोनों काम स्थिर पॉइंटर वर्क में कर सकती है।
दूसरा संकेत यह है कि क्या दोनों संरचनाएँ एक ही स्थिति (state) बनाती हैं। मैप केवल मान संग्रहीत नहीं कर सकता; इसे प्रत्येक की को उसके लिस्ट नोड से मैप करना होगा। प्रत्येक वास्तविक लिस्ट नोड की ठीक एक मैप प्रविष्टि होनी चाहिए, और प्रत्येक मैप प्रविष्टि को लिस्ट में ठीक एक वास्तविक नोड की ओर इंगित करना चाहिए। इसलिए एविक्शन दोनों संरचनाओं से समान की को हटाता है।
तीसरा संकेत पॉइंटर अनुशासन है। डमी हेड और टेल नोड्स सभी वास्तविक नोड्स को आंतरिक नोड्स बनाते हैं। डिटैच और इन्सर्ट को पहले, अंतिम या एकमात्र प्रविष्टि के लिए किसी विशेष मामले की आवश्यकता नहीं होती है। उम्मीदवार को कोडिंग से पहले यह बताने में सक्षम होना चाहिए कि कौन सा पक्ष सबसे हालिया है और उस परिपाटी को अपरिवर्तित रखना चाहिए।
अंत में, साक्षात्कारकर्ता ऐसे परीक्षणों की तलाश करता है जो केवल लौटाए गए मानों को ही नहीं, बल्कि क्रम को भी उजागर करते हैं। पूरी क्षमता पर मौजूदा की को अपडेट करना, बार-बार एक ही की को पढ़ना, क्षमता एक का उपयोग करना, और मिस के बाद इन्सर्ट करना ऐसे बग्स को उजागर करते हैं जो एक साधारण हैप्पी-पाथ उदाहरण में छूट जाते हैं।
उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न
- क्या
getरीसेंसी को अपडेट करता है? इस अनुबंध में यह करता है। केवल पढ़ने वाला (read-only)peekएक अलग ऑपरेशन होगा और नोड को स्थानांतरित नहीं करेगा। - क्या किसी मौजूदा की को अपडेट करने से क्षमता की खपत होती है? नहीं।
putउसी प्रविष्टि के मान और रीसेंसी को बदलता है; इसे किसी अन्य की को निष्कासित नहीं करना चाहिए। - मिस होने पर क्या लौटता है? यह समस्या
-1का उपयोग करती है, इसलिए मानों को उसी के अनुसार सीमित किया जाना चाहिए या एपीआई को एक वैकल्पिक मान लौटाना चाहिए। यहाँ मान गैर-ऋणात्मक पूर्णांक हैं और-1मिस के लिए आरक्षित है। - क्या शून्य क्षमता मान्य है? यह कार्यान्वयन गैर-धनात्मक क्षमता को अस्वीकार करता है। शून्य का समर्थन करने के लिए प्रत्येक इन्सर्शन को तुरंत गायब होना पड़ेगा और यह कंस्ट्रक्टर अनुबंध को बदल देता है।
- क्या गारंटी सख्त वर्स्ट-केस
O(1)होनी चाहिए? हैश टेबल सामान्यतः अपेक्षित स्थिर समय प्रदान करते हैं। एक सख्त वर्स्ट-केस गारंटी के लिए एक अलग लुकअप संरचना या मजबूत धारणाओं की आवश्यकता होती है। - क्या एक मानक ऑर्डर्ड मैप का उपयोग किया जा सकता है? यह प्रोडक्शन या एक छोटे अभ्यास में स्वीकार्य हो सकता है, लेकिन साक्षात्कारकर्ता अभी भी अंतर्निहित लिंक्ड-लिस्ट कार्यान्वयन और इसके इनवेरिएंट्स की मांग कर सकता है।
- क्या थ्रेड सुरक्षा आवश्यक है? नहीं। यदि इसे जोड़ा जाता है, तो याद रखें कि
getरीसेंसी को म्यूटेट करता है, इसलिए यह सिंक्रोनाइज़ेशन के उद्देश्यों के लिए एक राइट (write) ऑपरेशन है।
30-सेकंड उत्तर ढांचा
"मुझे अपेक्षित स्थिर-समय लुकअप और रीसेंसी अपडेट की आवश्यकता है, इसलिए मैं प्रत्येक की को डबली लिंक्ड लिस्ट के एक नोड से मैप करूँगा। हेड साइड सबसे हालिया है और टेल साइड सबसे पुरानी; सेंटिनल्स डिटैच और इन्सर्ट को एकसमान बनाते हैं। एक हिट या अपडेट अपने नोड को आगे ले जाता है। क्षमता से अधिक नया इन्सर्ट दोनों संरचनाओं से tail.prev को हटा देता है। क्योंकि मैप और लिस्ट में समान वास्तविक नोड्स होते हैं, get और put अपेक्षित O(1) हैं, जिसमें O(capacity) स्पेस लगता है।"
चरण-दर-चरण विस्तृत उत्तर
अकेले एक लिस्ट रीसेंसी को बनाए रखती है, लेकिन किसी की को खोजने या किसी मनमाने नोड को हटाने में O(n) लागत आती है। केवल एक मैप मान को तेज़ी से ढूंढता है, लेकिन यह स्कैन किए बिना या दूसरी ऑर्डरिंग संरचना को संग्रहीत किए बिना सबसे कम हाल ही में उपयोग की गई की की पहचान नहीं कर सकता है। एक ऐरे और मैप में अभी भी O(n) शिफ्ट या पूर्ववर्ती की खोज होती है। ये दो आवश्यकताएं एक लुकअप इंडेक्स और एक परिवर्तनीय क्रम को अनिवार्य बनाती हैं।
पूरे उत्तर में इस ओरिएंटेशन का उपयोग करें:
head <-> most recent <-> ... <-> least recent <-> tailसेंटिनल्स कभी भी मैप में प्रवेश नहीं करते हैं और कभी भी क्षमता में नहीं गिने जाते हैं। प्रत्येक वास्तविक नोड key, value, prev, और next संग्रहीत करता है; की को संग्रहीत करना आवश्यक है क्योंकि एविक्शन tail.prev से शुरू होता है और बिना रिवर्स स्कैन के मैचिंग मैप प्रविष्टि को हटाना आवश्यक होता है।
चार इनवेरिएंट कार्यान्वयन को समीक्षा योग्य बनाते हैं:
- जब कैश खाली न हो, तो
head.nextसबसे हाल ही में उपयोग किया गया वास्तविक नोड है, औरtail.prevसबसे कम हाल ही में उपयोग किया गया वास्तविक नोड है। - मैप कीज़ और वास्तविक लिस्ट नोड्स एक-से-एक (one-to-one) आधार पर प्रविष्टियों के समान सेट का वर्णन करते हैं।
- प्रत्येक आसन्न युग्म के लिए,
left.next is rightऔरright.prev is left। - प्रत्येक सार्वजनिक ऑपरेशन के बाद,
0 <= len(nodes) <= capacity।
कार्यान्वयन पॉइंटर हेरफेर को दो हेल्पर्स में रखता है क्योंकि get और put दोनों वास्तव में इसका पुन: उपयोग करते हैं:
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _detach(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _attach_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _mark_recent(self, node: Node) -> None:
self._detach(node)
self._attach_after_head(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
self._mark_recent(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._mark_recent(node)
return
node = Node(key, value)
self.nodes[key] = node
self._attach_after_head(node)
if len(self.nodes) > self.capacity:
victim = self.tail.prev
self._detach(victim)
del self.nodes[victim.key]_attach_after_head में पॉइंटर असाइनमेंट का क्रम मायने रखता है। नया नोड पहले पुराने पहले नोड को कैप्चर करता है, फिर वह पुराना नोड वापस नए नोड की ओर इशारा करता है, और उसके बाद ही head.next बदलता है। head.next को बहुत जल्दी ओवरराइट करने से वह पड़ोसी खो सकता है जिसे अभी भी अपने prev को अपडेट करने की आवश्यकता है।
शुद्धता ऑपरेशन्स पर इंडक्शन द्वारा सिद्ध होती है। इनिशियलाइज़ेशन सभी चार इनवेरिएंट्स को संतुष्ट करता है। मिस होने पर कुछ नहीं बदलता। एक हिट या मौजूदा-की अपडेट एक मैप किए गए नोड को डिटैच करता है और उसी नोड को सामने फिर से इन्सर्ट करता है, इसलिए सदस्यता और आकार नहीं बदलते हैं। एक नया इन्सर्शन दोनों संरचनाओं में नोड जोड़ता है; यदि आकार capacity + 1 हो जाता है, तो लिस्ट से tail.prev और मैप से उसकी की को हटाने से एक-से-एक सेट और क्षमता सीमा बहाल हो जाती है। धनात्मक क्षमता यह सुनिश्चित करती है कि हटाया जाने वाला नोड एक वास्तविक नोड है।
दो की क्षमता के साथ, ट्रेस put(1,10), put(2,20), get(1), put(3,30), put(1,15) रीसेंसी क्रम [1], [2,1], [1,2], [3,1], [1,3] उत्पन्न करता है। की 2 निष्कासित हो जाती है, जबकि की 1 को अपडेट करने से की 3 को निष्कासित किए बिना इसका मान बदल जाता है।
औसत हैश-टेबल प्रदर्शन के तहत, प्रत्येक सार्वजनिक मेथड एक लुकअप और पॉइंटर तथा मैप ऑपरेशन्स की एक निश्चित संख्या निष्पादित करती है, इसलिए अपेक्षित समय O(1) है। मैप और लिस्ट में अधिकतम capacity वास्तविक नोड्स होते हैं, इसलिए स्पेस O(capacity) है। यह एक सख्त वर्स्ट-केस हैश-टेबल गारंटी नहीं है।
सत्यापन में उदाहरण ट्रेसेस को इनवेरिएंट जांच के साथ जोड़ना चाहिए। खाली कैश मिस, अस्वीकृत शून्य क्षमता, क्षमता एक, विभिन्न कीज़ के तहत दोहराए गए मान, पूरी क्षमता पर अपडेट, बार-बार हिट, बारी-बारी से एविक्शन, और एक लंबी यादृच्छिक (random) ऑपरेशन स्ट्रीम का परीक्षण करें। यादृच्छिक परीक्षण के लिए, एक सरल O(n) संदर्भ मॉडल के साथ परिणामों और क्रम की तुलना करें और प्रत्येक ऑपरेशन के बाद रेसिप्रोकल पॉइंटर्स, कोई डुप्लिकेट नोड्स नहीं, मैप-लिस्ट समानता और क्षमता सीमा का दावा (assert) करें।
जब लाइब्रेरीज़ की अनुमति हो, तो एक एक्सेस-ऑर्डर्ड मैप उसी नीति को अधिक संक्षिप्त रूप से व्यक्त कर सकता है। Java का LinkedHashMap एक्सेस ऑर्डर और एल्डेस्ट-एंट्री रिमूवल हुक का समर्थन करता है। यह एक उपयोगी प्रोडक्शन विकल्प है, लेकिन यह साक्षात्कार के प्रमाण का स्थान नहीं लेता है। इसके अलावा सटीक इन-प्रोसेस LRU को प्रोडक्शन एविक्शन से अलग रखें: एक सर्वर ग्लोबल मेटाडेटा और कंटेंशन को कम करने के लिए सैम्पल्ड अनुमानित (approximate) LRU का उपयोग कर सकता है।
उच्च-गुणवत्ता वाला नमूना उत्तर
"मैं पहले अनुबंध को तय करूँगा: धनात्मक क्षमता, मिस पर get द्वारा -1 लौटाना, और प्रत्येक हिट या put द्वारा रीसेंसी अपडेट करना। किसी मौजूदा की को अपडेट करने से आकार नहीं बढ़ता है। औसत हैश-टेबल लुकअप के आधार पर लक्ष्य अपेक्षित O(1) है।
एक हैश मैप की लुकअप को हल करता है लेकिन एविक्शन क्रम को नहीं। एक डबली लिंक्ड लिस्ट क्रम को हल करती है और मुझे स्थिर पॉइंटर वर्क में एक मनमाने नोड को अनलिंक करने देती है, बशर्ते मेरे पास पहले से वह नोड हो। इसलिए मैं मैप में key -> node स्टोर करता हूँ और नोड्स को डमी हेड के बाद सबसे हालिया से लेकर डमी टेल से पहले सबसे पुराने तक व्यवस्थित करता हूँ। नोड्स अपनी की को स्टोर करते हैं ताकि टेल एविक्शन मैप प्रविष्टि को भी हटा सके।
मुख्य इनवेरिएंट यह है कि मैप और वास्तविक लिस्ट नोड्स एक ही सेट हैं। हिट होने पर, मैं उस नोड को डिटैच करता हूँ और उसे हेड के बाद इन्सर्ट करता हूँ। अपडेट पर, मैं उसका मान बदलता हूँ और वही चाल चलता हूँ। एक नए put पर, मैं इसे दोनों संरचनाओं में जोड़ता हूँ; यदि आकार क्षमता से अधिक हो जाता है, तो मैं दोनों से tail.prev हटा देता हूँ। सेंटिनल्स इन ऑपरेशन्स को पहली, अंतिम और एकमात्र प्रविष्टि के लिए समान बनाते हैं।
मैं क्षमता एक, भरे होने पर अपडेट, बार-बार get जो विक्टिम को बदलते हैं, और एक मिस जो क्रम को नहीं बदलना चाहिए, का परीक्षण करूँगा। मैं प्रत्येक यादृच्छिक ऑपरेशन के बाद लिस्ट का भी निरीक्षण करूँगा और एक धीमे संदर्भ मॉडल के साथ इसकी तुलना करूँगा। अंतिम जटिलता प्रति ऑपरेशन अपेक्षित O(1) और O(capacity) स्पेस है।"
सामान्य गलतियाँ
- मैप में केवल मान स्टोर करना → एक हिट को अभी भी क्रम संरचना खोजने की आवश्यकता होती है → प्रत्येक की को सीधे उसके लिस्ट नोड से मैप करें।
- सिंगली लिंक्ड लिस्ट का उपयोग करना → मैप नोड प्रदान करता है लेकिन उसका पूर्ववर्ती नहीं, इसलिए मनमाने निष्कासन के लिए स्कैन की आवश्यकता हो सकती है →
prevऔरnextदोनों स्टोर करें। - प्रत्येक नोड के अंदर की को भूल जाना → टेल एविक्शन रिवर्स लुकअप के बिना मैप प्रविष्टि को नहीं हटा सकता → नोड में की और मान दोनों स्टोर करें।
- इन्सर्शन क्रम को रीसेंसी मानना → एक सफल
getभविष्य के विक्टिम को बदलने में विफल रहता है → प्रत्येक हिट को सबसे हालिया छोर पर ले जाएं। - मौजूदा-की अपडेट पर निष्कासित करना → आकार नहीं बढ़ा, इसलिए एक असंबद्ध प्रविष्टि गायब हो जाती है → नई-प्रविष्टि क्षमता जांच से पहले अपडेट और रिटर्न को संभालें।
- केवल एक संरचना से विक्टिम को हटाना → पुरानी मैप प्रविष्टियां या घोस्ट लिस्ट नोड्स बाद के ऑपरेशन्स को तोड़ देते हैं → सममित रूप से एविक्शन करें और मैप-लिस्ट समानता का परीक्षण करें।
- अलग हेड, टेल और सिंगलटन शाखाएँ लिखना → पॉइंटर के मामले बढ़ जाते हैं और अंततः एक सीमा विचलित हो जाती है → दो स्थायी सेंटिनल्स का उपयोग करें।
- सख्त
O(1)का दावा करना → हैश टेबल आम तौर पर एक अपेक्षित सीमा देते हैं और टकराव (collisions) के तहत ख़राब हो सकते हैं → हैशिंग धारणा का उल्लेख करें। - केवल रिटर्न मानों का परीक्षण करना → सही मान बाद के एविक्शन तक दूषित क्रम को छिपा सकते हैं → पूर्ण रीसेंसी अनुक्रम और पॉइंटर इनवेरिएंट्स का दावा (assert) करें।
फॉलो-अप सवाल और उत्तर
फॉलो-अप 1: आप इसे थ्रेड-सुरक्षित कैसे बनाएंगे?
get एक राइट है क्योंकि यह लिस्ट को बदलता है। सबसे सरल सही विस्तार पूरे get या put के चारों ओर एक म्यूटेक्स (mutex) लगाता है, जिससे मैप और लिस्ट अपडेट परमाणु (atomic) रहता है। रीड-राइट लॉकिंग साधारण हिट्स को रीडर्स नहीं बनाती है। शार्डिंग कंटेंशन को कम करती है, लेकिन फिर प्रत्येक शार्ड का अपना LRU क्रम होता है; यह अब एक सटीक ग्लोबल LRU को लागू नहीं करता है जब तक कि एक साझा ऑर्डरिंग तंत्र फिर से प्रस्तुत न किया जाए।
फॉलो-अप 2: आप TTL समाप्ति कैसे जोड़ेंगे?
TTL और रीसेंसी अलग-अलग एविक्शन नियम हैं। एक हिट को पहले समाप्त हो चुकी प्रविष्टियों को अस्वीकार करना चाहिए, जबकि put को क्षमता नीति लागू करने से पहले समाप्त हो चुकी प्रविष्टियों को हटाने की आवश्यकता हो सकती है। समाप्ति समय का एक मिन-हीप (min-heap) लेज़ी क्लीनअप का समर्थन करता है लेकिन O(log n) रखरखाव और बासी हीप रिकॉर्ड जोड़ता है; एक टाइमिंग व्हील सटीकता और कार्यान्वयन को बदलता है। समाप्ति तंत्र और सीमा को फिर से परिभाषित किए बिना दोनों ऑपरेशन्स के O(1) होने का दावा न करते रहें।
फॉलो-अप 3: क्या आप सख्त वर्स्ट-केस O(1) प्रदान कर सकते हैं?
लिंक्ड-लिस्ट वाले हिस्से में पहले से ही पॉइंटर ऑपरेशन्स की एक सख्त स्थिर संख्या होती है। लुकअप वाला हिस्सा हैश टेबल की गारंटियों पर निर्भर करता है। सख्त वर्स्ट-केस स्थिर लुकअप प्राप्त करने के लिए एक मजबूत डिक्शनरी मॉडल, डायरेक्ट एड्रेसिंग के साथ सीमित की यूनिवर्स, या विशेष हैशिंग धारणाओं की आवश्यकता होती है। एक सामान्य भाषा के हैश मैप में, उस कार्यान्वयन के अनुबंध के अनुसार परिणाम को अपेक्षित या एमॉर्टाइज़्ड O(1) के रूप में वर्णित करें।
फॉलो-अप 4: LinkedHashMap या OrderedDict का उपयोग क्यों न करें?
लाइब्रेरी का उपयोग तब करें जब इसके एक्सेस-ऑर्डर और एविक्शन सिमेंटिक्स उत्पाद से मेल खाते हों और मैन्युअल पॉइंटर कोड कोई अतिरिक्त मूल्य न जोड़ता हो। एक साक्षात्कार में, पहले अंतर्निहित मैप और लिंक्ड-ऑर्डर इनवेरिएंट की व्याख्या करें, फिर लाइब्रेरी विकल्प प्रस्तुत करें। सत्यापित करें कि क्या अपडेट करना, पढ़ना, पुनरावृत्ति (iteration), और एल्डेस्ट निष्कासन को एक्सेस के रूप में गिना जाता है; समान नाम वाले ऑर्डर्ड मैप्स सभी समान रीसेंसी सिमेंटिक्स साझा नहीं करते हैं।
फॉलो-अप 5: क्या आप बड़े कैश सर्वर में सटीक LRU का उपयोग करेंगे?
स्वचालित रूप से नहीं। एक सटीक ग्लोबल एक्सेस क्रम बनाए रखने से मेटाडेटा राइट्स और प्रत्येक हिट पर एक कंटेंशन पॉइंट जुड़ जाता है। एक प्रोडक्शन कैश क्रम को शार्ड कर सकता है, कैंडिडेट कीज़ का नमूना (sample) ले सकता है, या LFU चुन सकता है जब फ्रीक्वेंसी पुन: उपयोग का बेहतर अनुमान लगाती है। वे विकल्प मेमोरी और थ्रूपुट के लिए सटीक विक्टिम चयन का समझौता करते हैं। साक्षात्कार वाला ऑब्जेक्ट अभी भी उपयोगी है क्योंकि यह सटीक नीति और उसके इनवेरिएंट्स को परीक्षण योग्य बनाता है।