Implement an LRU cache with O(1) ops

Design and code an LRU cache supporting get(key) and put(key, value) in O(1) average time with capacity N. Specify your data structures, handle updates to existing keys, and define precise eviction behavior when capacity is exceeded. Discuss thread-safety concerns and how you would add an optional per-key TTL without violating big-O guarantees. Provide complexity analysis for time and space, and identify edge cases (e.g., N=1, repeated gets, large values).

Implement an LRU Cache with O(1) get and put

Design a Least Recently Used (LRU) cache that supports get and put in O(1) average time, given a fixed capacity.

Rules:

• get(key) returns the value if the key exists, otherwise -1. A successful get marks the key as the most recently used.
• put(key, value) inserts or updates the value for key. Updating an existing key also marks it most recently used. If inserting a new key would exceed capacity, evict the least recently used key first.

To make the cache executable here, implement a single driver function that replays a sequence of operations:

solution(capacity, operations)

• capacity (int): the cache capacity (>= 1).
• operations (list): each element is either ['get', key] or ['put', key, value], applied in order.

Return the list of results from the get operations only (in order), where a miss returns -1. put operations produce no output.

Classic implementation: a hash map for O(1) lookup plus a doubly linked list (or an ordered map / OrderedDict) to maintain recency order so that eviction and re-ordering are also O(1).

Constraints

• 1 <= capacity
• Keys and values are integers.
• Each operation is ['get', key] or ['put', key, value].
• A miss on get returns -1.
• Both a successful get and a put (insert or update) mark the key most recently used.
• Eviction removes the least recently used key when a new insert would exceed capacity.

Examples

Example 1

Input: (2, [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2], ['put', 4, 4], ['get', 1], ['get', 3], ['get', 4]])
Output: [1, -1, -1, 3, 4]

Explanation: Capacity 2. After put(1),put(2): {1,2}. get(1)=1 makes 1 MRU. put(3) evicts LRU key 2 -> {1,3}. get(2)=-1 (evicted). put(4) evicts LRU key 1 -> {3,4}. get(1)=-1, get(3)=3, get(4)=4.

Example 2

Input: (1, [['put', 2, 1], ['get', 2], ['put', 3, 2], ['get', 2], ['get', 3]])
Output: [1, -1, 2]

Explanation: Capacity 1 edge case. put(2,1) -> {2}. get(2)=1. put(3,2) evicts 2 -> {3}. get(2)=-1, get(3)=2.

Hints

1. Combine a hash map (O(1) key lookup) with a structure that preserves recency order, such as a doubly linked list or an ordered map.
2. On a successful get, move the key to the most-recently-used end. On put, insert/update then move-to-end.
3. Evict only when inserting a NEW key pushes the size beyond capacity — updating an existing key never triggers eviction.
4. Python's collections.OrderedDict gives O(1) move_to_end and popitem(last=False), making the whole thing O(1) per op.