डायनामिक टॉप-K फ़्रीक्वेंट आइटम्स के लिए डेटा स्ट्रक्चर डिज़ाइन करना

प्रश्न और इसका उपयोग कब करें

पूर्णांक IDs की एक कभी न खत्म होने वाली स्ट्रीम एक समय में एक आइटम के रूप में आती है। add(x), ID x की एक और उपस्थिति (occurrence) को रिकॉर्ड करता है। topK(k) उच्चतम वर्तमान फ़्रीक्वेंसी वाले अधिकतम k भिन्न (distinct) IDs और उनकी गणना (counts) लौटाता है; बराबर (tied) IDs किसी भी क्रम में दिखाई दे सकते हैं, और k क्वेरीज़ के बीच बदल सकता है। रीड-हैवी और राइट-हैवी वर्कलोड के लिए सटीक समाधान डिज़ाइन करें और उनकी टाइम और स्पेस लागतों का विश्लेषण करें। यदि मेमोरी सीमित होने पर भिन्न IDs की संख्या असीमित रूप से बढ़ सकती है, तो एक अनुमानित (approximate) डिज़ाइन प्रदान करें और परिभाषित करें कि इसकी त्रुटि (error) का क्या अर्थ है।

यह प्रश्न सॉफ्टवेयर इंजीनियरिंग और एल्गोरिदम इंटरव्यू के लिए उपयुक्त है। सटीक अनुबंध (contract) केवल फ़्रीक्वेंसी वृद्धि (increments) की अनुमति देता है: कोई डिलीशन, स्लाइडिंग विंडो या डिस्ट्रीब्यूटेड मर्ज नहीं। मान लें कि N अब तक के अपडेट्स की संख्या है और D भिन्न IDs की संख्या है, जिसमें सामान्य मामले में k << D है। इस प्रॉम्प्ट के सार्वजनिक संस्करण स्पष्ट रूप से वर्कलोड-आधारित डिज़ाइन और सीमित-मेमोरी स्ट्रीमिंग एक्सटेंशन की मांग करते हैं, इसलिए “हैश मैप प्लस मिन-हीप” उत्तर की केवल शुरुआत है।

इंटरव्यूअर क्या मूल्यांकन कर रहा है

पहला, क्या उम्मीदवार ऑपरेशन अनुबंध और वर्कलोड अनुपात स्थापित करता है? स्ट्रीम समाप्त होने के बाद केवल एक बार पूछने वाले बैच को हर अपडेट के बाद पूछे जाने वाले ऑनलाइन लीडरबोर्ड जितनी रखरखाव लागत नहीं चुकानी चाहिए।

दूसरा, क्या बताई गई जटिलताएँ मेंटेन की गई स्थिति (state) से मेल खाती हैं? हैश मैप में काउंट करना और क्वेरी के समय आकार-k का मिन-हीप बनाना, add के लिए अपेक्षित O(1) और topK के लिए O(D log k) देता है। प्रति अपडेट O(log k) हीप मेंटेनेंस का दावा करने के लिए हीप-पोजीशन ट्रैकिंग और इस बात की व्याख्या की भी आवश्यकता होती है कि हीप के बाहर का आइटम इसमें कब प्रवेश करता है।

तीसरा, क्या उम्मीदवार एक डायनामिक स्ट्रक्चर को सही साबित कर सकता है? एक मजबूत उत्तर तीन इनवेरिएंट्स बताता है: प्रत्येक ID ठीक एक फ़्रीक्वेंसी बकेट से संबंधित है; बकेट फ़्रीक्वेंसी सख्ती से बढ़ती हुई (strictly increasing) हैं और कोई भी बकेट खाली नहीं है; और किसी ID की बकेट फ़्रीक्वेंसी उसकी वास्तविक संचित गणना (accumulated count) के बराबर है। जटिलता का तर्क इन्हीं इनवेरिएंट्स से निकलना चाहिए।

