Build an LRU Cache with a Hash Map and Linked List

## Problem Build an LRU cache backed by a hash map and a doubly linked list. Capacity is the number of entries. - `get(key)` returns the value or `-1`; a hit becomes most recently used. - `put(key, value)` inserts or updates; an existing key becomes most recently used. - Inserting a new key while full evicts exactly the least recently used entry. ### Portable Function Contract Implement `executeLru(capacity, operations)`. - `capacity` is an integer. - `operations` is a list of string rows. - A put row has exactly three fields: `["put", keyText, valueText]`. - A get row has exactly two fields: `["get", keyText]`. - `keyText` and `valueText` are canonical signed 64-bit decimal integers: `"0"`, a nonzero digit followed by digits, or `"-"` followed by a nonzero digit and then zero or more digits. They contain no leading zero, whitespace, or plus sign. Parse keys and values exactly as signed 64-bit integers. Return, in operation order, a list of canonical signed decimal strings for all `get` rows. A cache miss contributes `"-1"`. A hit contributes the stored value formatted canonically, so every signed 64-bit result remains exact through the JavaScript JSON transport. A stored value may also be `-1`; the returned string is the same in either case. All operation rows satisfy the shapes above. Their string encoding is part of the portable console interface; do not use a heterogeneous row whose first element is a string but whose other elements are language-specific numeric objects. ### Constraints & Assumptions - `1 <= capacity <= 100,000`. - At most `200,000` operations are supplied. - Keys and values are signed 64-bit integers encoded by the canonical strings above. - Average time per operation must be constant. - The returned list contains at most `200,000` canonical signed decimal strings. ### Clarifying Questions to Ask - Does `put` on an existing key trigger eviction? No; update and promote that entry. - Does a failed `get` affect recency? No. - Is the capacity measured by entry count? Yes. - Why are keys and values strings inside operation rows? A uniform string-row shape maps directly to all four console languages while preserving the exact integer values. - How should numeric strings be interpreted? Parse them as signed decimal 64-bit integers before applying the cache operation. ```hint One node must have one owner The map should point to the exact linked-list node. Moving or deleting that node must not leave another copy behind. ``` ```hint Isolate list operations Helpers for detach, attach-as-most-recent, and evict-least-recent make every public operation a short composition of correct primitives. ``` ### Example ```text capacity = 2 operations = [ ["put","1","10"], ["put","2","20"], ["get","1"], ["put","3","30"], ["get","2"], ["get","3"] ] result = ["10","-1","30"] ``` ### Evaluation Focus - Parses the uniform string rows into exact signed 64-bit keys and values and formats every get result canonically. - Promotes hits and updates to the most-recent position. - Deletes evicted nodes from both structures. - Handles capacity one, misses, negative keys and values, and repeated updates. - Uses `O(capacity)` space and average `O(1)` operations. ### Extensions to Discuss 1. How would a least-frequently-used policy change the data structures? 2. Where would locks be placed for a thread-safe implementation? 3. How would you add per-entry expiration?