## 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. ### Function Contract Implement `executeLru(capacity, operations)`, where operations use `['put', key, value]` and `['get', key]`. Return the results of all `get` operations. ### Constraints & Assumptions - `1 <= capacity <= 100,000`. - At most `200,000` operations are supplied. - Keys and values are integers. - Average time per operation must be constant. ### 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. ```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 - Promotes hits and updates to the most-recent position. - Deletes evicted nodes from both structures. - Handles capacity one 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?