चौथा, क्या उम्मीदवार सटीक टॉप-k, हैवी हिटर्स (heavy hitters) और फ़्रीक्वेंसी अनुमान के बीच अंतर कर सकता है? Space-Saving एक निश्चित काउंटर बजट के तहत काउंट सीमाओं के साथ उम्मीदवार कुंजियों (candidate keys) को बनाए रखता है। Count-Min Sketch मुख्य रूप से दी गई कुंजी की फ़्रीक्वेंसी का अनुमान लगाता है और स्वयं IDs के एन्युमरेबल सेट को बनाए नहीं रखता है। अकेले स्केच को टॉप-k सूची के रूप में मानने से उम्मीदवार खोज (candidate discovery) अस्पष्ट रह जाती है।

उत्तर देने से पहले स्पष्ट करने योग्य प्रश्न

• क्या k निश्चित है या क्वेरी-विशिष्ट? एक निश्चित K एक इंडेक्स किए गए आकार-K हीप की अनुमति देता है। एक आर्बिट्रेरी k सभी फ़्रीक्वेंसी में व्यवस्थित स्ट्रक्चर के पक्ष में है।
• अपडेट-टू-क्वेरी अनुपात क्या है? एक राइट-हैवी सिस्टम क्वेरी समय तक काम को टाल सकता है। बार-बार होने वाली क्वेरीज़ हर add पर क्रम बनाए रखने को उचित ठहराती हैं।
• क्या बराबरी (ties) का कोई डिटर्मिनिस्टिक क्रम होना चाहिए? यह अनुबंध किसी भी क्रम की अनुमति देता है, इसलिए प्रत्येक बकेट के अंदर एक हैश सेट पर्याप्त है। आरोही (ascending) IDs की आवश्यकता के लिए एक ऑर्डर्ड सेट की आवश्यकता होती है और यह अपेक्षित O(1) अपडेट को हटा देता है।
• क्या डिलीशन या टाइम विंडो की आवश्यकता है? केवल वृद्धि के साथ, एक आइटम फ़्रीक्वेंसी f से आसन्न फ़्रीक्वेंसी f + 1 पर चला जाता है। डिलीशन विपरीत गति जोड़ता है; एक विंडो को समाप्ति स्थिति (expiration state) की भी आवश्यकता होती है।
• क्या D मेमोरी में फिट बैठता है? एक अप्रतिबंधित वितरण के लिए सटीक उत्तर हर भिन्न ID की गणना को बनाए रखता है। निश्चित मेमोरी के लिए अनुमान (approximation) या दोबारा चलाने योग्य (replayable) दूसरे पास की आवश्यकता होती है।
• क्या त्रुटि स्वीकार्य है? “लगभग सही” परीक्षण योग्य नहीं है। योगात्मक काउंट त्रुटि (additive count error), एक अनिश्चित उम्मीदवार सेट, या टॉप-k को प्रमाणित करने वाली फ़्रीक्वेंसी-पृथक्करण स्थिति निर्दिष्ट करें।
• क्या काउंटर्स ओवरफ्लो हो सकते हैं? एक लंबे समय तक चलने वाली सेवा को 64-बिट या व्यापक काउंटर्स की आवश्यकता होती है। उदाहरण में JavaScript number का उपयोग किया गया है और यह केवल सुरक्षित-पूर्णांक (safe-integer) सीमा के भीतर सटीक है।

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

“मैं पहले स्पष्ट करूँगा कि क्या k बदलता है, रीड-राइट अनुपात, टाई ऑर्डरिंग और मेमोरी सीमा क्या है। राइट-हैवी और कम-क्वेरी वाले ट्रैफ़िक के लिए, मैं अपेक्षित O(1) ऐड्स के लिए हैश मैप का उपयोग करूँगा, फिर प्रति क्वेरी O(D log k) में आकार-k के मिन-हीप में D काउंट्स को स्कैन करूँगा। यदि आर्बिट्रेरी-k क्वेरीज़ बार-बार होती हैं, तो मैं फ़्रीक्वेंसी बकेट्स की एक बढ़ती हुई डबली लिंक्ड लिस्ट और एक ID → bucket मैप बनाए रखूँगा। एक अपडेट एक ID को केवल बकेट f से आसन्न बकेट f + 1 में ले जाता है, जिससे अपेक्षित O(1) अपडेट मिलते हैं; k परिणामों के लिए पीछे की ओर चलने की लागत O(min(k, D)) है, जिसमें O(D) स्पेस लगता है। यदि D मेमोरी में फिट नहीं हो सकता है, तो मैं एरर बाउंड्स के साथ निश्चित Space-Saving काउंटर्स का उपयोग करूँगा और केवल तभी प्रमाणित टॉप-k का दावा करूँगा जब बाउंड्स अलग हो जाएँ। Count-Min Sketch को अभी भी IDs को एन्युमरेट करने के लिए एक कैंडिडेट सेट की आवश्यकता होती है।”

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

