Implement LRU cache with O(1) ops

Design and implement a fixed-capacity cache supporting get(key) -> value and put(key, value) in O(1) average time. When capacity is reached, evict the least recently used entry. Specify how recency is updated on get and put, how updates to existing keys are handled, what to return for missing keys, and discuss thread-safety options and testing strategy.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Implement an LRU Cache with O(1) Operations

Design and implement a fixed-capacity Least Recently Used (LRU) cache that supports two operations in O(1) average time:

• put(key, value) — insert or update a key. If the key already exists, overwrite its value and mark it as most recently used. If inserting a new key would exceed the cache capacity, first evict the least recently used entry.
• get(key) — return the value for key if it is present (and mark it most recently used), otherwise return -1.

Because a cache is stateful and operations are interdependent, this challenge gives you the whole operation stream up front so your solution is deterministically testable. Implement a function solution(capacity, operations) where:

• capacity is a positive integer — the maximum number of key/value pairs the cache may hold.
• operations is a list of operations applied in order. Each operation is one of:
  • ["put", key, value]
  • ["get", key]

Return a list with one entry per operation, in order:

• For each put, append null (Python None).
• For each get, append the looked-up value, or -1 if the key is absent.

Recency rules:

• A successful get makes that key the most recently used.
• A put (whether it inserts a new key or updates an existing one) makes that key the most recently used.
• Eviction removes the single least recently used key, and only happens when a new insertion pushes the size past capacity.

The intended O(1) design pairs a hash map (key → node) with a doubly linked list ordered by recency (head = most recent, tail = least recent). The hash map gives O(1) lookup; the linked list gives O(1) move-to-front and O(1) tail eviction. Python's OrderedDict provides the same guarantees via move_to_end and popitem(last=False).

Constraints

• 1 <= capacity <= 10^4
• 0 <= number of operations <= 10^5
• Keys and values are integers in the range -10^9 .. 10^9
• Each 'put' has the form ["put", key, value]; each 'get' has the form ["get", key]
• get on a missing key returns -1 (values are otherwise valid integers, including negative ones)

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: [None, None, 1, None, -1, None, -1, 3, 4]

Explanation: Capacity 2, the canonical LRU trace. put(1,1) and put(2,2) fill the cache. get(1)=1 makes 1 most recent (order now: 1 newest, 2 oldest). put(3,3) overflows and evicts the LRU key 2. get(2)=-1 (evicted). put(4,4) evicts the now-LRU key 1. 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: [None, 1, None, -1, 2]

Explanation: Capacity 1 edge case. put(2,1) then get(2)=1. put(3,2) must evict key 2 because only one slot exists, so get(2)=-1 and get(3)=2.

Hints

1. You need two things at once: O(1) lookup by key, and O(1) knowledge of which key is least recently used. A hash map alone gives you the first but not the second.
2. Pair a hash map (key -> node) with a doubly linked list ordered by recency: head = most recently used, tail = least recently used. On any access, splice the node to the head; to evict, remove the tail.
3. Treat an update to an existing key like an access: refresh its recency, then overwrite its value. Eviction should only trigger after an insertion makes the size exceed capacity — never on a get or on an in-place update.
4. In Python, collections.OrderedDict does all of this for you: move_to_end(key) refreshes recency and popitem(last=False) removes the LRU entry. In Java, a LinkedHashMap with accessOrder=true plus an overridden removeEldestEntry is the equivalent shortcut.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Design and implement a fixed-capacity cache supporting get(key) -> value and put(key, value) in O(1) average time. When capacity is reached, evict the least recently used entry. Specify how recency is updated on get and put, how updates to existing keys are handled, what to return for missing keys, and discuss thread-safety options and testing strategy.

Recommended Approach

Use a hash map from key to doubly linked-list node plus a doubly linked list ordered by recency. get moves the node to the front. put updates and moves an existing node, or inserts a new node at the front and evicts the tail when capacity is exceeded.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

get and put are O(1) average time. Space is O(capacity).

Edge Cases and Tests

Capacity 0 or 1, updating an existing key, eviction order after get, repeated puts, and missing-key gets.