The Frequency Eviction

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

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.

When storage is tight, something has to go.

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.

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

Common follow-up questions