चरण 1: वर्कलोड के अनुसार सटीक डिज़ाइनों की तुलना करें

“हैश मैप प्लस मिन-हीप” हमेशा सबसे बेहतर विकल्प नहीं होता है। यह जानबूझकर ऑर्डरिंग के काम को क्वेरी पाथ पर डालता है, जो तब उपयुक्त होता है जब राइट्स की संख्या अधिक हो। यदि उत्पाद हर add के बाद एक लीडरबोर्ड दिखाता है, तो बार-बार D कुंजियों को स्कैन करना बाधा (bottleneck) बन जाता है और अधिक जटिल फ़्रीक्वेंसी-बकेट स्ट्रक्चर अपनी उपयोगिता साबित करता है।

चरण 2: फ़्रीक्वेंसी-बकेट इनवेरिएंट्स स्थापित करें

बढ़ते हुए फ़्रीक्वेंसी क्रम में बकेट्स की एक डबली लिंक्ड लिस्ट रखें। प्रत्येक बकेट के पास उस फ़्रीक्वेंसी वाले IDs का एक सेट होता है, जबकि एक हैश मैप किसी ID के बकेट को सीधे खोजता है। एक नया ID फ़्रीक्वेंसी-1 बकेट में शामिल होता है। एक मौजूदा ID बकेट f से बकेट f + 1 में चला जाता है। चूंकि एक अपडेट ठीक एक से बढ़ता है, एक नया बकेट केवल स्रोत और उसके उत्तराधिकारी के बीच ही डाला जा सकता है; किसी सूची खोज की आवश्यकता नहीं है। स्रोत बकेट के खाली होते ही उसे हटा दें।

तीन इनवेरिएंट्स परिणाम को सही साबित करते हैं:

1. locations में प्रत्येक ID ठीक एक बकेट सेट में दिखाई देता है।
2. प्रत्येक गैर-रिक्त बकेट का frequency उसमें मौजूद प्रत्येक ID की वास्तविक गणना के बराबर होता है।
3. फ़्रीक्वेंसी head से tail तक सख्ती से बढ़ती हैं।

इसलिए, tail से पीछे की ओर चलने पर कोई भी उच्च-फ़्रीक्वेंसी ID पीछे नहीं छूट सकता, जबकि बराबरी वाले किसी भी क्रम में लौटाए जा सकते हैं। प्रत्येक विज़िट किया गया बकेट कम से कम एक परिणाम देता है, इसलिए विज़िट किए गए बकेट्स की संख्या आउटपुट आकार से अधिक नहीं होती है और क्वेरी का समय O(min(k, D)) होता है।

चरण 3: सटीक आर्बिट्रेरी-k क्वेरीज़ लागू करें

interface Bucket {
  frequency: number;
  values: Set<number>;
  prev: Bucket | null;
  next: Bucket | null;
}

interface TopKEntry {
  value: number;
  count: number;
}

class FrequencyIndex {
  private readonly locations = new Map<number, Bucket>();
  private head: Bucket | null = null;
  private tail: Bucket | null = null;

  add(value: number): void {
    const source = this.locations.get(value);

    if (!source) {
      let target = this.head;
      if (!target || target.frequency !== 1) {
        target = this.insertBefore(this.head, 1);
      }
      target.values.add(value);
      this.locations.set(value, target);
      return;
    }

    let target = source.next;
    if (!target || target.frequency !== source.frequency + 1) {
      target = this.insertAfter(source, source.frequency + 1);
    }

    source.values.delete(value);
    target.values.add(value);
    this.locations.set(value, target);

    if (source.values.size === 0) {
      this.removeBucket(source);
    }
  }

