A simple LRU-style access cache

Python data engineering interview problem. Difficulty: advanced. Pattern: Hashing. About 20 minutes. Part of the Pro drill bank.

A hot key-value cache for SKU lookups should evict the least recently used entry when it hits capacity, the same policy as many production caches.

A cache keeps the most recently used items and throws away the least recently used one when it is full. This is called an LRU cache. Run a list of operations on a cache with room for cap items. ['put', key, value] stores a value (and counts as using it). ['get', key] returns the value, or None if it is not there, and counts as using it. When the cache has more than cap items, remove the one that was used longest ago. Return the results of all get operations in order. Write lru_run(cap, ops). With capacity 2: put 1, put 2, get 1 (returns 'a'), put 3 (this removes key 2, the oldest unused), get 2 (None), get 3 ('c'). The result is ['a', None, 'c']. The starter file already has the function name and its print lines. Keep them and fill in the body.

Requirements

• get returns the stored value or None.
• get and put both make a key the most recently used.
• When the cache is over capacity, remove the least recently used key.
• Return only the results of get operations, in order.

Constraints

• cap is at least 1.
• Operations are lists such as ['put', key, value] and ['get', key].

Examples

Input: lru_run(2, [['put', 1, 'a'], ['put', 2, 'b'], ['get', 1], ['put', 3, 'c'], ['get', 2], ['get', 3]]) Output: ['a', None, 'c'] This input follows the stated rules and produces this output.

Topics: lakebench, python, OOP.

More Python interview questions · All interview problems · Learn data engineering