280. LRU Cache Implementation

Design a Least Recently Used (LRU) cache with a fixed capacity. Simulate m operations, each 'PUT k v' (insert/update key k with value v, evicting the least recently used entry first if the cache is already at capacity) or 'GET k' (return the value for key k, or -1 if not present). Both PUT and GET count as a 'use' of the key, making it the most recently used. GET prints its result; PUT produces no output. Print one result per line, in the order GET operations occurred.

Input: The first line contains the cache's capacity. The second line contains an integer m, the number of operations. Each of the next m lines contains one operation: 'PUT k v' or 'GET k'. Output: Print one line per GET operation, in order, printing the value or -1 if the key isn't present.

1 <= capacity <= 10^5, 1 <= m <= 10^5

Both GET and PUT count as a 'use' that refreshes a key's recency - a very common implementation bug is forgetting to update recency on GET, treating it as a pure read with no side effect on eviction order.

Build a fixed-size cache that remembers key-value pairs, but when it's full and a NEW key needs to be added, it kicks out whichever existing key hasn't been touched (read OR written) the longest. Brute force: Store entries in a plain list and, to find the least-recently-used one, scan through recording timestamps of last access - this works but costs O(n) to find the eviction candidate every time the cache is full, rather than instant O(1). Optimised: Combining a hash map (for instant key lookup) with a doubly linked list (for instant 'move to most-recent end' and instant 'remove least-recent end' operations) gives every single operation - GET, PUT, and eviction - O(1) time, since a doubly linked list lets you splice a node out from anywhere and re-insert it at an end without shifting any other elements.

Keep a hashmap from key to (value, last-used-timestamp) so that checking whether a key exists and reading/updating its value is O(1). Increment a global counter on every operation and store it as the timestamp when a key is touched. GET and PUT-to-existing-key become O(1), but eviction on a PUT to a new key at full capacity still requires scanning all entries in the hashmap to find the one with the smallest timestamp. This is a clear improvement over the brute-force approach's linear existence checks, even though eviction remains linear in capacity. Time: O(1) amortized get/put value access, O(capacity) eviction Space: O(capacity)

Combine a hashmap from key to a node in a doubly linked list with the linked list itself maintaining strict recency order (most-recently-used at the front, least-recently-used at the back). GET looks up the node via the hashmap in O(1) and then unlinks and relinks it to the front in O(1) using its stored pointers. PUT does the same for an existing key, or for a new key at capacity unlinks the tail node (the true least-recently-used entry, found in O(1) with no scanning) before inserting the new one at the front. Every operation - lookup, recency update, and eviction - is true O(1), because the linked list's pointer structure directly encodes the eviction order instead of requiring any scan to find it. Time: O(1) Space: O(capacity)

Store all cached (key, value) pairs in a simple list. For GET, linearly scan the list to find the key, and if found move that entry to mark it most-recently-used. For PUT, linearly scan to check if the key already exists (update it if so), otherwise, if at capacity, linearly scan to find the least-recently-used entry to evict, then insert the new entry. Every operation is correct but costs time proportional to the number of entries currently cached, since there's no direct-lookup structure. Time: O(capacity) per operation Space: O(capacity)

1. Keep a hash map from key to value for instant O(1) lookup, PLUS an ordering structure (like a doubly linked list) tracking which keys were used most recently versus longest ago. 2. On GET, look up the key in the hash map - if found, move that key to the 'most recently used' end of the ordering, and return its value; if not found, return -1. 3. On PUT for an EXISTING key, update its value and also move it to the 'most recently used' end. 4. On PUT for a brand-NEW key when the cache is already full, first evict the key at the 'least recently used' end, then insert the new key at the 'most recently used' end.

Time: O(1) for every GET and PUT operation - genuinely constant time, not just 'fast on average', because both the hash map lookup and the linked-list splice/move are O(1) by construction. Space: O(capacity), since the cache never holds more entries than its fixed capacity allows.

capacity = 1 (every new key immediately evicts the previous one); a GET on a key that was never inserted or already evicted (print -1); a PUT that updates an existing key's value without evicting anything (per the hints); m and capacity both up to 10^5 for performance.

This is one of the most frequently asked system-design-adjacent coding interview problems - be ready to explain PRECISELY why a hash map ALONE isn't enough (it can't tell you usage order) and why a linked list ALONE isn't enough (it can't do instant key lookup) - you genuinely need both together.