FastPrep
Problem · Design

LRU Cache Operations

Learn this problem
● MediumDigitalOcean logoDigitalOceanFULLTIMEONSITE INTERVIEW

Problem statement

Process a sequence of operations on a least recently used (LRU) cache with a fixed positive capacity.

The cache starts empty. The parallel arrays operations and arguments describe the calls in order:

  • get has arguments [key]. Return the stored value, or -1 when the key is absent. A successful get makes that key the most recently used.
  • put has arguments [key, value]. Insert or update the key and make it the most recently used. If inserting a new key would exceed capacity, first evict the least recently used key.

Return an array containing the results of the get operations, in operation order. A put operation produces no result.

Function

runLruCache(capacity: int, operations: String[], arguments: int[][]) → int[]

Examples

Example 1

capacity = 2operations = ["put","put","get","put","get","get"]arguments = [[1,1],[2,2],[1],[3,3],[2],[3]]return = [1,-1,3]

Reading key 1 makes it most recent. Inserting key 3 then evicts key 2, so the final two reads return -1 and 3.

Example 2

capacity = 1operations = ["put","put","get","put","get"]arguments = [[5,10],[5,20],[5],[6,30],[5]]return = [20,-1]

Updating key 5 changes its value without increasing the cache size. Inserting key 6 later evicts key 5 because the capacity is 1.

Constraints

  • 1 <= capacity <= 10^5
  • 1 <= operations.length <= 2 * 10^5
  • operations.length == arguments.length
  • Each operation is exactly get or put.
  • A get row contains exactly one integer, and a put row contains exactly two integers.
  • 0 <= key <= 10^9
  • 0 <= value <= 10^9
drafts saved locally
public int[] runLruCache(int capacity, String[] operations, int[][] arguments) {
    // write your code here
}
capacity2
operations["put","put","get","put","get","get"]
arguments[[1,1],[2,2],[1],[3,3],[2],[3]]
expected[1,-1,3]
checking account