Before you start

LRU Cache is the design problem that tests whether you actually know your data structures. Almost every big-tech design interview includes it — small, unambiguous, and reveals whether you can hit the O(1) requirement.

Why no design patterns fit

Modules 1-3 taught GoF patterns. NONE of them are the right answer here.

• Strategy? Not swapping algorithms.
• Factory? Not building polymorphic types.
• Observer? Nothing to observe.
• State? Only two states (present / absent).

This is a data-structure design problem, not a class-composition design problem. Your design.md should say this out loud. Reaching for a pattern to "look sophisticated" is a junior signal.

The grader accepts "no pattern from modules 1-3 applies — this is a data-structures problem" as a valid answer for the Patterns section. Say so. Then defend your data-structure choice.

The DS choice

Three reasonable ways to do it:

1. Plain list. get O(N), put O(N). Fails the O(1) requirement.
2. Python's OrderedDict. get O(1), put O(1), and move_to_end handles the "promote" step. Fine in real code. But interviewers usually want to see you know WHAT OrderedDict does inside — hence...
3. Doubly-linked list + hash map. Manual implementation. O(1) both operations. Interview-classic.

Your design.md should pick one and defend it. For the tests, OrderedDict would work — but the "show you know the mechanics" answer is DLL + map.

The rule that matters

The DLL and the hash map must stay in sync. Every put that adds a key must add to both. Every eviction must remove from both. Every promote must reorder the DLL AND leave the map untouched.

The way to enforce this: every change goes through a small number of helper methods (_add_after_head, _unlink, _evict_tail). No self._map[key] = node in one place and self._map.pop(key) scattered elsewhere.

Why sentinels help

A DLL with dummy head and tail sentinels (nodes with key=None, value=None, no meaning) makes edge cases trivial. Every real node has BOTH a prev and a next — no if node.prev is None special cases. The MRU is head.next, the LRU is tail.prev.

Interviewers can spot right away whether you're using sentinels — cleaner code is a small signal that you've implemented this before.

Performance follow-ups to expect

• "How would you make this thread-safe?" — wrap all operations in a lock. Or use a lock-free CAS approach (harder, out of scope).
• "How would you add TTL (time-based expiry)?" — new mechanism (min-heap on expiry) alongside the LRU. Two eviction policies working together.
• "How would you scale it across machines?" — Redis. Consistent hashing. HLD territory.

Your design.md doesn't need to answer these, but a Trade-offs section that mentions "single-threaded and no TTL are known simplifications" scores points.

Design a fixed-capacity Least-Recently-Used cache. This problem is 90% data structures, 10% design. Your design.md will focus on the DS choices, not on Gang-of-Four patterns.

The problem

A LRUCache(capacity):

• get(key) — returns value, or None if not present. Accessing a key marks it as most-recently-used.
• put(key, value) — sets value. If key exists, updates value AND marks as MRU. If cache is at capacity AND key is new, EVICT the least-recently-used entry first.
• size() — current count.
• keys() — list of keys, from MRU to LRU.

Constraints:

• Both get and put must be O(1) (amortized).
• Capacity is fixed at construction.

Requirement-gathering questions

1. Thread-safe? — Single-threaded MVP.
2. TTL / expiration by time? — No, only LRU eviction by access.
3. Fixed vs resizable capacity? — Fixed at construction.
4. Missing key on get: None or raise? — Return None.
5. put with same key: does it change position? — Yes, put promotes to MRU (both new and existing keys).

Design goals

• O(1) for get and put.
• Invariants: total entries never exceeds capacity; the MRU list is always in sync with the map.

Your task

This problem is fundamentally about combining a doubly-linked list (for O(1) reorder) with a hash map (for O(1) lookup). Your design.md should EXPLAIN why that combination is the right choice — not just apply it.

Design.md's Patterns section can (and honestly should) say "no GoF pattern applies — this is a data-structures problem". What patterns are for is design AROUND the DS: how the LRU interacts with the caller, how invariants are enforced.

Public API:

from main import LRUCache

c = LRUCache(capacity=3)
c.put("a", 1)
c.put("b", 2)
c.put("c", 3)
c.get("a")           # 1; "a" is now MRU
c.put("d", 4)        # evicts "b" (LRU)
c.keys()             # ["d", "a", "c"] (MRU first)
c.size()             # 3

Click Submit to run the tests.