A PayPal data engineer is building a real-time analytics dashboard to show trending search queries and their frequencies. How would you design a data structure to efficiently track and query the top-K most frequent queries from a continuous, high-volume stream?

import hashlib
import sys
import heapq

class CountMinSketch:
    def __init__(self, width, depth):
        """
        Initializes the Count-Min Sketch with specified width and depth.
        width (m): number of columns in the sketch (controls error rate).
        depth (k): number of hash functions (controls probability of error).
        """
        self.width = width
        self.depth = depth
        self.table = [[0] * width for _ in range(depth)]
        self.hash_seeds = [i for i in range(depth)] # Simple seeds for hash functions

    def _hash(self, item, seed_index):
        """
        Generates a hash for the item using a specific seed.
        In production, use a more robust hash function.
        """
        return (hash(str(item) + str(self.hash_seeds[seed_index])) % self.width)

    def add(self, item):
        """
        Adds an item to the sketch, incrementing its approximate count.
        """
        for i in range(self.depth):
            col = self._hash(item, i)
            self.table[i][col] += 1

    def estimate(self, item):
        """
        Estimates the frequency of an item.
        """
        min_count = sys.maxsize
        for i in range(self.depth):
            col = self._hash(item, i)
            min_count = min(min_count, self.table[i][col])
        return min_count

class TopKFrequentTracker:
    def __init__(self, k, cms_width=1000, cms_depth=5):
        self.k = k
        self.cms = CountMinSketch(cms_width, cms_depth)
        self.min_heap = [] # Stores (frequency, item) tuples
        self.item_frequencies = {} # To quickly check if item is in heap

    def add_item(self, item):
        self.cms.add(item)
        estimated_freq = self.cms.estimate(item)

        if item in self.item_frequencies:
            # If item is already in our heap, update its frequency
            # This is a simplification; a true heap update would involve removing and re-adding,
            # or using a more complex data structure. For interview, this approximation is often accepted.
            for i, (freq, current_item) in enumerate(self.min_heap):
                if current_item == item:
                    self.min_heap[i] = (estimated_freq, item)
                    heapq.heapify(self.min_heap) # Re-heapify after update
                    self.item_frequencies[item] = estimated_freq
                    return

        if len(self.min_heap) < self.k:
            heapq.heappush(self.min_heap, (estimated_freq, item))
            self.item_frequencies[item] = estimated_freq
        elif estimated_freq > self.min_heap[0][0]:
            # If current item is more frequent than the smallest in heap
            smallest_freq, smallest_item = heapq.heappop(self.min_heap)
            del self.item_frequencies[smallest_item]
            
            heapq.heappush(self.min_heap, (estimated_freq, item))
            self.item_frequencies[item] = estimated_freq

    def get_top_k(self):
        # Returns top K items sorted by frequency (highest first)
        return sorted(self.min_heap, key=lambda x: x[0], reverse=True)

# Example usage:
tracker = TopKFrequentTracker(k=3)
search_queries = ["laptop", "mouse", "keyboard", "laptop", "monitor", "mouse", "laptop", "keyboard", "laptop", "headphones", "mouse", "laptop"]

print("--- Processing queries ---")
for query in search_queries:
    tracker.add_item(query)
    print(f"Added: '{query}'. Current Top {tracker.k}: {tracker.get_top_k()}")

print("n--- Final Top K queries ---")
print(tracker.get_top_k())

# Expected actual frequencies: laptop: 5, mouse: 3, keyboard: 2, monitor: 1, headphones: 1