LRU Cache with Expiring Entries
Updated
Problem statement
Process a sequence of operations on an initially empty least-recently-used cache with at most capacity live entries. Each entry has the same time-to-live duration ttl. Return the results of all get operations, in input order.
Each operation is a row [type, time, key, value], in nondecreasing time order. Process rows with equal times in their input order.
type = 0: put the key and value. An inserted or updated entry expires attime + ttland becomes most recently used.type = 1: get the key. Its value field is0and is ignored. Return the stored value if live and make it most recently used; otherwise return-1. A get does not extend expiry.
Before each operation at time t, remove every entry with expiry time less than or equal to t. If putting a new key would exceed capacity, evict the least recently used live entry. A failed get changes no recency. Expired entries never consume capacity.
The operations run one after another, and each row carries its own time. Handling many users at once is a discussion topic. It does not change the results you return.
Function
cacheResults(capacity: int, ttl: int, operations: int[][]) → int[]Examples
Example 1
capacity = 2ttl = 5operations = [[0,0,1,10],[0,1,2,20],[1,2,1,0],[0,3,3,30],[1,3,2,0],[1,5,1,0]]return = [10,-1,-1]Getting key 1 makes key 2 least recent, so inserting key 3 evicts key 2. Key 1 still expires at time 5 because get does not refresh TTL.
Example 2
capacity = 1ttl = 3operations = [[0,0,7,4],[0,2,7,9],[1,3,7,0],[1,5,7,0]]return = [9,-1]Updating key 7 resets expiry to time 5. Its older expiry at time 3 must not remove the refreshed entry.
Constraints
1 <= capacity <= 10^4.1 <= ttl <= 10^9.0 <= operations.length <= 10^5; every row has four integers.- There are at most
10^4get operations, so the returned array remains bounded. typeis0or1.0 <= time <= 10^9, with nondecreasing times.1 <= key <= 10^9and0 <= value <= 10^9. Get rows have value zero.
More Paytm interview questions
- Nth Highest SalaryPHONE SCREEN · Seen Nov 2026
- Second Highest SalaryPHONE SCREEN · Seen Nov 2026
- Jump GamePHONE SCREEN · Seen Nov 2026
- Detect a Linked-List CycleONSITE INTERVIEW · Seen Sep 2026
- Find First and Last Position in Sorted ArrayONSITE INTERVIEW · Seen Sep 2026
- Minimum Coins for a TargetONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- LRU Cache with TTLAutodesk · ONSITE INTERVIEWAutodesk interview questions
- Split Tender Part 4 - RefundsStripe · OA · PHONE SCREENStripe interview questions
- 15-Minute Chat Session TrackerOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Capacity-Limited Timed CacheNetflix · PHONE SCREENNetflix interview questions
- Tiered Expiring Item StoreHudson River Trading · PHONE SCREEN · ONSITE INTERVIEWHudson River Trading interview questions
- LFU CacheFreshworks · PHONE SCREENFreshworks interview questions
- Tiered Expiring Item StoreAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Multi-Level Inventory Storage SystemOptiver · OA · PHONE SCREENOptiver interview questions
- Limit Order Book Matching EngineCitadel · PHONE SCREENCitadel interview questions
- Document Enrichment Stream AggregatorBloomberg LP · PHONE SCREENBloomberg LP interview questions