How should I practice Least Recently Used Cache?

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

Is Least Recently Used Cache associated with Illumio?

FastPrep tags this as a Illumio 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

IllumioFULLTIMEPHONE SCREEN

Problem statement

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

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

Return the integer results of the GET operations in encounter order. A PUT operation produces no result. Every operation uses 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]

Reading key 1 makes it the most recently used entry, 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 increasing the cache size. 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 the insertion, the stored value 0 is returned normally.

Constraints

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