How should I practice LRU Cache with Expiring Entries?

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

Is LRU Cache with Expiring Entries associated with Paytm?

FastPrep tags this as a Paytm phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Hash Table

LRU Cache with Expiring Entries

Learn this problem

● Hard

PaytmFULLTIMEPHONE SCREEN

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.

For this exercise, operations are rows [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 at time + ttl and becomes most recently used.
type = 1: get the key. Its value field is 0 and 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.

This judged exercise uses a sequential batch with an explicit clock. Concurrent access is a discussion extension, separate from the returned batch results.

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^4 get operations, so the returned array remains bounded.
type is 0 or 1.
0 <= time <= 10^9, with nondecreasing times.
1 <= key <= 10^9 and 0 <= value <= 10^9. Get rows have value zero.