LRU Cache with TTL
Updated
Problem statement
Process a linearized history for a least-recently-used cache with a fixed positive capacity and per-entry time-to-live values.
SET key value ttl timestampinserts or replaces an entry, makes it most recently used, and returnsOK. The entry expires attimestamp + ttl.GET key timestampreturns the stored integer as text and makes the entry most recently used, or returnsMISS.DELETE key timestampremoves a live entry and returnsDELETED, or returnsMISS.
An entry is expired when the operation timestamp is greater than or equal to its expiration time. Remove expired entries before each operation. When a set leaves too many live entries, evict the least recently used one. Return one result string per command.
Function
runLruCache(capacity: int, commands: String[]) → String[]Examples
Example 1
capacity = 2commands = ["SET a 1 5 0","SET b 2 10 1","GET a 2","SET c 3 10 3","GET b 4","GET a 5","DELETE c 6","GET c 7"]return = ["OK","OK","1","OK","MISS","MISS","DELETED","MISS"]The access to a makes it newer than b, so setting c evicts b. Entry a expires exactly at timestamp 5.
Example 2
capacity = 1commands = ["SET x 4 3 0","GET x 2","GET x 3"]return = ["OK","4","MISS"]The entry is live before timestamp 3 and expired at timestamp 3.
Constraints
capacityis between 1 and 1000.- The command list contains between 1 and 2000 rows.
- Each command contains between 5 and 100 characters.
- Commands use
SET key value ttl timestamp,GET key timestamp, orDELETE key timestamp; keys contain no spaces, values are integers that fit in signed 64-bit integers, TTL values are between 1 and 1012, timestamps are between 0 and 1012 and are nondecreasing, and every expiration timestamp is at most 2 × 1012.
Source note: Author-written prompt excerpt retained for source fidelity.
More Autodesk interview questions
Similar questions at other companies
- LFU CacheAmazon · ONSITE INTERVIEW
- LFU CacheSnowflake · OA · ONSITE INTERVIEWSnowflake interview questions
- 15-Minute Chat Session TrackerOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Recover a Function-Call LRU Cache with a Write-Ahead LogAnthropic · ONSITE INTERVIEWAnthropic interview questions
- LFU CacheSalesforce · ONSITE INTERVIEWSalesforce interview questions
- Tiered Expiring Item StoreHudson River Trading · PHONE SCREEN · ONSITE INTERVIEWHudson River Trading interview questions
- LFU CacheBlinkit · ONSITE INTERVIEWBlinkit interview questions
- Thread-Safe LRU Cache with TTLLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Fair Multi-Tenant CacheOkta · ONSITE INTERVIEWOkta interview questions
- LFU CacheZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions