कोडिंग इंटरव्यू: आप O(1) LFU कैश कैसे लागू करते हैं?

समस्या और दायरा

एक निश्चित क्षमता वाला LFUCache लागू करें। यदि कोई की मौजूद है, तो get(key) उसका मान लौटाता है और उसकी एक्सेस फ्रीक्वेंसी को बढ़ाता है; अन्यथा यह -1 लौटाता है। put(key, value) एक नई की डालता है या मौजूदा मान को बदलता है। किसी मौजूदा की को अपडेट करना भी एक एक्सेस माना जाता है। एक नई की फ्रीक्वेंसी 1 से शुरू होती है। पूरी क्षमता वाले कैश में इंसर्ट करते समय, सबसे कम फ्रीक्वेंसी वाली की को एविक्ट (हटा) करें। यदि कई कीज़ समान फ्रीक्वेंसी साझा करती हैं, तो उनमें से सबसे कम हाल ही में उपयोग की गई (least recently used) की को एविक्ट करें।

get और put दोनों को हैश मैप्स के सामान्य औसत-प्रदर्शन धारणा के तहत अपेक्षित O(1) समय में चलना चाहिए। 0 की क्षमता मान्य है और यह प्रत्येक put को एक नो-ऑप (no-op) बना देती है। दायरा एक सिंगल-थ्रेडेड, इन-मेमोरी डेटा संरचना है। TTL, बाइट-आधारित क्षमता, पर्सिस्टेंस और डिस्ट्रीब्यूटेड कंसिस्टेंसी शामिल नहीं हैं।

दिसंबर 2025 का एक चीनी सार्वजनिक इंटरव्यू रिकॉर्ड स्पष्ट रूप से LFU Cache को सूचीबद्ध करता है, और 2026 का एक सार्वजनिक इंटरव्यू पेज उसी समस्या को बनाए रखता है। LeetCode 460 एक स्थिर कॉन्ट्रैक्ट प्रदान करता है, जबकि O(1) LFU पेपर दो-स्तरीय लिंक्ड संरचना का विवरण देता है। यह किसी स्वतंत्र रूप से सत्यापित कंपनी एट्रिब्यूशन को स्थापित किए बिना प्रश्न की वर्तमान प्रासंगिकता का समर्थन करता है, इसलिए companyName नल (null) रहता है।

साक्षात्कारकर्ता क्या मूल्यांकन करता है

पहला, क्या उम्मीदवार दो एविक्शन आयामों से संरचना प्राप्त कर सकता है? की लुकअप के लिए हैश मैप की आवश्यकता होती है। फ्रीक्वेंसी द्वारा चयन के लिए फ्रीक्वेंसी इंडेक्स की आवश्यकता होती है। समान फ्रीक्वेंसी वाली कीज़ को अभी भी रीसेंसी (recency) क्रम की आवश्यकता होती है। एक सिंगल हीप (heap) सबसे कम फ्रीक्वेंसी पा सकता है, लेकिन प्रत्येक हिट प्राथमिकता को बदलता है और आमतौर पर O(log capacity) की लागत लेता है।

दूसरा, क्या उम्मीदवार इनवेरिएंट्स (invariants) बता सकता है? प्रत्येक की को सटीक रूप से एक नोड की पहचान करनी चाहिए। प्रत्येक नोड को अपनी फ्रीक्वेंसी से मेल खाने वाले सटीक रूप से एक बकेट से संबंधित होना चाहिए। प्रत्येक बकेट को सबसे हालिया से लेकर सबसे पुराने क्रम में व्यवस्थित किया जाता है। minFrequency को वर्तमान में मौजूद सबसे छोटी फ्रीक्वेंसी की पहचान करनी चाहिए। केवल “दो मैप और एक डबल लिंक्ड लिस्ट” रटने से खाली-बकेट विलोपन, अपडेट या कैपेसिटी-वन व्यवहार स्पष्ट नहीं होता है।

तीसरा, क्या टाई-ब्रेक सही रहता है? जब कोई नोड फ्रीक्वेंसी f से f + 1 पर जाता है, तो यह अपने नए बकेट के सबसे हालिया छोर में प्रवेश करता है क्योंकि ट्रिगर करने वाला एक्सेस अभी-अभी हुआ है। एविक्शन न्यूनतम-फ्रीक्वेंसी बकेट से सबसे पुराने नोड को हटाता है। एक अनऑर्डर्ड सेट पहले LFU नियम को संतुष्ट कर सकता है लेकिन LRU टाई-ब्रेक खो देता है।

अंत में, साक्षात्कारकर्ता एक जटिलता प्रमाण और एक परीक्षण रणनीति सुनना चाहता है। प्रत्येक ऑपरेशन केवल मैप ऑपरेशन्स, बकेट लुकअप और लिंक्ड-लिस्ट परिवर्तनों की एक निश्चित संख्या ही कर सकता है। परीक्षणों में फ्रीक्वेंसी टाई, एक पुराना न्यूनतम बकेट खाली होना, मौजूदा की का अपडेट, शून्य क्षमता, और लंबे रैंडम अनुक्रमों पर एक धीमे संदर्भ मॉडल के विरुद्ध डिफ़रेंशियल तुलना शामिल होनी चाहिए।

उत्तर देने से पहले स्पष्ट करने वाले प्रश्न

• क्या किसी मौजूदा की को अपडेट करने से उसकी फ्रीक्वेंसी बढ़ती है? हाँ। मान बदलने के बाद, put उसी प्रमोशन पाथ का उपयोग करता है जैसा कि एक सफल get करता है।
• समान फ्रीक्वेंसी का समाधान कैसे किया जाता है? उस फ्रीक्वेंसी के भीतर LRU द्वारा: उस की को एविक्ट करें जिसका अंतिम सफल get या अपडेट करने वाला put सबसे पुराना है।
• क्या नई की फ्रीक्वेंसी 0 से शुरू होती है या 1 से? 1 से, क्योंकि इंसर्शन स्वयं एक उपयोग के रूप में गिना जाता है।
• क्या क्षमता 0 मान्य है? हाँ। प्रत्येक put तुरंत वापस लौटता है, और प्रत्येक get मिस (miss) होता है।
• क्या लक्ष्य सख्त वर्स्ट-केस O(1) है? लिंक्ड-लिस्ट परिवर्तन वर्स्ट-केस में कॉन्स्टेंट होते हैं। सामान्य मैप्स सामान्य औसत या अपेक्षित कॉन्स्टेंट-टाइम गारंटी देते हैं, इसलिए समग्र दावा अपेक्षित O(1) का है।
• क्या फ्रीक्वेंसी बिना किसी सीमा के बढ़ सकती है? इंटरव्यू कार्यान्वयन आमतौर पर मानते हैं कि पूर्णांक एक सुरक्षित सीमा में रहते हैं। एक लंबे समय तक चलने वाले प्रोडक्शन कैश को ओवरफ्लो, एजिंग या रीनॉर्मलाइजेशन को परिभाषित करना चाहिए, जो कॉन्ट्रैक्ट को बदलता है।
• क्या कैश थ्रेड-सेफ होना चाहिए? नहीं। चूंकि get फ्रीक्वेंसी और क्रम को बदलता है, इसलिए एक समवर्ती (concurrent) संस्करण को मल्टी-स्ट्रक्चर अपडेट को एक क्रिटिकल सेक्शन बनाना होगा।

30-सेकंड उत्तर रूपरेखा

“मैं की से नोड के लिए एक मैप और फ्रीक्वेंसी से डबल लिंक्ड लिस्ट के लिए दूसरा मैप उपयोग करूँगा। प्रत्येक लिस्ट में केवल समान-फ्रीक्वेंसी वाले नोड्स होते हैं, जो आगे सबसे नए और पीछे सबसे पुराने क्रम में होते हैं। minFrequency सीधे एविक्शन बकेट की पहचान करता है। एक सफल get या अपडेटिंग put नोड को फ्रीक्वेंसी f से हटाता है, आवश्यकता पड़ने पर खाली पुराने बकेट को हटाता है, फ्रीक्वेंसी बढ़ाता है, और नोड को नए बकेट के आगे जोड़ता है। एक नई की के लिए, यदि कैश भरा हुआ है, तो मैं minFrequency बकेट के पिछले नोड को हटा देता हूँ; फिर मैं नए नोड को फ्रीक्वेंसी 1 में जोड़ता हूँ और न्यूनतम को 1 पर सेट करता हूँ। प्रत्येक चरण मैप और पॉइंटर ऑपरेशन्स की एक निश्चित संख्या का उपयोग करता है, इसलिए get और put अपेक्षित O(1) हैं, O(capacity) स्पेस के साथ।”

चरण-दर-चरण समाधान

चरण 1: सीधे दृष्टिकोणों को हटाएँ जो सीमा को पूरा नहीं करते

key से {value, frequency, lastUsed} तक के एक मैप के साथ, एविक्शन सभी कीज़ को स्कैन करता है और इसकी लागत O(capacity) होती है। एक मिन-हीप (min-heap) एविक्शन को O(log capacity) तक कम कर देता है, लेकिन एक सफल एक्सेस फ्रीक्वेंसी और रीसेंसी दोनों को बदल देता है, जिसके लिए स्थिति इंडेक्स और हीप रिपेयर की आवश्यकता होती है। (frequency, time) द्वारा ऑर्डर्ड एक बैलेंस्ड ट्री की लागत भी O(log capacity) होती है।

अपेक्षित O(1) के लिए क्रम को विभाजित करने की आवश्यकता होती है। एक मैप सीधे फ्रीक्वेंसी का पता लगाता है। एक डबल लिंक्ड लिस्ट केवल एक ही फ्रीक्वेंसी के नोड्स के बीच रीसेंसी बनाए रखती है और एक ज्ञात नोड के लिए रिमूवल, फ्रंट इंसर्शन और बैक रिमूवल का समर्थन करती है। एक पूर्णांक वर्तमान न्यूनतम फ्रीक्वेंसी को रिकॉर्ड करता है।

चरण 2: चार इनवेरिएंट्स को परिभाषित करें

1. nodes में प्रत्येक की सटीक रूप से एक वास्तविक नोड को इंगित करती है, और प्रत्येक वास्तविक नोड nodes में दिखाई देता है।
2. फ्रीक्वेंसी f वाला नोड केवल frequencyLists.get(f) में दिखाई देता है; मैप कोई खाली लिस्ट नहीं रखता है।
3. प्रत्येक फ्रीक्वेंसी लिस्ट आगे सबसे हाल ही में उपयोग किए गए से लेकर पीछे सबसे कम हाल ही में उपयोग किए गए तक चलती है।
4. जब कैश खाली नहीं होता है, तो minFrequency सभी नोड्स की न्यूनतम फ्रीक्वेंसी होती है; कैश खाली होने पर यह 0 होता है।

एक प्रमोशन किसी नोड को केवल f से f + 1 पर ले जाता है। यदि f न्यूनतम है और इसका बकेट खाली हो जाता है, तो नया न्यूनतम बिल्कुल f + 1 होता है: कोई निचला बकेट मौजूद नहीं था, और प्रमोट किया गया नोड यह गारंटी देता है कि एक f + 1 बकेट मौजूद है। एक नए इंसर्ट किए गए नोड की फ्रीक्वेंसी 1 होती है, इसलिए इंसर्शन सीधे minFrequency को 1 पर रीसेट करता है।

चरण 3: नोड्स और फ्रीक्वेंसी लिस्ट्स लागू करें

एक डबल लिंक्ड लिस्ट खाली, सिंगल-नोड और एंडपॉइंट मामलों के लिए अलग-अलग शाखाओं से बचने के लिए हेड और टेल सेंटिनल्स का उपयोग करती है। एक नोड अपनी की को संग्रहीत करता है ताकि एविक्शन बिना किसी रिवर्स सर्च के nodes से मेल खाने वाली एंट्री को हटा सके।

class Entry {
  frequency = 1
  prev: Entry | null = null
  next: Entry | null = null

  constructor(
    readonly key: number,
    public value: number,
  ) {}
}

class FrequencyList {
  private readonly head = new Entry(0, 0)
  private readonly tail = new Entry(0, 0)
  size = 0

  constructor() {
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  addFirst(node: Entry): void {
    node.prev = this.head
    node.next = this.head.next
    this.head.next!.prev = node
    this.head.next = node
    this.size += 1
  }

  remove(node: Entry): void {
    node.prev!.next = node.next
    node.next!.prev = node.prev
    node.prev = null
    node.next = null
    this.size -= 1
  }

  removeLast(): Entry {
    const node = this.tail.prev
    if (!node || node === this.head) {
      throw new Error("cannot remove from an empty frequency list")
    }
    this.remove(node)
    return node
  }
}

सेंटिनल्स कैश प्रविष्टियाँ नहीं हैं, nodes में दिखाई नहीं देते हैं, और क्षमता में नहीं गिने जाते हैं। remove केवल उस लिस्ट में वर्तमान में मौजूद एक वास्तविक नोड को स्वीकार करता है; LFUCache इनवेरिएंट्स इस पूर्व शर्त को स्थापित करते हैं।

चरण 4: प्रमोशन, रीड्स और राइट्स लागू करें

class LFUCache {
  private readonly nodes = new Map<number, Entry>()
  private readonly frequencyLists = new Map<number, FrequencyList>()
  private minFrequency = 0

  constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 0) {
      throw new RangeError("capacity must be a non-negative integer")
    }
  }

  get(key: number): number {
    const node = this.nodes.get(key)
    if (!node) return -1

    this.promote(node)
    return node.value
  }

  put(key: number, value: number): void {
    if (this.capacity === 0) return

    const existing = this.nodes.get(key)
    if (existing) {
      existing.value = value
      this.promote(existing)
      return
    }

    if (this.nodes.size === this.capacity) {
      const victimList = this.frequencyLists.get(this.minFrequency)
      if (!victimList) throw new Error("missing minimum-frequency list")

      const victim = victimList.removeLast()
      this.nodes.delete(victim.key)
      if (victimList.size === 0) {
        this.frequencyLists.delete(this.minFrequency)
      }
    }

    const node = new Entry(key, value)
    this.getOrCreateList(1).addFirst(node)
    this.nodes.set(key, node)
    this.minFrequency = 1
  }

  private promote(node: Entry): void {
    const oldFrequency = node.frequency
    const oldList = this.frequencyLists.get(oldFrequency)
    if (!oldList) throw new Error("missing source frequency list")

    oldList.remove(node)
    if (oldList.size === 0) {
      this.frequencyLists.delete(oldFrequency)
      if (this.minFrequency === oldFrequency) {
        this.minFrequency = oldFrequency + 1
      }
    }

    node.frequency = oldFrequency + 1
    this.getOrCreateList(node.frequency).addFirst(node)
  }

  private getOrCreateList(frequency: number): FrequencyList {
    let list = this.frequencyLists.get(frequency)
    if (!list) {
      list = new FrequencyList()
      this.frequencyLists.set(frequency, list)
    }
    return list
  }
}

मौजूदा-की शाखा क्षमता जांच से पहले होनी चाहिए। यह एंट्री काउंट नहीं बढ़ाती है और इसे किसी असंबंधित की को एविक्ट नहीं करना चाहिए, हालांकि यह नोड को प्रमोट करती है और नए बकेट के भीतर रीसेंसी को रीफ्रेश करती है। एक नई की के लिए, एविक्शन इंसर्शन से पहले होता है, जबकि minFrequency अभी भी विक्टिम बकेट की पहचान करता है।

चरण 5: शुद्धता और जटिलता सिद्ध करें

आरंभीकरण (initialization) के बाद सभी चार इनवेरिएंट्स बने रहते हैं। एक मिस कुछ भी नहीं बदलता है। एक सफल एक्सेस सही पुराने बकेट से एक नोड को हटाता है और उसी नोड को उसकी नई फ्रीक्वेंसी के साथ नए बकेट के सबसे हालिया छोर पर इंसर्ट करता है। सदस्यता नहीं बदलती है, बकेट असाइनमेंट और रीसेंसी बदलती है, और खाली-न्यूनतम हैंडलिंग सही न्यूनतम को बनाए रखती है।

किसी मौजूदा की को अपडेट करने से वही प्रमोशन चलाने से पहले केवल उसका मान बदलता है। यदि इंसर्शन को एक भरा हुआ कैश मिलता है, तो न्यूनतम-फ्रीक्वेंसी बकेट का बैक नोड दोनों विक्टिम नियमों को संतुष्ट करता है: इसकी फ्रीक्वेंसी सबसे कम है और यह उस फ्रीक्वेंसी में सबसे पुराना है। इसे लिस्ट और nodes से हटाने से वन-टू-वन सदस्यता इनवेरिएंट बना रहता है। नया नोड फ्रीक्वेंसी 1 के सबसे हालिया छोर में प्रवेश करता है, और minFrequency = 1 प्रत्येक इनवेरिएंट को पुनर्स्थापित करता है।

प्रत्येक मेथड मैप लुकअप, इंसर्शन या विलोपन की एक निश्चित संख्या और लिंक्ड-लिस्ट पॉइंटर परिवर्तनों की एक निश्चित संख्या निष्पादित करती है। मैप्स के लिए औसत-प्रदर्शन धारणा के तहत, get और put दोनों अपेक्षित O(1) हैं। प्रत्येक वास्तविक नोड एक की मैप और एक लिस्ट में मौजूद होता है, जबकि बकेट्स की संख्या नोड्स की संख्या से अधिक नहीं हो सकती है, इसलिए स्पेस O(capacity) है।

चरण 6: ट्रेसेस और डिफ़रेंशियल परीक्षणों से सत्यापित करें

क्षमता 2 के लिए, यह अनुक्रम चलाएँ:

put(1, 10)  -> key 1 has frequency 1
put(2, 20)  -> keys 1 and 2 tie; 2 is newer
get(1)      -> returns 10; key 1 moves to frequency 2
put(3, 30)  -> evicts key 2 at frequency 1
get(3)      -> returns 30; key 3 moves to frequency 2 and is newer than 1
put(4, 40)  -> keys 1 and 3 tie; evicts older key 1

परीक्षण सेट में 0 और 1 की क्षमताएं, मिस होने पर स्थिति अपरिवर्तित रहना, मौजूदा कीज़ के अपडेट, न्यूनतम बकेट को खाली करने वाले लगातार प्रमोशन, और समान-फ्रीक्वेंसी कीज़ के बीच बार-बार रीसेंसी परिवर्तन भी शामिल होने चाहिए। एक अधिक मजबूत जांच एक O(capacity) संदर्भ मॉडल लागू करती है जो विक्टिम के लिए स्कैन करता है, फिर एक नियतात्मक रैंडम ऑपरेशन स्ट्रीम पर प्रत्येक get परिणाम और अंतिम दृश्यमान की-वैल्यू स्थिति की तुलना करता है। यह minFrequency ड्रिफ्ट और टूटे हुए लिस्ट लिंक्स को पकड़ता है जो केवल लंबे ट्रेसेस के बाद दिखाई दे सकते हैं।

उच्च गुणवत्ता वाला नमूना उत्तर

“मैं पहले कॉन्ट्रैक्ट तय करूँगा: एक नई की की फ्रीक्वेंसी 1 होती है; सफल get और अपडेटिंग put दोनों फ्रीक्वेंसी बढ़ाते हैं; समान फ्रीक्वेंसी LRU का उपयोग करती हैं; और क्षमता 0 मान्य है। सामान्य मैप व्यवहार के तहत लक्ष्य अपेक्षित O(1) है।

मैं key -> node, frequency -> doubly linked list, और minFrequency बनाए रखूँगा। एक नोड अपनी की, मान, फ्रीक्वेंसी और लिस्ट लिंक्स को संग्रहीत करता है। एक फ्रीक्वेंसी के भीतर, अगला छोर सबसे नया और पिछला छोर सबसे पुराना होता है। हिट होने पर, मैं नोड को बकेट f से अलग करता हूँ और यदि पुराना बकेट खाली हो जाता है तो उसे हटा देता हूँ। यदि वह बकेट न्यूनतम था, तो मैं न्यूनतम को f+1 पर आगे बढ़ाता हूँ। फिर मैं नोड को बकेट f+1 के आगे इंसर्ट करता हूँ।

put के लिए, एक मौजूदा की मान बदलती है और बिना एविक्शन के प्रमोट होती है। एक भरे हुए कैश में एक नई की के लिए, मैं न्यूनतम-फ्रीक्वेंसी बकेट के पिछले नोड को हटाता हूँ और उसका की इंडेक्स हटा देता हूँ। फिर मैं नए नोड को फ्रीक्वेंसी 1 में इंसर्ट करता हूँ और न्यूनतम को 1 पर रीसेट करता हूँ। मुख्य इनवेरिएंट्स प्रति नोड एक की, प्रति नोड एक सही बकेट, प्रत्येक बकेट के भीतर रीसेंसी क्रम, और एक सटीक न्यूनतम फ्रीक्वेंसी हैं। प्रत्येक चरण हैश और पॉइंटर ऑपरेशन्स की एक निश्चित संख्या का उपयोग करता है, जिसमें स्पेस क्षमता के रैखिक (linear) होता है।

