Design LFU cache with distributed extension

### Problem You are asked to design and implement a data structure that behaves like an in-memory cache with a **Least Frequently Used (LFU)** eviction policy. Then, you will discuss how to extend the idea to a distributed, streaming setting. #### Part A: Single-node LFU cache Design a class `LFUCache` with the following API: - Constructor: `LFUCache(int capacity)` - `capacity` is a positive integer indicating the maximum number of key–value pairs the cache can hold. - Method: `int get(int key)` - If the key exists in the cache, return its value and update its usage frequency. - If the key does not exist, return `-1`. - Method: `void put(int key, int value)` - Insert or update the value of the key. - If inserting a new key would exceed `capacity`, you must evict **one** key according to the LFU policy. Eviction rules: 1. Evict the key with the **lowest access frequency**. 2. If multiple keys share the same (lowest) frequency, evict the one that is **least recently used** among them. **Requirements:** - Aim for **O(1)** amortized time for both `get` and `put` operations. - Clearly describe the data structures you choose and how they support: - Updating a key’s frequency on `get` and `put`. - Finding and evicting the correct key in O(1). You may assume: - `capacity >= 0`. - Keys and values are integers that fit in standard 32-bit types. #### Part B: Distributed / streaming extension Now assume that instead of a single process, you are dealing with a **high-volume data stream** of keys (e.g., user IDs, item IDs, or search queries) spread across multiple machines. The input rate is too high to store all keys and their counts exactly on a single node. You want to extend the LFU idea so that you can: - Continuously ingest a (potentially unbounded) stream of keys across **many machines**. - Approximate the set of **most frequently used keys** (LFU-like behavior) over a recent time window or over all time. - Support queries such as: "What are the current top *K* most frequent keys?" with reasonable accuracy. **Questions for the distributed extension:** 1. What data structures or algorithms would you use on each machine to track local frequencies under memory constraints (e.g., sketches, approximate counting, bounded-size summaries)? 2. How would you periodically **merge** local summaries to obtain a global view of the most frequent keys? 3. How would you handle: - Late or out-of-order events in the stream? - Sliding windows or time-based decay (so that recent events matter more)? 4. What trade-offs do you make between **accuracy**, **memory usage**, and **latency**, and why? You do **not** need to draw full system architecture diagrams, but your answer should make it clear how the LFU concept is adapted to a distributed, streaming environment.