Stage 2: LRU Core

Objective:Combine a hashmap with a doubly-linked list to achieve O(1) get and put with correct LRU eviction semantics.

The LRU cache wraps the doubly-linked list with a Map from key to node. The Map handles lookup (is "user:1" in the cache?). The list handles order (which key was used longest ago?).

get(key):

1. If key is not in the Map, return -1
2. Find the node via the Map (O(1))
3. Move the node to the head of the list (O(1) -- you have the node, no traversal)
4. Return node.value

put(key, value):

1. If key already exists: update node.value, move to head
2. If key is new: create a node, add to head of list, store in Map
3. If size > capacity: remove the tail node from the list, delete its key from the Map (the tail node's key is needed for this -- store it in the node)

Implement createLRUCache(capacity) returning:

• get(key) -- return cached value or -1
• put(key, value) -- store value, evict LRU if over capacity
• size -- number of entries currently in the cache

Why -1 for missing? The LRU interface convention (from Leetcode 146 and real cache libraries) returns -1 for cache miss so tests don't need to distinguish undefined (absent) from null (stored). Your implementation should follow this convention exactly.

Why this matters in production

The LRU cache is the canonical example of combining two data structures to get performance that neither provides alone. A hashmap gives O(1) key lookup but no ordering. A doubly-linked list gives O(1) ordered insertion and removal but no fast lookup. Together: O(1) everything. This is why LRU cache appears in every system design interview -- it tests whether you understand that data structure composition is often the answer to performance problems. The same composition pattern appears in Redis's sorted sets (hashmap + skip list) and in Python's `OrderedDict`.