  topK(k: number): TopKEntry[] {
    if (!Number.isInteger(k) || k < 0) {
      throw new RangeError("k must be a non-negative integer");
    }

    const result: TopKEntry[] = [];
    let bucket = this.tail;

    while (bucket && result.length < k) {
      for (const value of bucket.values) {
        result.push({ value, count: bucket.frequency });
        if (result.length === k) break;
      }
      bucket = bucket.prev;
    }

    return result;
  }

  private insertBefore(next: Bucket | null, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev: next?.prev ?? null,
      next,
    };

    if (bucket.prev) bucket.prev.next = bucket;
    else this.head = bucket;

    if (next) next.prev = bucket;
    else this.tail = bucket;

    return bucket;
  }

  private insertAfter(prev: Bucket, frequency: number): Bucket {
    const bucket: Bucket = {
      frequency,
      values: new Set<number>(),
      prev,
      next: prev.next,
    };

    if (prev.next) prev.next.prev = bucket;
    else this.tail = bucket;

    prev.next = bucket;
    return bucket;
  }

  private removeBucket(bucket: Bucket): void {
    if (bucket.prev) bucket.prev.next = bucket.next;
    else this.head = bucket.next;

    if (bucket.next) bucket.next.prev = bucket.prev;
    else this.tail = bucket.prev;
  }
}

यह जटिलता Map और Set के लिए सामान्य अपेक्षित निरंतर-समय (constant-time) मान्यताओं का उपयोग करती है, न कि सख्त वर्स्ट-केस O(1) की JavaScript विनिर्देश गारंटी। topK(0) एक खाली ऐरे लौटाता है, k > D सभी IDs लौटाता है, और एक नकारात्मक या गैर-पूर्णांक k त्रुटि फेंकता है।

चरण 4: सीमित मेमोरी के तहत अनुमान गारंटी बताएं

सटीक हैश मैप D के साथ बढ़ता है। Space-Saving इसके बजाय केवल m काउंटर्स रखता है जिसमें एक ID, एक अनुमानित गणना और एक अधिकतम त्रुटि होती है; सीमा उम्मीदवार k + 1 के साथ तुलना करने के लिए m > k की आवश्यकता होती है। देखा गया ट्रैक किया गया ID अपने काउंटर को बढ़ाता है। जब सभी काउंटर्स भर जाने के बाद एक अनट्रैक किया गया ID आता है, तो यह न्यूनतम अनुमानित गणना c_min वाले ID को बदल देता है; नया अनुमान दर्ज की गई त्रुटि c_min के साथ c_min + 1 बन जाता है।

प्रत्येक मॉनिटर किए गए ID के लिए, वास्तविक फ़्रीक्वेंसी [estimate - error, estimate] में होती है, और रिसर्च पेपर अधिकतम ओवरएस्टिमेशन को N / m तक सीमित करता है। टॉप-k सेट को तब प्रमाणित किया जा सकता है जब पहले k उम्मीदवारों के बीच सबसे निचली निचली सीमा (smallest lower bound) उम्मीदवार k + 1 की अनुमानित ऊपरी सीमा से कम न हो। यदि वे अंतराल ओवरलैप होते हैं, तो अनुमानित क्रम को सटीक के रूप में प्रस्तुत करने के बजाय अनुमानित उम्मीदवार लौटाएं। जब पूरी स्ट्रीम में D <= m होता है, तो कोई प्रतिस्थापन नहीं होता है और काउंट्स सटीक रहते हैं।

Count-Min Sketch एक निश्चित width × depth काउंटर ऐरे का उपयोग करता है। केवल-वृद्धि वाली स्ट्रीम पर width = ceil(e / ε) और depth = ceil(ln(1 / δ)) के साथ, आपूर्ति की गई ID का अनुमान कभी भी उसकी वास्तविक गणना से कम नहीं होता है और, कम से कम 1 - δ की संभावना के साथ, true count + εN से अधिक नहीं होता है। स्केच IDs को बनाए नहीं रखता है, इसलिए इसे अभी भी एक कैंडिडेट हीप, कैंडिडेट सेट, या एन्युमरेबल डोमेन की आवश्यकता होती है। केवल एक स्केच यह उत्तर नहीं दे सकता कि “कौन से IDs टॉप-k हैं?”