मैं क्षमता-दो टाई ट्रेस, शून्य और एक क्षमता, मौजूदा-की अपडेट, और एक खाली किए गए न्यूनतम बकेट का परीक्षण करूँगा, फिर एक स्कैनिंग मॉडल के खिलाफ नियतात्मक डिफ़रेंशियल टेस्ट चलाऊँगा। प्रोडक्शन एक्सटेंशन को फ्रीक्वेंसी एजिंग, ओवरफ्लो, समवर्तीता (concurrency), और TTL के लिए अलग कॉन्ट्रैक्ट की आवश्यकता होती है; उन्हें वर्तमान जटिलता के दावे में नहीं जोड़ा जा सकता है।”

सामान्य गलतियाँ

• केवल key -> frequency रखना → एविक्शन अभी भी सभी कीज़ को स्कैन करता है → सीधे न्यूनतम-फ्रीक्वेंसी बकेट को ट्रैक करें।
• प्रत्येक फ्रीक्वेंसी बकेट में एक अनऑर्डर्ड सेट का उपयोग करना → समान-फ्रीक्वेंसी वाली सबसे पुरानी की अज्ञात रहती है → प्रति बकेट एक डबल लिंक्ड LRU लिस्ट बनाए रखें।
• प्रमोट किए गए नोड को पीछे जोड़ना → अभी-अभी एक्सेस की गई की सबसे पुरानी बन जाती है → प्रमोट किए गए नोड्स को सबसे हालिया (front) छोर पर इंसर्ट करें।
• पुराने खाली बकेट को बनाए रखना → minFrequency बिना किसी विक्टिम वाले बकेट को इंगित कर सकता है → खाली बकेट्स को हटाएं और आवश्यकता पड़ने पर न्यूनतम को आगे बढ़ाएं।
• मौजूदा की को संभालने से पहले क्षमता की जांच करना → आकार में वृद्धि न होने के बावजूद एक अपडेट एक असंबंधित एंट्री को एविक्ट कर देता है → पहले अपडेट करें, प्रमोट करें और रिटर्न करें।
• किसी विक्टिम को केवल उसकी लिस्ट से हटाना → की मैप एक घोस्ट नोड बनाए रखता है → दोनों संरचनाओं से समान की को हटाएं।
• इंसर्शन के बाद न्यूनतम को रीसेट करने में विफल होना → बाद का एविक्शन फ्रीक्वेंसी 1 को छोड़ सकता है → प्रत्येक नई की के लिए इसे 1 पर सेट करें।
• हीप समाधान को O(1) कहना → एक्सेस द्वारा ट्रिगर किए गए प्राथमिकता परिवर्तनों के लिए हीप रिपेयर की आवश्यकता होती है → O(log capacity) स्वीकार करें या फ्रीक्वेंसी बकेट्स का उपयोग करें।
• सख्त O(1) का दावा करना → सामान्य मैप्स औसत हैश व्यवहार पर निर्भर करते हैं → अपेक्षित O(1) बताएं।
• केवल प्रकाशित उदाहरण चलाना → खाली-बकेट और टाई-ऑर्डर ड्रिफ्ट छिपे रहते हैं → इनवेरिएंट जांच और रैंडम डिफ़रेंशियल टेस्ट जोड़ें।

फॉलो-अप प्रश्न

फॉलो-अप 1: न्यूनतम बकेट खाली होने पर minFrequency बिल्कुल एक से क्यों बढ़ सकता है?

एक नोड केवल f से f + 1 पर जाता है। यदि f वर्तमान न्यूनतम है और इसका पुराना बकेट खाली हो जाता है, तो प्रत्येक अन्य नोड की फ्रीक्वेंसी पहले से ही कम से कम f + 1 है, जबकि प्रमोट किया गया नोड यह गारंटी देता है कि एक f + 1 बकेट मौजूद है। इसलिए नया न्यूनतम बिल्कुल f + 1 है; किसी ऊपर की ओर स्कैन की आवश्यकता नहीं है। यदि एविक्शन के तुरंत बाद एक नया इंसर्शन होता है, तो अंतिम न्यूनतम वैसे भी 1 पर रीसेट हो जाता है।

फॉलो-अप 2: आप TTL कैसे जोड़ेंगे?

