How should I practice Least Recently Used Cache?

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

Is Least Recently Used Cache associated with Microsoft?

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

Problem · Hash Table

Least Recently Used Cache

Learn this problem

● Medium

MicrosoftNEW GRADONSITE INTERVIEW

See Microsoft hiring insights

Problem statement

Process a sequence of operations on a least recently used cache with capacity capacity.

PUT key value inserts or updates a key. An update makes the key most recently used. If a new insertion exceeds capacity, evict the least recently used key.
GET key returns the value, or -1 when absent. A hit makes the key most recently used; a miss does not change recency.

Return all GET results in operation order. Operation fields are decimal integers separated by one space.

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]

The lookup of key 1 makes key 2 least recently used, so inserting key 3 evicts key 2.

Example 2

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

Updating key 5 replaces its value without adding a second entry. Inserting key 6 later evicts it.

Example 3

capacity = 3operations = ["GET 8","PUT 8 0","GET 8"]return = [-1,0]

The first lookup misses. After insertion, a stored value of 0 is returned normally.

Constraints

1 <= capacity <= 10^5
1 <= operations.length <= 2 * 10^5
Every operation is exactly GET key or PUT key value.
-10^9 <= key, value <= 10^9