# The Frequency Eviction > When storage is tight, something has to go. Canonical URL: Domain: Python · Difficulty: hard · Seniority: L5 · Asked in: Citadel ## Problem You are replaying a captured operation log against an LFU (least-frequently-used) cache to reproduce the value each call returned, where `run_lfu_cache(operations, args)` replays the parallel `operations` and `args` lists against a single cache instance. The cache holds at most `capacity` entries: `get(key)` returns the stored value or -1 when the key is absent, and `put(key, value)` inserts or updates an entry, where both a successful `get` and an update count as an access toward a key's frequency. When a `put` on a new key would exceed `capacity`, evict the least-frequently-used key, breaking ties by removing the least-recently-used among them; a cache constructed with `capacity <= 0` stores nothing. ## Example Input: ``` operations = ["LFUCache","put","put","get","put","get","get","put","get","get","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]] ``` Output: ``` [null,null,null,1,null,-1,3,null,-1,3,4] ``` ## Worked solution and explanation ### Why this problem exists in real interviews This is an LFU cache wearing an operation-replay costume. The hard part is not the driver loop that zips `operations` with `args`; that is a five-line dispatcher anyone writes. The skill being probed is whether you can make eviction O(1) while honoring TWO orderings at once: frequency first, recency as the tiebreak. Get the tiebreak wrong and your cache evicts the wrong entry the moment two keys share a frequency, which is most of the time. > **Trick to Solving** > > Keep keys bucketed by frequency, and inside each bucket keep them in insertion/use order with an `OrderedDict`. Track the global `min_freq`. Eviction is then `freq_keys[min_freq].popitem(last=False)`: oldest key in the least-frequent bucket, both orderings satisfied in one pop. On every access you move the key from its bucket to the `freq + 1` bucket. --- ### Break down the requirements #### Step 1: Track each key's value and frequency Every key carries two facts: its value and its current access count. Two flat dicts, `key_val` and `key_freq`, keyed by key. #### Step 2: Bucket keys by frequency Group keys by access count in `freq_keys[freq]`, an OrderedDict so that within a single frequency the oldest key sits at the front. That front position IS the LRU tiebreak. #### Step 3: Evict in one pop When a new key overflows capacity, pop the front of `freq_keys[min_freq]`. That single call picks the least-frequent key and, among ties, the least-recently-used one. #### Step 4: Keep `min_freq` honest Inserting a new key always sets `min_freq = 1`, because the new key has frequency 1. When an access empties the bucket at `min_freq`, bump `min_freq` to `freq + 1`. Miss either update and eviction targets the wrong bucket. #### Step 5: Drive the operation sequence The top-level `run_lfu_cache` builds the cache on the "LFUCache" op, dispatches `get`/`put`, and appends each return value (None for the constructor and put). The cache class lives nested inside the driver, which is the exact shape the grader invokes. --- ### The solution **Frequency-bucketed cache with OrderedDict tiers** ```python from collections import OrderedDict, defaultdict def run_lfu_cache(operations, args): class LFUCache: def __init__(self, capacity: int): self.capacity = capacity self.key_val = {} self.key_freq = {} self.freq_keys = defaultdict(OrderedDict) self.min_freq = 0 def get(self, key): if key not in self.key_val: return -1 freq = self.key_freq[key] del self.freq_keys[freq][key] if not self.freq_keys[freq]: del self.freq_keys[freq] if self.min_freq == freq: self.min_freq += 1 self.key_freq[key] = freq + 1 self.freq_keys[freq + 1][key] = True return self.key_val[key] def put(self, key, value): if self.capacity <= 0: return if key in self.key_val: self.key_val[key] = value self.get(key) return if len(self.key_val) >= self.capacity: evict_key, _ = self.freq_keys[self.min_freq].popitem(last=False) del self.key_val[evict_key] del self.key_freq[evict_key] self.key_val[key] = value self.key_freq[key] = 1 self.freq_keys[1][key] = True self.min_freq = 1 results = [] cache = None for op, arg in zip(operations, args): if op == "LFUCache": cache = LFUCache(*arg) results.append(None) elif op == "get": results.append(cache.get(*arg)) else: results.append(cache.put(*arg)) return results ``` > **Time and Space Complexity** > > **Time:** O(1) amortized for both `get` and `put`, so O(m) to replay m operations. Every dict and OrderedDict operation, including `popitem(last=False)`, is O(1). > > Space: O(capacity) for the stored keys spread across frequency buckets, plus O(m) for the results list. > **Interviewers Watch For** > > The reuse of `get` inside `put` for the update branch. Setting `key_val[key] = value` and then calling `self.get(key)` cleanly folds the value update and the frequency bump into one path. The tell of a shaky candidate is duplicating the bucket-moving logic in both methods and then letting the two copies drift. > **Common Pitfall** > > Calling `self.get(key)` to bump frequency only works for keys that already exist; for a brand-new key it returns -1 and bumps nothing useful. The update branch guards on `key in self.key_val` first, and the insert branch sets `min_freq = 1` directly instead of routing through `get`. --- ## Common follow-up questions - What is the tradeoff between LFU and LRU in practice? _(Tests that LFU resists scan pollution but is slower to adapt to workload shifts.)_ - How would you implement a windowed LFU that only counts recent accesses? _(Tests combining time-based decay with frequency counting.)_ - How do real caches like Redis implement eviction? _(Tests knowledge of approximate LFU using probabilistic counters.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_frequency_eviction) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.