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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bytedance during technical interviews.

Least Frequently Used (LFU) Cache | Bytedance Coding Question

Quick Overview

This question tests practical data structure design by requiring an O(1) implementation of a Least Frequently Used cache with tie-breaking by recency. It evaluates a software engineer's ability to combine hash maps and ordered collections to enforce eviction policies, a skill commonly assessed in system design and algorithm interviews.

Least Frequently Used (LFU) Cache

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Least Frequently Used (LFU) Cache Design and implement a data structure for a **Least Frequently Used (LFU) cache** that supports `get` and `put` operations in **O(1)** average time complexity. The cache is initialized with a fixed positive integer `capacity`. It must support the following two operations: - `get(key)` — Return the value associated with `key` if it exists in the cache. Otherwise, return `-1`. A successful `get` counts as a use of `key` (its use frequency increases by one). - `put(key, value)` — Update the value of `key` if it already exists. Otherwise, insert the `key`-`value` pair into the cache. A `put` (insert or update) also counts as a use of `key`. When the cache reaches `capacity` and a new key must be inserted, **evict the key with the smallest use frequency** before inserting the new key. If there is a tie — multiple keys share the same lowest use frequency — evict the **least recently used** among them (the one whose most recent `get`/`put` happened longest ago). A newly inserted key starts with a use frequency of `1` (the inserting `put` is its first use). ### Constraints & Assumptions - `1 <= capacity <= 10^4` - `0 <= key <= 10^5` - `0 <= value <= 10^9` - At most `2 * 10^5` calls in total will be made to `get` and `put`. - `get` and `put` must each run in **O(1)** average time. - All keys are non-negative integers; values fit in a 64-bit signed integer. ### Example Given `capacity = 2` and the following call sequence: | Operation | Returns | Cache state after (key: value, freq) | |----------------|---------|---------------------------------------------| | `put(1, 10)` | — | `{1: 10 (f=1)}` | | `put(2, 20)` | — | `{1: 10 (f=1), 2: 20 (f=1)}` | | `get(1)` | `10` | `{1: 10 (f=2), 2: 20 (f=1)}` | | `put(3, 30)` | — | evict key `2` (lowest freq) -> `{1: 10 (f=2), 3: 30 (f=1)}` | | `get(2)` | `-1` | `{1: 10 (f=2), 3: 30 (f=1)}` | | `get(3)` | `30` | `{1: 10 (f=2), 3: 30 (f=2)}` | | `put(4, 40)` | — | tie at f=2; evict least recently used (key `1`) -> `{3: 30 (f=2), 4: 40 (f=1)}` | | `get(1)` | `-1` | `{3: 30 (f=2), 4: 40 (f=1)}` | | `get(4)` | `40` | `{3: 30 (f=2), 4: 40 (f=2)}` | ### Required Interface Implement a class with the following methods: - a constructor taking the integer `capacity` - `get(key) -> int` - `put(key, value) -> None` Edge cases to handle: a cache of capacity that fills exactly, repeated `put` on an existing key (updates value and frequency, no eviction), and `get` on a missing key (returns `-1`, no frequency change).

Quick Answer: This question tests practical data structure design by requiring an O(1) implementation of a Least Frequently Used cache with tie-breaking by recency. It evaluates a software engineer's ability to combine hash maps and ordered collections to enforce eviction policies, a skill commonly assessed in system design and algorithm interviews.