चरण 5: केवल एक उदाहरण से नहीं, बल्कि ऑरेकल के विरुद्ध सत्यापित करें

[1, 2, 1, 3, 2, 1] से शुरू करें और सत्यापित करें कि topK(2) 3 और 2 फ़्रीक्वेंसी वाले दो IDs लौटाता है। फिर एक खाली स्ट्रक्चर, k = 0, k > D, सभी टाइज़, एक हॉट आइटम के साथ कई सिंगलटन, और कई बकेट्स के माध्यम से आगे बढ़ने वाले एक ID को कवर करें।

अंत में, एक रैंडम अपडेट स्ट्रीम उत्पन्न करें और ऑरेकल के रूप में बुनियादी हैश काउंट्स और पूर्ण सॉर्टिंग का उपयोग करें। अंतरालों पर, सत्यापित करें कि परिणाम की लंबाई min(k, D) है, IDs अद्वितीय हैं, प्रत्येक रिपोर्ट की गई गणना सटीक है, और किसी भी बाहर रखे गए ID की गणना सबसे छोटी चयनित गणना से अधिक नहीं है। उपरोक्त कार्यान्वयन ने 10,000 नियतात्मक (deterministic) रैंडम अपडेट और कई k मानों पर इस डिफरेंशियल चेक को पास किया।

एक मजबूत उत्तर का उदाहरण

“मैं सटीक अनुबंध को केवल-वृद्धि अपडेट, क्वेरी-विशिष्ट k, और मनमाने टाई क्रम तक सीमित रखूँगा। कई राइट्स और दुर्लभ क्वेरीज़ के लिए, मैं अपेक्षित O(1) ऐड्स के लिए केवल एक ID → count हैश मैप बनाए रखूँगा। एक क्वेरी आकार-k के मिन-हीप के माध्यम से D IDs को स्कैन करती है, जिसमें O(D log k) समय और O(k) अतिरिक्त स्पेस की लागत आती है।

बार-बार होने वाली लीडरबोर्ड क्वेरीज़ के लिए, मैं डबली लिंक्ड फ़्रीक्वेंसी बकेट्स का उपयोग करूँगा। बकेट्स को कम से उच्च फ़्रीक्वेंसी के क्रम में व्यवस्थित किया जाता है और उनमें उस फ़्रीक्वेंसी पर टाई वाले IDs होते हैं; एक हैश मैप प्रत्येक ID के बकेट का पता लगाता है। एक add एक ID को केवल f से f + 1 में ले जाता है, इसलिए यह एक आसन्न बकेट की जांच करता है और खाली स्रोत बकेट को हटा देता है। अपडेट्स अपेक्षित रूप से O(1) होते हैं, टेल से पीछे की ओर चलने पर परिणाम O(min(k, D)) में मिलते हैं, और कुल स्पेस O(D) है। शुद्धता अद्वितीय बकेट सदस्यता, सटीक बकेट गणना और सख्ती से बढ़ते बकेट क्रम से प्राप्त होती है।

यदि D मेमोरी में फिट नहीं होता है, तो सटीक अनुबंध बदलना होगा। मैं उम्मीदवार त्रुटि अंतरालों के साथ m Space-Saving काउंटर्स बनाए रखूँगा; अधिकतम ओवरएस्टिमेशन N / m से घिरा है, और मैं सेट को केवल तभी प्रमाणित करूँगा जब पहले k निचली सीमाएं बाद की ऊपरी सीमाओं से अलग हो जाएं। Count-Min Sketch दी गई ID का अनुमान लगा सकता है लेकिन फिर भी उसे उम्मीदवार खोज की आवश्यकता होती है। रिलीज़ से पहले, मैं पूर्ण सॉर्टिंग के विरुद्ध रैंडमाइज्ड डिफरेंशियल टेस्ट चलाऊँगा और स्पष्ट रूप से टाइज़, अमान्य k, और काउंटर-ओवरफ्लो सीमाओं का परीक्षण करूँगा।”

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

