LRU Cache
Reported by candidates from Navan's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The mistake that sinks a first attempt at this one is forgetting that a PUT on an existing key also counts as a use. Navan reported this LRU Cache OA in June 2024, and it's the classic design problem with a string-parsing wrapper. You get a capacity, a list of "GET key" and "PUT key value" strings, and you return the GET results in order. No library LRU allowed. It's a hash map plus a doubly linked list, and every operation has to be O(1). If you've seen it before, it's twenty minutes. If you blank on pointer wiring, StealthCoder is the safety net running invisibly during the live OA.
The problem
Implement a least recently used cache with fixed positive capacity, then process the operations in operations. "PUT key value" inserts or updates a key. When a new key would exceed capacity, evict the least recently used key. "GET key" returns the stored value, or -1 when the key is absent. A successful GET and every PUT make that key the most recently used. A missing GET does not change recency. Return the results of all GET operations in their original order. Build the cache behavior directly; do not use a library-provided LRU cache. Interview follow-up The interviewer also asked for a generic implementation. Discuss an LRU cache parameterized by key and value types, including key equality and hashing, the map and linked-list invariants, and a typed absence result rather than the integer sentinel -1. The judged operation-sequence adapter remains integer-based. Function runLRU(capacity: int, operations: String[]) → int[] Examples Example 1 capacity = 2 operations = ["PUT 1 10","PUT 2 20","GET 1","PUT 3 30","GET 2","GET 3"] return = [10,-1,30] GET 1 makes key 1 recent, so inserting key 3 evicts key 2. Example 2 capacity = 1 operations = ["PUT 4 7","PUT 4 9","GET 4","PUT 5 5","GET 4"] return = [9,-1] Updating key 4 changes its value to 9. Inserting key 5 later evicts it because capacity is 1. Example 3 capacity = 2 operations = ["GET 7","PUT 0 0","GET 0"] return = [-1,0] The first lookup misses without changing the cache. Keys and values may be zero. Constraints 1 <= capacity <= 100000. 1 <= operations.length <= 200000. Every operation is exactly "GET key" or "PUT key value". -10^9 <= key, value <= 10^9.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is pairing a hash map with a doubly linked list. The map takes key to node in O(1). The list keeps recency order, with most recent at the head and least recent at the tail. Use dummy head and tail nodes so you never special-case empty or single-node lists. On GET hit, move the node to the front. On GET miss, return -1 and touch nothing. On PUT, update the value and move to front if the key exists. Otherwise insert at front, and if size exceeds capacity, remove the tail node and delete its key from the map. The pitfalls are skipping the recency bump on a PUT update, bumping on a missed GET, and forgetting to delete the evicted key from the map. Parse each operation by splitting on spaces, and keys and values can be negative or zero. If the pointer order trips you up mid-assessment, StealthCoder can hand you a clean implementation.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill LRU Cache cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as lru cache. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Navan's OA.
Navan reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
LRU Cache FAQ
How hard is the Navan LRU Cache question really?+
It's a known medium. The idea is simple, but the implementation has many small steps: map, linked list, eviction, parsing. Most failures come from pointer bugs, not from not knowing the approach. Write the helper methods first, remove node and add to front, and the rest falls into place.
What's the trick to getting O(1) for every operation?+
Use a hash map from key to list node, plus a doubly linked list ordered by recency. The map finds the node instantly, and the doubly linked list lets you unlink it without scanning. A singly linked list or an array makes moves O(n) and risks timeouts with 200000 operations.
Can I use LinkedHashMap or OrderedDict?+
No. The problem says to build the cache behavior directly and not use a library-provided LRU cache. Using one of those would likely break that rule. Write your own node class and the map-plus-list structure by hand.
What edge cases should I test before submitting?+
Test a PUT that updates an existing key at full capacity, which must not evict anything. Test a GET miss, which must not change order. Test capacity 1, and keys or values equal to 0 or negative. Example 2 and Example 3 in the statement cover most of these.
What about the generic follow-up with key and value types?+
Parameterize the node and cache by K and V. Keys need correct equality and hashing, since the map depends on them. Keep the same invariants: map size equals list size, and the tail is least recent. Return an optional or nullable type for a miss instead of -1.