← Python roadmap

Implement a bounded least-recently-used cache

ExpertSenior · 5–8 yearsData structures

Python 3.10+; standard library only. GIL discussion refers to conventional CPython builds, not optional free-threaded builds.

Problem statement

Implement get and put with eviction of the least recently used key when capacity is exceeded.

Keep a bounded set of frequently accessed lookup results.

Input: Nonnegative capacity and a sequence of key/value operations; values exclude None.

Output: get returns value or None for a miss.

  • Values are not None.
  • Single-threaded; no TTL.
  • Capacity zero must retain no entries.

Sample 1

Input: capacity2: put(a,1),put(b,2),get(a),put(c,3),get(b)
Output: None

b is least recent and evicted.

Sample 2

Input: capacity0:put(a,1),get(a)
Output: None

No capacity to store entries.

Brute-force solution

Keep an ordered list and linearly search/move keys on every operation.

O(1) expected per get/put.

from collections import OrderedDict
class LRU:
    def __init__(self,capacity):
        if capacity<0: raise ValueError("negative capacity")
        self.capacity=capacity;self.data=OrderedDict()
    def get(self,key):
        if key not in self.data: return None
        self.data.move_to_end(key);return self.data[key]
    def put(self,key,value):
        self.data[key]=value;self.data.move_to_end(key)
        if len(self.data)>self.capacity:self.data.popitem(last=False)
c=LRU(2);c.put("a",1);c.put("b",2);c.get("a");c.put("c",3);print(c.get("b"))
Optimized solution

OrderedDict combines a hash lookup with a linked order, enabling constant-time expected promotion and eviction.

  1. Move hits to the end.
  2. Move inserted/updated keys to the end.
  3. Evict from the beginning when over capacity.
from collections import OrderedDict
class LRU:
    def __init__(self,capacity):
        if capacity<0: raise ValueError("negative capacity")
        self.capacity=capacity;self.data=OrderedDict()
    def get(self,key):
        if key not in self.data: return None
        self.data.move_to_end(key);return self.data[key]
    def put(self,key,value):
        self.data[key]=value;self.data.move_to_end(key)
        if len(self.data)>self.capacity:self.data.popitem(last=False)
c=LRU(2);c.put("a",1);c.put("b",2);c.get("a");c.put("c",3);print(c.get("b"))
Complexity analysis

Time: O(1) expected per get/put.

Auxiliary space: O(capacity)

Test cases
  • Zero capacity.
  • Update existing key.
  • Missing key must not change order.
c=LRU(2)
c.put("a",1);c.put("b",2)
assert c.get("a")==1
c.put("c",3)
assert c.get("b") is None
c.put("a",4)
assert c.get("a")==4
z=LRU(0);z.put("a",1);assert z.get("a") is None
Common mistakes
  • Not promoting a successful get.
  • Evicting an entry unnecessarily on overwrite.
Key takeaways
  • Maintain an explicit recency invariant.
  • Bound memory.
  • Document miss and value semantics.
Follow-up challenges
  • How would you add TTL?
  • How would you synchronize concurrent calls?