FastPrepSingle-Flight Chunk Cache

Single-Flight Chunk Cache

Modal logoModal● HardFULLTIMEPHONE SCREEN
Learn

Problem statement

Simulate a byte-capacity cache for network image chunks. Process operations in order:

  • GET key size: return HIT key and refresh recency when cached; return WAIT key when the same key is already being fetched; otherwise start one fetch, remember its size, and return FETCH key.
  • DONE key: return IGNORED key when no fetch is active. Otherwise finish that fetch. If its size exceeds total capacity, do not cache it and return TOO_LARGE key. Otherwise evict least-recently-used cached chunks until it fits, cache it as most recent, and return STORED key. When eviction occurs append EVICT key1,key2 in eviction order.

Only completed chunks occupy cache capacity. An operation is the recency clock; lexicographically smaller keys break an otherwise impossible equal-clock tie.

Function

processChunkCache(capacity: int, operations: String[]) → String[]

Examples

Example 1

capacity = 10operations = ["GET a 6","GET a 6","DONE a","GET a 6"]return = ["FETCH a","WAIT a","STORED a","HIT a"]

The second miss waits for the active fetch, and the later request is a cache hit.

Example 2

capacity = 10operations = ["GET a 6","DONE a","GET b 7","DONE b"]return = ["FETCH a","STORED a","FETCH b","STORED b EVICT a"]

Storing b evicts least-recently-used a because both chunks do not fit.

Constraints

  • 0 <= capacity <= 1000000000
  • 1 <= operations.length <= 2000
  • Keys contain letters, digits, dash, or underscore and sizes are nonnegative integers.
See Modal hiring insights
public String[] processChunkCache(int capacity, String[] operations) {
  // Write your code here.
}
capacity10
operations["GET a 6","GET a 6","DONE a","GET a 6"]
expected["FETCH a", "WAIT a", "STORED a", "HIT a"]
Checking account…