The Forgetful Machine

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

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
W. W. Grainger

Problem

Our in-memory LRUCache holds at most capacity entries, and adding a new key to a full cache drops the entry that has gone longest without a read or a write. Once it is built, what does each get return when the ops log is replayed against one fresh cache, in the order the log runs?

It remembers everything, until it does not.

Example 1

Input:

capacity = 2, ops = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]]

Output:

[1,-1,3]

Example 2

Input:

capacity = 2, ops = [["put",1,1],["put",2,2],["put",1,10],["put",3,3],["get",2],["get",1],["get",3]]

Output:

[-1,10,3]

Worked solution and explanation

What this really is

Strip the costume and this is a dictionary that also remembers the order keys were last touched. Anyone can store key-value pairs. The interview is really asking whether you keep that touch order right in O(1) on every operation, including the one most candidates miss: a put to a key that already exists is an access too. It has to move that key to the most-recent end of the line, and it must not evict anything. Forget that and a hot key you keep overwriting gets evicted as if it were stale, so the cache silently discards exactly the data it exists to hold.

Walking the operations

Step 1: get: read and refresh recency

On a hit, move the key to the end so it becomes the most recent, then return its value. On a miss, return -1 and touch nothing: a failed lookup is not an access and must not reorder anything.

Step 2: put: insert or update, then evict

If the key is already present, move it to the end before overwriting so the update counts as an access. Then assign the value. Only after assigning do you check size: if you are now over capacity, pop the front item. An overwrite never grows the cache, so this check after the insert evicts only when a genuinely new key arrives, with one uniform code path for new and existing keys.

Step 3: Replay the log and collect get results

The grader calls LRUCache_driver(capacity, ops). It constructs a single LRUCache(capacity), walks ops in order (a ['put', k, v] calls put, a ['get', k] calls get), and appends only the get return values to the result list. A log with no gets yields an empty list, which is correct.

The solution

`OrderedDict`-backed LRU cache with driver
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

def LRUCache_driver(capacity, ops):
    cache = LRUCache(capacity)
    results = []
    for op in ops:
        if op[0] == 'get':
            results.append(cache.get(op[1]))
        else:
            cache.put(op[1], op[2])
    return results

Common follow-up questions