• वर्कलोड के बारे में पूछे बिना मिन-हीप चुनना → बार-बार होने वाली क्वेरीज़ सभी D IDs को स्कैन करती हैं, जबकि दुर्लभ क्वेरीज़ निरंतर रखरखाव को उचित नहीं ठहरा सकती हैं → वास्तविक अनुपात के अनुसार अपडेट या क्वेरी पाथ पर लागत डालें।
• k बदलने पर एक निश्चित K बनाए रखना → मेंटेन किए गए K से बड़ी क्वेरी के पास कोई पूरा कैंडिडेट सेट नहीं होता है → k को स्पष्ट रूप से बाउंड करें या फ़्रीक्वेंसी बकेट्स या एक ऑर्डर्ड स्ट्रक्चर का उपयोग करें जो आर्बिट्रेरी k का समर्थन करता है।
• हीप कुंजी को उसी स्थान पर बदलना (Mutating in place) → एक सामान्य हीप को किसी आइटम की स्थिति का पता नहीं होता है, इसलिए इसका क्रम टूट जाता है या पुराने रिकॉर्ड जमा हो जाते हैं → ID → heap index बनाए रखें, या बताई गई जटिलता के साथ पुरानी कुंजी को हटाएं और फिर से डालें।
• खाली फ़्रीक्वेंसी बकेट्स को लिंक्ड छोड़ना → एक क्वेरी फ़्रीक्वेंसी 1 से अधिकतम काउंट तक के अंतरालों को पार कर सकती है → किसी बकेट के अंतिम ID के स्थानांतरित होने के तुरंत बाद उसे अनलिंक करें।
• सख्त O(1) हैशिंग का दावा करना → Map और Set सामान्य अपेक्षित-जटिलता विश्लेषण का समर्थन करते हैं, न कि सख्त भाषा गारंटी का → हैश धारणा बताएं; एक बैलेंस्ड ट्री का उपयोग करें और वर्स्ट-केस सीमाएं महत्वपूर्ण होने पर O(log D) स्वीकार करें।
• Count-Min Sketch से सीधे टॉप-k लौटाना → स्केच आपूर्ति की गई कुंजी की क्वेरीज़ का उत्तर देता है और अज्ञात IDs को एन्युमरेट नहीं कर सकता है → कैंडिडेट खोज को अलग से बनाए रखें या Space-Saving का उपयोग करें, जो कैंडिडेट कुंजियों को बनाए रखता है।
• त्रुटि के बिना अनुमान की रिपोर्ट करना → इंटरव्यूअर यह नहीं बता सकता कि क्या रैंक k और k + 1 में अंतर किया जा सकता है → अनुमान, निचली और ऊपरी सीमाएं लौटाएं, और बताएं कि क्या सेट प्रमाणित है।
• केवल नमूने का परीक्षण करना → टूटे हुए लिंक्स, खाली बकेट्स और टाई की सीमाएं अक्सर लंबे अपडेट अनुक्रमों के बाद ही दिखाई देती हैं → पूर्ण-सॉर्ट ऑरेकल के विरुद्ध डिफरेंशियल-परीक्षण करें और इनवेरिएंट्स को सत्यापित करें।

फॉलो-अप प्रश्न और उत्तर

फॉलो-अप 1: यदि topK हमेशा K = 100 का उपयोग करता है, तो क्या आपको अभी भी फ़्रीक्वेंसी बकेट्स की आवश्यकता है?

ज़रूरी नहीं। एक काउंट मैप, आकार-100 का मिन-हीप, और ID → heap index O(log 100) में प्रत्येक अपडेट के बाद हीप सदस्य को समायोजित कर सकते हैं या न्यूनतम के विरुद्ध तुलना कर सकते हैं। यह कोड और मेमोरी लेआउट में सरल हो सकता है, लेकिन यह topK(1000) का उत्तर नहीं दे सकता है। फ़्रीक्वेंसी बकेट्स अपनी जटिलता को तब सार्थक बनाते हैं जब k आर्बिट्रेरी हो और अपेक्षित निरंतर-समय अपडेट महत्वपूर्ण हों।

