Simulate an LRU cache

The problem

Run the operations against a least-recently-used cache with the given capacity. ['put', key, value] stores a value and ['get', key] reads one. Return the result of every get in order, using -1 for a miss.

Function: def lru_simulate(capacity,operations):

Example input (a JSON list of arguments): [2, [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2], ["put", 4, 4], ["get", 1], ["get", 3], ["get", 4]]]
Expected output: [1, -1, -1, 3, 4]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. An OrderedDict keeps keys in recency order.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def lru_simulate(capacity,operations):
    from collections import OrderedDict
    cache=OrderedDict();results=[]
    for op in operations:
        if op[0]=='get':
            key=op[1]
            if key in cache:cache.move_to_end(key);results.append(cache[key])
            else:results.append(-1)
        else:
            key,value=op[1],op[2]
            if key in cache:cache.move_to_end(key)
            elif len(cache)>=capacity:cache.popitem(last=False)
            cache[key]=value
    return results

Why it works

An OrderedDict keeps keys in recency order. Call move_to_end on every get hit and every put, and evict with popitem(last=False) when a new key would exceed capacity. Updating an existing key counts as a use but doesn't grow the cache.

Complexity: O(1) average per operation / O(capacity) space.

Time: O(1) average per operation · Space: O(capacity) space