TTL समाप्ति समय के आधार पर एक दूसरा क्रम प्रस्तुत करता है। एक हिट को समाप्ति की जांच करनी चाहिए, और क्षमता एविक्शन पहले समाप्त हो चुकी प्रविष्टियों को हटा सकता है। एक मिन-हीप समाप्ति को क्रमबद्ध कर सकता है, लेकिन अपडेट और विलोपन आमतौर पर O(log n) बन जाते हैं। एक टाइमिंग व्हील कुछ लागतों को कम करता है लेकिन सटीकता और स्थिति के ट्रेड-ऑफ जोड़ता है। परिभाषित करें कि समाप्ति या LFU में से कौन पहले जीतता है, फिर जटिलता को फिर से बताएं।

फॉलो-अप 3: क्या होता है जब फ्रीक्वेंसी लंबे समय तक बढ़ती रहती है?

काउंटर्स ओवरफ्लो हो सकते हैं, और पुरानी हॉट कीज़ अनिश्चित काल तक कैश पर कब्जा कर सकती हैं। विकल्पों में आवधिक क्षय (periodic decay), ग्लोबल न्यूनतम के एक सीमा को पार करने पर रीनॉर्मलाइजेशन, या एक अनुमानित समय-क्षयित (time-decayed) नीति शामिल है। एक पूर्ण रीनॉर्मलाइजेशन एक सामयिक O(n) कार्य बनाता है। स्थिर विलंबता (latency) के लिए वृद्धिशील प्रवास (incremental migration) या एक परिशोधित (amortized) कॉन्ट्रैक्ट की आवश्यकता होती है, जिसमें सटीक लाइफटाइम काउंट से सिमेंटिक अंतर को स्पष्ट किया गया हो।

फॉलो-अप 4: आप इसे थ्रेड-सेफ कैसे बनाएंगे?

सबसे सरल सही एक्सटेंशन प्रत्येक पूर्ण get और put के चारों ओर एक म्यूटेक्स (mutex) लगाता है, क्योंकि एक सफल रीड एक नोड, दो बकेट्स और न्यूनतम को बदल देता है। शार्पिंग (Sharding) विवाद को कम करती है लेकिन प्रत्येक शार्प को एक स्वतंत्र एविक्शन नीति देती है, जो एक सटीक वैश्विक LFU से भिन्न होती है। फाइन-ग्रेन्ड लॉकिंग को की इंडेक्स, पुराने बकेट और नए बकेट के लिए एक निश्चित क्रम परिभाषित करना चाहिए, और एविक्शन को प्रमोशन के साथ इंटरलीव होने से रोकना चाहिए।

फॉलो-अप 5: क्या LFU हमेशा LRU से बेहतर होता है?

यह एक्सेस डिस्ट्रीब्यूशन पर निर्भर करता है। LFU बार-बार एक्सेस की जाने वाली लंबी अवधि की हॉट कीज़ को संरक्षित करता है लेकिन जब ऐतिहासिक हॉट कीज़ कोल्ड हो जाती हैं तो धीरे-धीरे अनुकूलित होता है। LRU वर्किंग-सेट परिवर्तनों पर तेजी से प्रतिक्रिया करता है और इसका कार्यान्वयन छोटा होता है। प्रोडक्शन कैश अक्सर एजिंग, एडमिशन या अनुमानित नीतियों को जोड़ते हैं। इंटरव्यू कार्यान्वयन सटीक रूप से एक संयुक्त एविक्शन नियम का अभ्यास करता है; यह प्रत्येक वर्कलोड के लिए शुद्ध LFU निर्धारित नहीं करता है।

फॉलो-अप 6: मौजूदा डायनेमिक Top-K फ्रीक्वेंसी बकेट्स को बिना बदलाव के पुन: उपयोग क्यों नहीं किया जा सकता है?

डायनेमिक Top-K केवल काउंट के अनुसार परिणामों की गणना करता है और आमतौर पर समान-काउंट क्रम को अनिर्दिष्ट छोड़ सकता है। इस कैश को ठीक क्षमता पर एविक्ट करना चाहिए और इसके लिए LRU टाई-ब्रेक की आवश्यकता होती है, इसलिए प्रत्येक बकेट को एक रीसेंसी क्रम की आवश्यकता होती है और प्रत्येक अपडेट को इसे रीफ्रेश करना चाहिए। दोनों संरचनाएं फ्रीक्वेंसी बकेट्स का उपयोग करती हैं, लेकिन उनके इंटरफेस, इनवेरिएंट्स और शुद्धता के लक्ष्य भिन्न हैं।