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.

Design LFU Cache

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

• LFUCache(int capacity) — initialize the object with the maximum capacity of the cache.
• int get(int key) — return the value of key if it exists in the cache, otherwise return -1. Accessing a key increases its usage frequency.
• void put(int key, int value) — update the value of key if present, otherwise insert it. When the cache reaches capacity and a new key is inserted, evict the least frequently used key. If multiple keys share the lowest frequency, evict the least recently used among them.

Both get and put must run in O(1) average time.

Harness encoding. To make this runnable, your function is called as lfuCache(capacity, operations):

• capacity is the cache capacity (an integer, >= 0).
• operations is a list of operations. Each is either ["put", key, value] or ["get", key].
• Return a list with one entry per operation, in order: None for each put, and the returned value (the value, or -1) for each get.

For example, with capacity = 2 and ops [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]], after inserting keys 1 and 2 and accessing key 1 (raising its frequency), inserting key 3 evicts key 2 (lowest frequency), so get(2) returns -1. The result is [None, None, 1, None, -1].

---

Follow-up (system design discussion — not graded by the console): Extend the LFU idea to a high-volume, distributed data stream where exact counts cannot fit on one machine. Consider per-node approximate-counting summaries (e.g. Count-Min Sketch + a bounded top-K heap, or the Space-Saving / Misra–Gries algorithm), periodic mergeable summaries to compute a global top-K, handling late/out-of-order events, sliding windows with time-decay, and the accuracy/memory/latency trade-offs involved.

Constraints

• 0 <= capacity
• Keys and values fit in 32-bit signed integers.
• Each operation is either ["put", key, value] or ["get", key].
• On eviction, remove the least frequently used key; break ties by least recently used.
• If capacity == 0, every put is a no-op and every get returns -1.

Examples

Example 1

Input: (2, [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2], ["get", 3], ["put", 4, 4], ["get", 1], ["get", 3], ["get", 4]])
Output: [None, None, 1, None, -1, 3, None, -1, 3, 4]

Explanation: Classic LeetCode trace. After get(1), key 1 has freq 2 and key 2 has freq 1, so put(3) evicts key 2. Later both keys 1 and 3 have freq 2; key 1 was accessed less recently, so put(4) evicts key 1.

Example 2

Input: (0, [["put", 0, 0], ["get", 0]])
Output: [None, -1]

Explanation: Zero capacity: the put stores nothing and the get returns -1.

Hints

1. Maintain three maps: key -> value, key -> frequency, and frequency -> ordered collection of keys at that frequency (insertion-ordered so the front is the least recently used).
2. Track a running min_freq. When you bump a key's frequency, remove it from its old frequency bucket; if that bucket was the min_freq bucket and becomes empty, increment min_freq.
3. On insertion into a full cache, evict the front (oldest) key of the min_freq bucket, then set min_freq back to 1 for the newly inserted key.
4. An OrderedDict (or a doubly-linked list per frequency) gives O(1) insertion, removal, and oldest-key eviction, which is what keeps both operations O(1).