Implement an O(1) LRU Cache

Implement `run_lru(capacity, operations)` to model a least-recently-used cache with integer keys and values. Each operation is a three-integer row: - `[0, key, value]` performs `put(key, value)` and produces no output. - `[1, key, 0]` performs `get(key)`; the third value is padding. Append the stored value to the result, or append `-1` if the key is absent. Both a successful `get` and a `put` of an existing key make that key most recently used. Inserting a new key at full capacity evicts the least recently used key. Capacity is positive. Return the results of all `get` operations in order. Each operation should run in `O(1)` time. ```hint Combine lookup with ordering A hash map locates a key's node, while a doubly linked list records recency from most recent to least recent. ``` ```hint Isolate pointer updates Use sentinel head and tail nodes plus helpers that remove a node and add a node at the most-recent end. ``` ### Discussion Extensions - Why does one lock around the entire cache limit concurrency, and why does segmented locking provide only approximate global LRU? - How would lazy expiry plus background cleanup add per-entry expiration? - What responsibilities change when keys are sharded across cache nodes?