FastPrepBlocking Keyed Cache with Waiting Readers
Problems/Blocking Keyed Cache with Waiting Readers

Blocking Keyed Cache with Waiting Readers

Databricks logoDatabricks● MediumFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report specifies a blocking cache, rejects busy waiting, and says all waiters are signaled, but omits the blocking condition and runnable contract. The judged core task matches the visible source at about 86%.

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.

More Databricks problems

  • Rolling Hit CounterPHONE SCREEN · Seen Nov 2026
  • Minimize CommuteOA · PHONE SCREEN · Seen Oct 2026
  • Path Between Two Nodes of a Fibonacci TreeONSITE INTERVIEW · Seen Oct 2026
All Databricks interview questionsSee Databricks hiring insights
Saved
class Solution {
    public String[][] runBlockingCache(String[] operations) {
        // Write your code here.
    }
}
Checking account…