FastPrepLRU Cache
Problem · Hash Table

LRU Cache

Learn this problem
● MediumIntuit logoIntuitINTERNONSITE INTERVIEW

Problem statement

Implement a least recently used cache with fixed positive capacity, then process the operations in operations.

  • "PUT key value" inserts or updates a key. When a new key would exceed capacity, evict the least recently used key.
  • "GET key" returns the stored value, or -1 when the key is absent.

A successful GET and every PUT make that key the most recently used. A missing GET does not change recency. Return the results of all GET operations in their original order.

Build the cache behavior directly; do not use a library-provided LRU cache.

Function

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

Examples

Example 1

capacity = 2operations = ["PUT 1 10","PUT 2 20","GET 1","PUT 3 30","GET 2","GET 3"]return = [10,-1,30]

GET 1 makes key 1 recent, so inserting key 3 evicts key 2.

Example 2

capacity = 1operations = ["PUT 4 7","PUT 4 9","GET 4","PUT 5 5","GET 4"]return = [9,-1]

Updating key 4 changes its value to 9. Inserting key 5 later evicts it because capacity is 1.

Example 3

capacity = 2operations = ["GET 7","PUT 0 0","GET 0"]return = [-1,0]

The first lookup misses without changing the cache. Keys and values may be zero.

Constraints

  • 1 <= capacity <= 100000.
  • 1 <= operations.length <= 200000.
  • Every operation is exactly "GET key" or "PUT key value".
  • -10^9 <= key, value <= 10^9.

More Intuit problems

drafts saved locally
public int[] runLRU(int capacity, String[] operations) {
    // Write your code here
}
capacity2
operations["PUT 1 10","PUT 2 20","GET 1","PUT 3 30","GET 2","GET 3"]
expected[10,-1,30]
checking account