The Frequency Eviction

A hard Python interview practice problem on DataDriven. Write and execute real python code with instant grading.

Domain

Python

Difficulty

hard

Seniority

L5

Problem

Implement an LFU (Least-Frequently-Used) cache and drive it through a sequence of operations. Your `LFUCache(capacity)` must support: - `get(key)` returns the stored value, or -1 if the key is absent. A successful `get` counts as an access. - `put(key, value)` inserts or updates a key. An update counts as an access. When inserting a new key would exceed `capacity`, first evict the least-frequently-used key; break frequency ties by evicting the least-recently-used key. If `capacity <= 0`, `put` stores nothing. Write the top-level driver `run_lfu_cache(operations, args)`. `operations` is a list of method-name strings whose first entry is always `"LFUCache"` (the constructor); `args` is a parallel list of argument lists. Replay them in order against a single cache instance and return the list of return values: `None` for the constructor and for every `put`, and the returned value (or -1) for every `get`. Example: operations `["LFUCache","put","put","get","put","get","get"]` with args `[[2],[1,1],[2,2],[1],[3,3],[2],[3]]` returns `[None, None, None, 1, None, -1, 3]` (inserting key 3 at capacity 2 evicts key 2, the tied-frequency least-recently-used entry).

Summary

When storage is tight, something has to go.

Practice This Problem

Solve this Python problem with real code execution. DataDriven runs your Python code in a real environment and grades it automatically.