FastPrep
Problem · Hash Table

Blocking Keyed Cache with Waiting Readers

Learn this problem
● MediumDatabricks logoDatabricksFULLTIMEONSITE INTERVIEW

Problem statement

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

drafts saved locally
public String[][] runBlockingCache(String[] operations) {
    // Write your code here.
}
operations["GET 1 a","GET 2 a","PUT a red","GET 3 a"]
expected[["1", "red", "2", "red", "3", "red"]]
checking account