Key-Value Store with Hit Counter
Reported by candidates from Databricks's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Databricks reported this one in July 2026, and the input size is the first thing to read. Up to 5000 operations sounds small, but a COUNT_HITS that rescans every hit for a key, on every call, turns into a quadratic mess fast. The problem is a key-value store with a per-key hit log, and it's mostly a design and hash-table question with a binary search on top. If you blank on how to count hits in a half-open interval, StealthCoder is the safety net running invisibly during the live OA. Know the shape before you sit down.
The problem
Process an ordered batch of operations on a string key-value store. The store also records every GET as a hit for the requested key, including a request for a missing key. Operations PUT|timestamp|key|value: set or overwrite key with value. Return OK. GET|timestamp|key: record one hit for key, then return VALUE:value when the key exists or NULL when it does not. COUNT_HITS|timestamp|key|start|end: return the number of recorded hits for key whose timestamps are in the half-open interval [start, end). Operation timestamps are nondecreasing. Operations that share a timestamp are processed in input order. Return one result string for every operation, in the same order. Function runStore(operations: String[]) → String[] Examples Example 1 operations = ["PUT|1|a|red","GET|2|a","GET|3|missing","COUNT_HITS|4|a|0|4","COUNT_HITS|5|missing|3|4","PUT|6|a|blue","GET|7|a","COUNT_HITS|8|a|2|8"] return = ["OK","VALUE:red","NULL","1","1","OK","VALUE:blue","2"] The first count includes the hit on a at time 2. The missing lookup at time 3 is also recorded. After the overwrite, the lookup at time 7 returns blue, while the hit history for a contains both times 2 and 7. Example 2 operations = ["GET|1|x","PUT|1|x|one","GET|1|x","COUNT_HITS|1|x|0|1","COUNT_HITS|2|x|1|2"] return = ["NULL","OK","VALUE:one","0","2"] Both lookups at time 1 count as hits. The half-open interval [0, 1) excludes them, while [1, 2) includes both. Input order determines that the second lookup sees the newly stored value. Constraints 1 <= operations.length <= 5000 Every operation uses one of the documented formats and contains no | inside a key or value. Timestamps are integers in [0, 10^9] and are nondecreasing across the input. Keys and values are non-empty lowercase English strings of length at most 30. For every count operation, 0 <= start <= end <= timestamp + 1.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Keep two hash maps. One maps key to current value. The other maps key to a list of hit timestamps. PUT overwrites the value. GET appends the timestamp to that key's list first, even if the key is missing, then returns VALUE:x or NULL. Timestamps are nondecreasing, so every hit list is already sorted. COUNT_HITS is then two binary searches: lower bound of end minus lower bound of start, which gives the half-open [start, end) count. The pitfalls are small but costly. Don't skip recording hits for missing keys. Don't use upper bound for end, because end is exclusive. Don't lose input order at equal timestamps, as Example 2 shows. Return counts as strings. If the binary search details slip under pressure, StealthCoder can supply the bound logic live without the proctor seeing it.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Key-Value Store with Hit Counter 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 for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Databricks's OA.
Databricks reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Key-Value Store with Hit Counter FAQ
What's the trick in the Databricks key-value store with hit counter problem?+
Store hits separately from values. A per-key list of timestamps stays sorted because timestamps never decrease. COUNT_HITS becomes two lower-bound binary searches, end minus start. The value map only matters for what GET returns.
Do GETs on missing keys really count as hits?+
Yes. The statement says every GET is recorded, including missing keys. Example 1 shows it: the missing lookup at time 3 gives a count of 1 for [3, 4). Record the hit before you decide between VALUE and NULL.
How do I handle the half-open interval correctly?+
Count timestamps t where start <= t < end. With a sorted list, that's lowerBound(end) minus lowerBound(start). Using upper bound on end would wrongly include hits exactly at end. Test against Example 2, where [0,1) gives 0 and [1,2) gives 2.
Is a linear scan good enough with 5000 operations?+
It would likely pass at this size, since worst case is around 25 million steps. But binary search is barely more code and is safer. It also shows the sorted-timestamp insight, which is what the problem is really testing.
How do I prepare for this in 48 hours?+
Write it once from scratch. Two hash maps, a manual or library lower bound, and string parsing split on the pipe character. Run both examples by hand. Watch for same-timestamp ordering and for returning counts as strings, not integers.