How should I practice LRU Cache?

Start by reading the full statement, solve the visible examples, then compare the pattern against related BNSF Railway phone screen problems in FastPrep.

Is LRU Cache associated with BNSF Railway?

FastPrep tags this as a BNSF Railway phone screen coding practice problem when the problem catalog has that company and stage context.

LRU Cache

BNSF Railway● MediumFULLTIMEPHONE SCREEN

Problem statement

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.

Function

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

Examples

Example 1

capacity = 2operations = ["PUT 4 40","PUT 7 70","GET 4","PUT 9 90","GET 7","GET 9","GET 4"]return = [40,-1,90,40]

After the two puts the cache holds keys 4 and 7. GET 4 returns 40 and makes key 4 the most recent, so PUT 9 90 evicts key 7. Then GET 7 returns -1, GET 9 returns 90 and GET 4 returns 40.

Example 2

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

PUT 1 8 changes key 1 to 8 and makes it the most recent, without evicting anything. When PUT 3 9 needs room, key 2 is the least recently used, so it is removed. The gets return 8, -1 and 9.

Example 3

capacity = 1operations = ["GET 5","PUT 5 50","PUT 6 60","GET 5","GET 6"]return = [-1,-1,60]

The first get misses and returns -1. With capacity 1, putting key 6 evicts key 5. So GET 5 returns -1 and GET 6 returns 60.

Constraints

1 <= capacity <= 1000
1 <= operations.length <= 2000
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.