फॉलो-अप 2: यदि बराबर IDs का आरोही होना आवश्यक हो तो क्या बदलता है?

प्रत्येक बकेट के Set को एक ऑर्डर्ड सेट से बदलें, या केवल उस बाउंड्री बकेट को सॉर्ट करें जो क्वेरी द्वारा आंशिक रूप से उपयोग की जाती है। पहला विकल्प s आकार के बकेट के लिए प्रत्येक गतिविधि में O(log s) जोड़ता है; दूसरा केवल क्वेरी समय पर बाउंड्री-सॉर्ट लागत वहन करता है। इस आधार पर चुनें कि कितनी बार डिटर्मिनिस्टिक क्रम की आवश्यकता होती है।

फॉलो-अप 3: आप remove(x) कैसे जोड़ेंगे?

पूर्ववर्ती बकेट की सममित रूप से जांच करके किसी ID को फ़्रीक्वेंसी f से f - 1 पर ले जाएं, शून्य पर पहुंचने पर ID को locations से हटा दें। परिभाषित करें कि किसी अनुपलब्ध ID को हटाने पर त्रुटि आती है या उसे अनदेखा किया जाता है। समवर्ती (concurrent) ऐड और रिमूव के साथ, खाली बकेट को खोजने, स्थानांतरित करने और अनलिंक करने के लिए एक ही एटॉमिक क्रिटिकल सेक्शन साझा करना होगा, अन्यथा वही ID दो बकेट्स में दिखाई दे सकती है।

फॉलो-अप 4: क्या होगा यदि क्वेरी केवल पिछले 10 मिनट के लिए मांगती है?

फ़्रीक्वेंसी अब मोनोटोनिक नहीं रहती हैं। बकेट इंडेक्स को टाइमस्टैम्प किए गए इवेंट्स या टाइम-बकेटेड काउंट्स की भी आवश्यकता होती है ताकि समाप्ति रिवर्स अपडेट जारी कर सके। प्रति-इवेंट कतार सटीक है लेकिन विंडो में इवेंट्स के अनुपात में स्थान का उपयोग करती है। टाइम बकेट्स एक स्पष्ट बाउंड्री एरर पेश करते हुए स्थिति को कम करते हैं। एक सर्व-इतिहास (all-history) Space-Saving सारांश मनमाने समाप्त हो चुके इवेंट्स को सीधे घटा नहीं सकता है।

फॉलो-अप 5: क्या होगा यदि रैंक k और k + 1 के लिए Space-Saving अंतराल ओवरलैप होते हैं?

काउंटर बजट m बढ़ाएं, रिपोर्ट करें कि कैंडिडेट सेट अभी प्रमाणित नहीं है, या कैंडिडेट सेट को सटीक रूप से गिनने के लिए डेटा को फिर से चलाएं (replay)। दूसरा पास केवल बनाए रखे गए उम्मीदवारों को सही करता है। यदि सारांश इतना छोटा था कि यह गारंटी नहीं दी जा सकती कि वास्तविक टॉप-k उस सेट में प्रवेश कर गया है, तो रीप्ले से पहले कैंडिडेट सेट को बड़ा करें।

फॉलो-अप 6: आप शार्ड्स (shards) में ग्लोबल टॉप-k कैसे प्राप्त करते हैं?

स्थानीय टॉप-k सूचियाँ किसी भी वितरण के लिए सटीक ग्लोबल टॉप-k उत्पन्न नहीं कर सकती हैं। प्रत्येक शार्ड पर कटऑफ के ठीक नीचे मौजूद एक ID एकत्रीकरण (aggregation) के बाद विश्व स्तर पर रैंक कर सकती है। एक सटीक डिज़ाइन को सभी प्रासंगिक काउंट्स को एकत्रित करना चाहिए या कैंडिडेट सीमाओं को बनाए रखना चाहिए जो कवरेज साबित करती हैं। एक अनुमानित डिज़ाइन मर्ज करने योग्य सारांशों को मर्ज कर सकता है, लेकिन इसके अनुबंध में अतिरिक्त त्रुटि और रिपोर्टिंग विलंब शामिल होना चाहिए।