#09HardData Structures · 38% acceptance

Design an LRU Cache

DesignHash MapLinked List

Design a cache with a fixed capacity that supports get(key) and put(key, value) in O(1) average time. When full, it evicts the least-recently-used entry.

Every pipeline you have written that caches expensive results is solving a version of this. Now make it strict.

Examples

Input: capacity = 2; put(1,1); put(2,2); get(1); put(3,3); get(2)

Output: get(2) -> -1

Note: Inserting 3 evicts key 2, the least recently used.

Constraints

·1 ≤ capacity ≤ 3000
·At most 10^5 calls to get and put.

Hints

solution.pyPython 3

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.store = {}            # key -> value, insertion-ordered

    def get(self, key):
        if key not in self.store:
            return -1
        val = self.store.pop(key)  # move to most-recent
        self.store[key] = val
        return val

    def put(self, key, value):
        if key in self.store:
            self.store.pop(key)
        elif len(self.store) >= self.cap:
            oldest = next(iter(self.store))
            self.store.pop(oldest)
        self.store[key] = value

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.