LRU cache: evict the least recently used entry
Coding problemHardAsked in: Adobe, Amazon, Flipkart, Goldman Sachs, Google, Microsoft
Build a cache (a small store that keeps recently used data for fast access) that holds at most capacity keys, each with a value, and runs every command in constant time on average. This is called an LRU cache: LRU means least recently used, the key that is removed (evicted) first when the cache is full. Your function receives the capacity and a list of commands, and runs them in order on an empty cache:
"get k"outputs the value stored for key k, or -1 if k is not in the cache. Reading a key counts as using it."put k v"stores value v for key k (replacing any old value), which also counts as using k. If this adds a new key and the cache now holds more thancapacitykeys, remove the key that was used least recently.
Return the outputs of all "get" commands, in order.
Examples
Example 1
Input: capacity = 2, commands = ["put 1 1","put 2 2","get 1","put 3 3","get 2","put 4 4","get 1","get 3","get 4"]
Output: [1,-1,-1,3,4]
Reading key 1 makes key 2 the least recently used, so key 3 pushes out key 2. Then key 4 pushes out key 1.
Example 2
Input: capacity = 1, commands = ["put 7 70","put 8 80","get 7","get 8"]
Output: [-1,80]
Example 3
Input: capacity = 2, commands = ["put 1 1","put 1 5","get 1"]
Output: [5]
Constraints
- 1 <= capacity <= 100,000
- Between 1 and 100,000 commands
- Keys are between 0 and 100,000; values between 0 and 1,000,000,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.