How should I practice LRU Cache?

Start by reading the full statement, solve the visible examples, then compare the pattern against related JP Morgan Chase onsite interview problems in FastPrep.

Is LRU Cache associated with JP Morgan Chase?

FastPrep tags this as a JP Morgan Chase onsite interview coding practice problem when the problem catalog has that company and stage context.

LRU Cache

JP Morgan Chase● MediumFULLTIMEONSITE INTERVIEW

Problem statement

Source note: This was the coding round of a JPMorgan Chase senior software engineer interview. The report names the classic LRU cache exercise, with an LFU version as the follow-up question, which is practiced as a separate FastPrep problem. Its tips are to know the data structures behind each cache, a hash map with a doubly linked list here, and to keep reads and writes at constant time. It gives no operation format, capacity or limits.

Practice choices: operations come as PUT and GET strings, and the answer is the list of GET results in order; a GET that finds its key returns the value and makes that key the most recent; a GET on a missing key returns -1 and changes nothing; every PUT makes its key the most recent, and updating a stored key evicts nothing; the limits; and the examples, which are ours. The tests check results only, not running time.

The judged task matches the report at about 85%.

Build a least recently used (LRU) cache that holds at most capacity keys, then run the operations in operations in order.

"PUT key value" stores value under key. If the key is already stored, its value is replaced and nothing is evicted. If the key is new and the cache already holds capacity keys, first remove the least recently used key.
"GET key" returns the stored value, or -1 if the key is not in the cache.
A PUT and a GET that finds its key both make that key the most recently used. A GET that misses changes nothing.

Return the results of all GET operations, in order.

Aim for O(1) average time for each operation. The judge checks only the returned results, not the running time.

Function

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

Examples

Example 1

capacity = 3operations = ["PUT 5 1","PUT 6 2","PUT 7 3","GET 5","PUT 8 4","GET 6","GET 7","GET 8","GET 5"]return = [1,-1,3,4,1]

The cache fills with keys 5, 6 and 7. GET 5 returns 1 and makes key 5 the most recent, so key 6 is now the least recently used and PUT 8 4 evicts it. The remaining gets return -1, 3, 4 and 1.

Example 2

capacity = 2operations = ["PUT 3 30","PUT 4 40","PUT 3 33","PUT 9 90","GET 4","GET 3","GET 9"]return = [-1,33,90]

PUT 3 33 replaces the value of key 3 and makes it the most recent, without evicting anything. When PUT 9 90 needs room, key 4 is the least recently used, so it is removed. The gets return -1, 33 and 90.

Example 3

capacity = 1operations = ["PUT 2 7","GET 3","GET 2","PUT 4 8","GET 2","GET 4"]return = [-1,7,-1,8]

GET 3 misses and returns -1 without changing anything. With capacity 1, PUT 4 8 evicts key 2, so the later GET 2 returns -1 and GET 4 returns 8.

Constraints

1 <= capacity <= 3000
1 <= operations.length <= 10^4
Each operation is "PUT key value" or "GET key", with single spaces and no leading zeros.
0 <= key <= 10^4 and 0 <= value <= 10^5
At least one operation is a GET.