How should I practice Least Recently Used Cache?

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

Is Least Recently Used Cache associated with ByteDance?

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

Problem · Hash Table

Least Recently Used Cache

Learn this problem

● Medium

ByteDanceFULLTIMEPHONE SCREEN

Problem statement

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

PUT key value inserts or updates a key. A successful update makes that key the most recently used. If inserting a new key exceeds capacity, evict the least recently used key.
GET key returns the stored value, or -1 when the key is absent. A successful lookup makes that key the most recently used; a missing lookup does not change recency.

Return the results of the GET operations in their original order. Keys and values are decimal integers separated by one space in each operation string.

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