LRU Cache
Updated
Problem statement
Process a least recently used cache with a fixed positive capacity.
[0, key, value]inserts or replaces a value and makes that key the most recently used. If a new key exceeds capacity, evict the least recently used key.[1, key]returns the stored value and makes that key the most recently used, or returns -1 if it is missing. A missed get does not change recency.
Return get results in operation order. Aim for O(1) average time per call.
Function
lruCache(capacity: int, operations: int[][]) → int[]Examples
Example 1
capacity = 2operations = [[0,1,10],[0,2,20],[1,1],[0,3,30],[1,2],[1,3]]return = [10,-1,30]Reading key 1 makes it recent. Inserting key 3 evicts key 2, so the gets return [10,-1,30].
Example 2
capacity = 1operations = [[0,7,-1],[1,7],[0,7,5],[1,7],[0,8,6],[1,7]]return = [-1,5,-1]Updating key 7 replaces its value. Inserting key 8 then evicts key 7. The gets return [-1,5,-1].
Constraints
- 1 <= capacity <= 1000
- 1 <= operations.length <= 100000
- Each operation is [0, key, value] for put, or [1, key] for get.
- 0 <= key <= 1000000 and -1 <= value <= 1000000
More Citadel Phone Screen questions
- Portfolio Tickers with Constant-Time Random PickPHONE SCREEN · Seen Nov 2026
- Square Root FunctionPHONE SCREEN · Seen Oct 2026
- Reachable Transfer PositionsPHONE SCREEN · Seen Oct 2026
- Spreadsheet Formula DependenciesPHONE SCREEN · Seen Oct 2026
- Merge Price-Delta FeedsPHONE SCREEN · Seen Sep 2026
- Reconcile Unmatched Trades with Timestamp TolerancePHONE SCREEN · Seen Sep 2026
- Top Ten Trades by Notional ValuePHONE SCREEN · Seen Sep 2026
- Exchange BBO and Market-Wide NBBOPHONE SCREEN · Seen Sep 2026
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- LRU Cache for Query ResultsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- LRU CacheGimlet Labs · PHONE SCREEN
- LRU CacheBNSF Railway · PHONE SCREENBNSF Railway interview questions
- Max Frequency TrackerProcol · PHONE SCREEN
- Balanced Session ManagerPalantir · PHONE SCREENPalantir interview questions
- LRU Cache Operation SequenceCARS24 · PHONE SCREEN
- LRU Key-Value Cache OperationsCohesity · PHONE SCREEN
- Least Recently Used CacheMicrosoft · OA · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- LRU CacheApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
- Least Recently Used CacheByteDance · PHONE SCREEN · ONSITE INTERVIEWByteDance interview questions