The Eviction Policy

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
L4
Asked in
Coinbase

Problem

A read-through cache sits in front of a slow store and holds at most a fixed number of entries; once it is full, the entry that has gone longest without being touched is dropped to make room for a new one. Replay operations against such a cache and return one result per operation, in order.

operations[0] is always ['LRUCache', capacity], which sets the entry limit (capacity is at least 1); each later operation is either ['put', key, value], which inserts or overwrites a key, or ['get', key], which returns that key's value or -1 when the key is absent. Both reading and writing a key count as touching it, so the next eviction removes whatever key has stayed idle longest. The constructor and every put contribute None to the result list; each get contributes the value it found, or -1.

Fixed capacity. The key left idle longest is the one that goes.

Example 1

Input:

operations = [["LRUCache",2],["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]]

Output:

[null,null,null,1,null,-1]

Example 2

Input:

operations = [["LRUCache",1],["put",1,10],["get",1],["put",2,20],["get",1],["get",2]]

Output:

[null,null,10,null,-1,20]

Worked solution and explanation

What this really is

Strip away the cache framing and this is an ordering problem wearing a storage costume: at every moment you must know which key was touched least recently, and you must know it without scanning. Anyone can stash keys in a dict. The trap is recency. A get is not a read-only operation here, it reorders. Candidates who treat get as a pure lookup and then evict by insertion order pass the easy cases and quietly evict the wrong key the first time a read lands before a write.

Break down the requirements

Step 1: get returns the value and marks the key most recently used

If the key exists, move it to the back of the order and return its value. Otherwise return -1, and leave the order untouched (a miss is not a touch).

Step 2: put inserts or updates and marks the key most recently used

If the key already exists, overwrite it and move it to the back. If it is new and the cache is at capacity, evict the front (least recently used) before inserting.

Step 3: drive the cache from the operations list

The driver reads operations[0] = ['LRUCache', capacity] to construct the cache, then replays each ['put', key, value] and ['get', key]. It appends None for the constructor and each put, and the looked-up value (or -1) for each get, returning the full list.

The solution

OrderedDict-based LRU cache with a replay 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):
        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)
        return None


def the_eviction_policy(operations):
    cache = None
    results = []
    for op in operations:
        name = op[0]
        if name == "LRUCache":
            cache = LRUCache(op[1])
            results.append(None)
        elif name == "put":
            results.append(cache.put(op[1], op[2]))
        elif name == "get":
            results.append(cache.get(op[1]))
    return results

Common follow-up questions