Blocking Keyed Cache with Waiting Readers
Reported by candidates from Databricks's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The Databricks OA reported in July 2026 hands you a blocking keyed cache. A GET on a missing key parks a request, and a later PUT releases everything waiting on that key, in order. It looks like a design question, but it's really a hash map plus a queue per key and a careful read of the rules. If you're taking it in a day or two, the shape is simple. The risk is small ordering mistakes under pressure. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment, but this one is very learnable.
The problem
Simulate a blocking keyed cache by processing a finite ordered array operations. Each operation is one of: GET requestId key: if key is cached, complete immediately with the current value. Otherwise register this unique request as blocked. PUT key value: store or replace the value, then complete every request currently blocked on that key in registration order. Every released request observes the value supplied by this PUT. Operations are issued without waiting for earlier blocked requests. Return completion pairs [requestId, value] in the order completions occur. A request still blocked after the last operation produces no completion. Keys and values are non-empty case-sensitive strings without spaces. Function runBlockingCache(operations: String[]) → String[][] Examples Example 1 operations = ["GET 1 a","GET 2 a","PUT a red","GET 3 a"] return = [["1","red"],["2","red"],["3","red"]] The PUT releases both blocked readers in registration order. The final GET then completes immediately. Example 2 operations = ["PUT x one","GET 7 x","PUT x two","GET 8 x","GET 9 y"] return = [["7","one"],["8","two"]] Later reads observe replacements immediately. Request 9 remains blocked because no value for y is written. Constraints 1 <= operations.length <= 2 * 10^5 Every operation is a well-formed GET or PUT. Every requestId is a unique positive integer represented in decimal. Keys and values are non-empty case-sensitive strings without spaces. The total number of input characters is at most 2 * 10^5.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is two hash maps. One maps key to its current value. The other maps key to a list of blocked request IDs in arrival order. On GET, if the key exists in the value map, append [id, value] to the output now. Otherwise push the id onto that key's waiting list. On PUT, overwrite the value, then drain the waiting list in order, emit [id, newValue] for each, and clear it. Common pitfalls: emitting released requests with a stale value, forgetting that a PUT only releases requests blocked at that moment, and splitting on spaces wrongly. Keys and values have no spaces, so a plain split works. Everything is O(1) amortized per operation, since each request is released at most once. That fits 2 * 10^5 operations easily. If the logic slips live, StealthCoder is the hedge, but the whole solution is about twenty lines.
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 Blocking Keyed Cache with Waiting Readers 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
You've seen the question.
Make sure you actually pass Databricks's OA.
Databricks 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.
Blocking Keyed Cache with Waiting Readers FAQ
How hard is the Databricks blocking cache problem really?+
Easy to medium. There's no clever algorithm, just two hash maps and a queue per key. The difficulty is getting the ordering rules right: immediate GET completions, then released waiters in registration order. Candidates who code it cleanly in one pass usually finish fast.
What's the core trick?+
Keep a value map and a waiting-list map keyed by cache key. A GET either completes now or joins the list. A PUT overwrites the value, then flushes that key's list in order using the new value. Clear the list afterward so nobody is released twice.
What mistakes break the solution?+
Releasing waiters with an old value, flushing in the wrong order, or leaving requests in the list after a PUT. Another one is treating blocked requests as holding the old value on replacement. Requests blocked after the last operation must produce nothing, so don't add placeholders.
What's the time complexity I should state?+
O(n) overall in the number of operations, plus parsing cost bounded by the total input characters. Each request is added to a waiting list at most once and removed at most once, so the flush work amortizes to constant per operation.
How do I prepare in 48 hours?+
Write this exact simulation once from scratch, then run both examples by hand. Practice parsing operation strings, a map of lists, and building a list of string pairs for output. Test edge cases: PUT before any GET, repeated PUTs on one key, and a key that never gets written.