LRU Cache Operation Sequence
Google● MediumFULLTIMEINTERNONSITE INTERVIEWProblem statement
Process an operation sequence on a least-recently-used (LRU) cache with the given capacity. Each operation is an integer array. [1, key, value] means put: insert or replace that key and mark it most recently used. [0, key] means get: return its value if present and mark it most recently used; otherwise return -1 without changing recency.
When inserting a new key would exceed capacity, first evict the least recently used existing key. Replacing an existing key never evicts another key. When capacity is zero, puts store nothing and every get returns -1. Only gets produce outputs. Return their results in operation order.
Examples
Example 1
capacity = 2operations = [[1,1,10],[1,2,20],[0,1],[1,3,30],[0,2],[0,1],[0,3]]return = [10,-1,10,30]Getting key 1 makes it newest, so inserting key 3 evicts key 2. The later gets return the remaining values.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 3 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.