LFU Cache with LRU Tiebreaker
Reported
3 times
Last seen
2021-11-29
First seen
2021-11-29
Active in
2021, 2024, 2025
Description
Design and implement a Least Frequently Used (LFU) cache with capacity `n`. Support two operations: • `get(key)` — Return the value if key exists, otherwise return -1. • `put(key, value)` — Insert or update the key-value pair. If the cache is at capacity, evict the least frequently used key. If there's a tie in frequency, evict the least recently used among them. Both operations must run in **O(1)** average time. **Example:** ``` LFUCache cache = new LFUCache(2); cache.put(1, 1); // freq(1)=1 cache.put(2, 2); // freq(2)=1 cache.get(1); // returns 1, freq(1)=2 cache.put(3, 3); // evicts key 2 (freq=1, LRU), freq(3)=1 cache.get(2); // returns -1 (evicted) cache.get(3); // returns 3, freq(3)=2 ``` **Constraints:** - 0 ≤ capacity ≤ 10^4 - 0 ≤ key ≤ 10^5 - 0 ≤ value ≤ 10^9 - At most 2 × 10^5 calls to get and put
Approach Tips
**Core Insight:** Combine three data structures for O(1) everything. **Data Structures:** 1. `keyMap: HashMap<key, Node>` — O(1) lookup by key 2. `freqMap: HashMap<freq, DoublyLinkedList>` — each frequency maps to a DLL of nodes with that frequency (head = most recent, tail = least recent) 3. `minFreq: int` — tracks the current minimum frequency for O(1) eviction **Algorithm:** `get(key)`: - If key not in keyMap → return -1 - Remove node from freqMap[node.freq] - If freqMap[node.freq] is now empty AND node.freq == minFreq → minFreq++ - node.freq++ - Add node to head of freqMap[node.freq] - Return node.value `put(key, value)`: - If key exists → update value, call get(key) logic to bump frequency - If at capacity → remove tail node from freqMap[minFreq] (this is the LFU+LRU victim), delete from keyMap - Create new node with freq=1, add to keyMap and head of freqMap[1] - Set minFreq = 1 **Why this works:** Each frequency bucket is a DLL ordered by recency. The tail of the minFreq bucket is always the eviction target — it's both the least frequent AND the least recently used among the least frequent. **Complexity:** O(1) time for both operations, O(capacity) space. **What interviewers look for:** - Clean separation of the DLL operations (addHead, removeTail, removeNode) - Correct handling of the minFreq update (only increment when the old min-freq bucket becomes empty) - Edge case: capacity = 0 **Common mistakes:** - Forgetting to update minFreq when the last node leaves a frequency bucket - Not handling the case where put() updates an existing key (should bump frequency, not evict) - Using a single LRU list (that's LRU cache, not LFU)
Related LeetCode Problem
LC 460 - LFU Cache
Sources
Rippling
HR Tech/SaaS
Typically appears in: Technical Phone Screen
60 min — LeetCode-style problem in CodePair. Meta-like pace expected.