LRU Cache

Problem

Clone the starter repo and build an LRU cache in your own editor with your own AI tools, under a 30-minute timer.

The spec

Implement an LRUCache with:

• get(key) — return the value, or -1 if absent. A get marks the key as most recently used.
• put(key, value) — insert or update, marking it most recently used. If the cache exceeds capacity, evict the least recently used key.

Both operations must be O(1) average. The starter repo ships a test harness — make it pass, then add edge cases of your own (capacity 0, capacity 1, overwriting existing keys, repeated gets).

What interviewers watch

• Do you decide the composition (map + doubly linked list with sentinels) before prompting the AI, or let it invent one?
• Is the "move to front on get" behavior actually implemented, or just promised?
• Can you explain the O(1) claim for each operation when asked?

Submission

Export your code (zip) and your AI chat transcript, note the tools you used and the time taken, and submit for a verdict.

Deliverables

• An LRUCache class with get(key) and put(key, value), both O(1) average
• Evict the least recently used entry when over capacity
• Pass the provided test harness
• A short README explaining your design and complexity