Practice: LRU Cache

Problem: https://leetcode.com/problems/lru-cache/

Recognition reminder: this is a design problem. You build a fixed-capacity cache where both get and put run in O(1) average time, and when the cache is full, the next put evicts the least-recently-used entry. The recognition is two structures working together: a hash map gives you O(1) lookup by key, and an ordering structure that tracks “most recently used” at one end and “least recently used” at the other gives you O(1) eviction of the right entry. The interesting tension is that a plain dict answers lookup in O(1) but does not, on its own, let you find and remove the least-recently-used key in O(1); pairing it with the right second structure is the whole design.

Before you start (the five-beat rhythm)

  1. Your Pattern Card for this week is already written.
  2. Name the pattern aloud and write your approach as a plain-English comment before any code.
  3. Struggle floor: 25 minutes unaided. No hints, no AI, no Discuss tab.
  4. If stuck past the floor, ask the tutor for a hint. Six rungs, one per ask.
  5. Debrief in your commit message before moving to the next problem.

Your target

Fill these in yourself before you look at anyone else’s solution:

Target time complexity per operation:  ____
Target space complexity:               ____

Both get and put are required to be O(1) on average. A list-backed ordering that you scan to find the least-recently-used entry is O(n) per operation, which violates the constraint. The interesting question is: what second structure, paired with the hash map, lets you both move an entry to “most recently used” and drop the “least recently used” entry without ever scanning?

The interface you implement

Write a class LRUCache in a file named solution.py in this folder (your own work repo, not the course repo). It supports:

LRUCache(capacity: int)        # initialize the cache with a positive size limit
get(key: int) -> int           # return the value for key, or -1 if the key is absent
put(key: int, value: int)      # insert or overwrite key with value (no return value)

A get or a put on an existing key counts as a use and makes that key the most recently used. A put that would exceed capacity evicts the least-recently-used entry first. Both operations must run in O(1) average time, exactly as the LeetCode problem requires.

Where your code goes

This folder ships only the problem spec and a provided-example test (tests/test_provided.py). Because this is a design problem, the test does not call one function; it drives your LRUCache through the operation sequence from the LeetCode example and checks each output. Run it locally before you submit to LeetCode’s judge. The judge is the oracle; the tutor will not confirm your answer by reading it.

Debrief (paste into your commit message) 

1. What pattern did this turn out to be?
2. What was the trigger phrase or input shape that should have made me reach for it?
3. What was the time and space complexity, and what would dominate at scale?
4. What edge case would have broken my first attempt?
5. What would I do differently in three days when I see this cold?