Least Recently Used Cache
Reported by candidates from ByteDance's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
ByteDance reported this one in October 2026, and it's the classic LRU cache wrapped in a string-parsing function. The whole problem hinges on one data structure: a hash map paired with a doubly linked list, so GET and PUT both run in O(1). If you've got an OA invite for ByteDance, expect to write this cold. The logic is short but easy to fumble under a timer. StealthCoder is the safety net if your mind goes blank mid-assessment, but the pattern below should get you most of the way.
The problem
Process a sequence of operations on a least recently used cache with capacity capacity. PUT key value inserts or updates a key. A successful update makes that key the most recently used. If inserting a new key exceeds capacity, evict the least recently used key. GET key returns the stored value, or -1 when the key is absent. A successful lookup makes that key the most recently used; a missing lookup does not change recency. Return the results of the GET operations in their original order. Keys and values are decimal integers separated by one space in each operation string. 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] The lookup of key 1 makes key 2 least recently used, so inserting key 3 evicts key 2. Example 2 capacity = 1 operations = ["PUT 5 7","PUT 5 9","GET 5","PUT 6 4","GET 5"] return = [9,-1] Updating key 5 replaces its value without adding a second entry. Inserting key 6 later evicts it. Example 3 capacity = 3 operations = ["GET 8","PUT 8 0","GET 8"] return = [-1,0] The first lookup misses. After insertion, a stored value of 0 is returned normally. Constraints 1 <= capacity <= 10^5 1 <= operations.length <= 2 * 10^5 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 O(1) recency tracking. A hash map gives you key to node lookup. A doubly linked list keeps order, with the most recent at the head and the least recent at the tail. On a hit, move the node to the head. On PUT of an existing key, update the value and move it to the head. On PUT of a new key, insert at the head, and if size exceeds capacity, drop the tail and delete it from the map. Common pitfalls: a missed GET must not change recency, a stored value of 0 is valid (don't test truthiness), and you must parse each operation string by splitting on the space. Negative keys and values are allowed. Use dummy head and tail sentinels to kill the edge cases. If you blank on pointer wiring during the live OA, StealthCoder is the hedge that hands you the structure.
If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.
You can drill Least Recently Used 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. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken.
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 ByteDance's OA.
ByteDance reuses patterns across OAs. Built by an Amazon engineer who passed his OA cold and still thinks the filter is broken. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Least Recently Used Cache FAQ
What's the trick in the ByteDance LRU cache problem?+
Combine a hash map with a doubly linked list. The map finds a node in O(1), and the list reorders it in O(1). Head is most recent, tail is least recent. Evict from the tail when a new key pushes size past capacity.
Can I use a built-in ordered map instead?+
Often yes. An ordered dictionary or LinkedHashMap does the same job in a few lines. But the OA may expect you to know the underlying structure, so be ready to write the manual version. Check what the language gives you and decide before the timer starts.
What edge cases break most solutions?+
A GET miss that wrongly alters recency, treating a stored 0 as absent, and PUT on an existing key that adds a duplicate instead of updating. Example 2 and Example 3 in the problem target exactly these. Capacity 1 is also a nasty small case.
How should I parse the operations?+
Split each string on the single space. The first token is GET or PUT, then parse the integers. Keys and values can be negative, up to 10^9 in magnitude, so integers are fine in most languages. Collect only GET results into the output array in order.
How do I prepare for this in 48 hours?+
Write the LRU cache from scratch twice, once with sentinel nodes and once with your language's ordered map. Then run the three examples from the problem by hand. With 2 * 10^5 operations, anything slower than O(1) per operation is a risk.