FastPrepCache an Expensive Service Across Threads

Cache an Expensive Service Across Threads

Oracle logoOracle● EasyFULLTIMEONSITE INTERVIEW

Problem statement

A service is very expensive to call. For the same key it always returns the same value, but every call takes latency time units. To make it cheaper, put a read-through cache in front of it. Many threads use the cache at the same time, so the cache must stay correct when several threads ask for the same key.

Requests are given as requests[i] = [time, key]: some thread asks the cache for key at time time. Requests are listed in non-decreasing order of time. Requests with the same time are handled in the order they appear in requests.

The cache handles each request with these rules:

  • Hit: if a service call for key has already finished at or before time, the value is stored, and the request returns at time.
  • Shared call: if a service call for key has started but finishes after time, the request does not call the service again. It waits for that call and returns when the call finishes.
  • Miss: otherwise, the cache calls the service at time. The call finishes at time + latency, the value is stored at that moment, and the request returns at that moment.

Stored values never expire, and the cache has no size limit. So the service is called at most once for each distinct key.

Return an integer array answer where answer[i] is the time when request i returns.

Function

cachedResponseTimes(latency: int, requests: int[][]) → int[]

Examples

Example 1

latency = 5requests = [[0,7],[2,7],[5,7],[6,3]]return = [5,5,5,11]

The service is called only once, for key 7, and later once for key 3.

  • At time 0, key 7 is not cached, so the cache calls the service. The call finishes at 0 + 5 = 5.
  • At time 2, the call for key 7 is still running, so this request waits and returns at 5.
  • At time 5, the call for key 7 has just finished, so this is a hit and returns at 5.
  • At time 6, key 3 is new, so the cache calls the service. The call finishes at 6 + 5 = 11.

Example 2

latency = 3requests = [[1,1],[1,2],[1,1],[4,2],[10,1]]return = [4,4,4,4,10]
  • At time 1, keys 1 and 2 are both new, so each starts a call that finishes at 4.
  • The third request also asks for key 1 at time 1. It is handled after the first request, so it shares that call and returns at 4.
  • At time 4, key 2 is already stored, so the request returns at 4.
  • At time 10, key 1 is stored, so the request returns at 10.

The service is called twice in total.

Example 3

latency = 1000000requests = [[0,42]]return = [1000000]

There is only one request, so it is a miss and returns at 0 + 1000000 = 1000000.

Constraints

  • 1 <= latency <= 10^6
  • 1 <= requests.length <= 10^5
  • requests[i].length == 2
  • 0 <= time, key <= 10^9 for every requests[i] = [time, key]
  • The time values in requests are in non-decreasing order.

More Oracle problems

See Oracle hiring insights
Saved
public int[] cachedResponseTimes(int latency, int[][] requests) {
    // write your code here
}
latency5
requests[[0,7],[2,7],[5,7],[6,3]]
expected[5,5,5,11]
Checking account…