Design and implement a data structure for a **Least Frequently Used (LFU) cache** that supports `get` and `put` in **O(1)** average time. The cache is created with a fixed positive integer `capacity` and supports: - `get(key)` — return the value of `key` if present, else `-1`. A successful `get` counts as a use (frequency += 1). - `put(key, value)` — update `key` if it exists, otherwise insert it. A `put` (insert or update) also counts as a use. A newly inserted key starts at frequency `1`. When the cache is at `capacity` and a new key must be inserted, **evict the key with the smallest use frequency**. On a tie (several keys share the lowest frequency), evict the **least recently used** of them — the one whose most recent `get`/`put` happened longest ago. ### Driver encoding (read carefully) Because the judge runs a single function, the call sequence is replayed for you. Implement: ``` solution(operations, arguments) -> list ``` - `operations[i]` is one of `"LFUCache"`, `"get"`, `"put"`. - `arguments[i]` is the argument list for that call: `[capacity]` for the constructor, `[key]` for `get`, `[key, value]` for `put`. - Return a list the same length as `operations`. Append `None` for the constructor and every `put`, and the returned integer for every `get`. Build your `LFUCache` class inside `solution` (or top-level) and drive it from the loop. ### Example `capacity = 2`, then: | Operation | Returns | Cache after (key: value, freq) | |--------------|---------|--------------------------------| | `put(1, 10)` | — | `{1: 10 (f=1)}` | | `put(2, 20)` | — | `{1: 10 (f=1), 2: 20 (f=1)}` | | `get(1)` | `10` | `{1: 10 (f=2), 2: 20 (f=1)}` | | `put(3, 30)` | — | evict 2 (lowest freq) -> `{1 (f=2), 3 (f=1)}` | | `get(2)` | `-1` | unchanged | | `get(3)` | `30` | `{1 (f=2), 3 (f=2)}` | | `put(4, 40)` | — | tie at f=2 -> evict LRU (key 1) -> `{3 (f=2), 4 (f=1)}` | | `get(1)` | `-1` | unchanged | | `get(4)` | `40` | `{3 (f=2), 4 (f=2)}` | ### Constraints - `1 <= capacity <= 10^4` - `0 <= key <= 10^5` - `0 <= value <= 10^9` - At most `2 * 10^5` total calls to `get` and `put`. - `get` and `put` must each run in **O(1)** average time.

Constraints

1 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
At most 2 * 10^5 total calls to get and put
get and put must each run in O(1) average time

Examples

Input: (["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get"], [[2], [1, 10], [2, 20], [1], [3, 30], [2], [3], [4, 40], [1], [4]])

Expected Output: [None, None, None, 10, None, -1, 30, None, -1, 40]

Explanation: The worked example from the prompt (capacity 2). put(3,30) evicts key 2 (lowest freq); put(4,40) hits a freq tie at 2 and evicts the least-recently-used key 1.

Input: (["LFUCache", "get"], [[1], [0]])

Expected Output: [None, -1]

Explanation: Edge case: get on an empty cache returns -1 and changes nothing.

Input: (["LFUCache", "put", "get", "put", "get", "get"], [[1], [1, 100], [1], [2, 200], [1], [2]])

Expected Output: [None, None, 100, None, -1, 200]

Explanation: Capacity 1. After put(2,200) the only slot must hold key 2, so key 1 is evicted and get(1) returns -1.

Input: (["LFUCache", "put", "put", "put", "put", "get", "get"], [[2], [1, 1], [1, 1], [1, 1], [2, 2], [1], [2]])

Expected Output: [None, None, None, None, None, 1, 2]

Explanation: Repeated put on existing key 1 only raises its frequency (no eviction). Inserting key 2 fills the cache exactly; both keys remain.

Input: (["LFUCache", "put", "put", "get", "get", "get", "put", "get", "put", "get", "get", "get"], [[3], [1, 1], [2, 2], [1], [2], [3], [3, 3], [3], [4, 4], [1], [3], [4]])

Expected Output: [None, None, None, 1, 2, -1, None, 3, None, -1, 3, 4]

Explanation: Capacity 3. After all keys reach freq 2, put(4,40) breaks the tie by LRU and evicts key 1 (touched longest ago), so the later get(1) returns -1.

Input: (["LFUCache", "put", "put", "put", "get", "get"], [[0], [0, 0], [1, 1], [2, 2], [0], [1]])

Expected Output: [None, None, None, None, -1, -1]

Explanation: Edge case: capacity 0. Every put is a no-op, so nothing is ever stored and all gets return -1.

Hints

Keep three maps: key->value, key->frequency, and frequency->ordered set of keys. Track the current minimum frequency.
Use an insertion-ordered container (e.g. Python OrderedDict / a doubly linked list per frequency) so that within one frequency bucket the front is the least recently used.
Every get and every successful put 'touches' a key: remove it from its current frequency bucket, increment its frequency, and append it to the next bucket. If the emptied bucket was min_freq, bump min_freq by one.
On insert into a full cache, evict from the min_freq bucket's front (oldest), then add the new key at frequency 1 and set min_freq back to 1.
Handle capacity 0 (or non-positive) by making put a no-op so nothing is ever stored.

Quick Overview