Rank-Based Cache with a Data Source
LinkedIn● MediumFULLTIMEPHONE SCREENProblem statement
Implement a fixed-capacity cache backed by a data source. Each input row [key, value, rank] supplies one immutable data-source record. All keys are unique, every requested key exists in the data source, and values and ranks remain fixed during this batch. The cache begins empty.
Process the requested keys in order. For each get(key):
- If the key is cached, return its cached value without reading the data source.
- Otherwise read its record from the data source and increase the cumulative data-source read count by one.
- If capacity is positive, store the missed record. When already full, first evict the existing cached record with the smallest rank, breaking ties by the smallest key. Then insert the newly fetched record, even if its rank is lower than the evicted rank.
- Capacity zero stores no records.
The finite practice adapter returns one string "value backendReads" per request. Its first number is the value returned by get; its second is a cumulative read counter starting at zero for this cache instance, included to make hits and eviction behavior observable.
Each get is atomic in the supplied order, which represents one legal linearization of concurrent calls. In a shared concurrent class, protect the complete hit-or-fetch, counter update, eviction and insertion as one operation. Cache hits do not change ranks or eviction order.
Function
runRankCache(capacity: int, records: int[][], requests: int[]) → String[]Examples
Example 1
capacity = 2records = [[1,10,5],[2,20,2],[3,30,9]]requests = [1,2,1,3,2]return = ["10 1","20 2","10 2","30 3","20 4"]The second number is the cumulative number of data-source reads. Hits return the cached value without increasing it; misses read and then store when capacity permits.
Example 2
capacity = 1records = [[1,7,100],[2,8,1]]requests = [1,2,1]return = ["7 1","8 2","7 3"]The second number is the cumulative number of data-source reads. Hits return the cached value without increasing it; misses read and then store when capacity permits.
Example 3
capacity = 0records = [[5,9,4]]requests = [5,5]return = ["9 1","9 2"]The second number is the cumulative number of data-source reads. Hits return the cached value without increasing it; misses read and then store when capacity permits.
Constraints
0 <= capacity <= 100000.0 <= records.length, requests.length <= 100000.- Every record has exactly three integers, keys are unique, and every request names a supplied key.
-10^9 <= key, value, rank <= 10^9.- The data source always succeeds, and its values and ranks are immutable for this batch.