How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Amazon during technical interviews.

Design LFU cache with distributed extension

Quick Overview

This question evaluates understanding of cache design and frequency-based eviction policies, efficient data structures that support O(1) operations, and techniques for approximate frequency estimation and summarization in distributed streaming environments.

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

### 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.

Quick Answer: This question evaluates understanding of cache design and frequency-based eviction policies, efficient data structures that support O(1) operations, and techniques for approximate frequency estimation and summarization in distributed streaming environments.

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

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]])

Expected 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.

Input: (0, [["put", 0, 0], ["get", 0]])

Expected Output: [None, -1]

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

Hints

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).
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.
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.
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).