How should I practice Capacity-Limited Timed Cache?

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

Is Capacity-Limited Timed Cache associated with Netflix?

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

Problem · Hash Table

Capacity-Limited Timed Cache

Learn this problem

● Hard

NetflixFULLTIMEPHONE SCREEN

Problem statement

Implement a key-value cache with a fixed positive capacity. Every entry has its own expiration time, and the cache processes operations whose timestamps are nondecreasing.

Each row in operations has one of these forms:

[0, key, value, ttl, timestamp] is a PUT. It creates or replaces key with value. The entry expires at timestamp + ttl. A successful PUT sets the entry's age to this timestamp.
[1, key, timestamp] is a GET. It returns the current value for key, or -1 when the key is absent or expired. A GET does not change an entry's age.

Before processing every operation, remove all entries whose expiration time is less than or equal to the operation's timestamp. When a PUT inserts a new key and the cache still contains capacity live entries, evict the live entry with the smallest most-recent PUT timestamp. If several live entries have that same timestamp, evict the one with the smaller key. Replacing an existing live key refreshes its value, expiration time, and age without evicting another entry.

Return the results of the GET operations in encounter order. PUT operations do not add a result.

Function

runCapacityTimedCache(capacity: int, operations: int[][]) → int[]

Examples

Example 1

capacity = 2operations = [[0,1,10,10,0],[0,2,20,10,1],[1,1,2],[0,3,30,10,3],[1,1,3],[1,2,3],[1,3,3]]return = [10,-1,20,30]

The cache is full when key 3 is inserted at time 3. Key 1 has the oldest live PUT timestamp, so it is evicted. Keys 2 and 3 remain available.

Example 2

capacity = 2operations = [[0,1,10,2,0],[0,2,20,10,0],[0,3,30,10,2],[1,1,2],[1,2,2],[1,3,2]]return = [-1,20,30]

Key 1 expires exactly at time 2 and is removed before key 3 is inserted. The expired entry frees capacity, so no live key is evicted.

Example 3

capacity = 2operations = [[0,2,20,10,0],[0,1,10,10,0],[0,3,30,10,0],[1,1,0],[1,2,0],[1,3,0]]return = [-1,20,30]

Keys 1 and 2 have equal age when key 3 arrives. The smaller key, 1, is evicted by the tie rule.

Constraints

1 <= capacity <= 100000.
1 <= operations.length <= 200000, and at least one operation is a GET.
Every PUT row is [0, key, value, ttl, timestamp].
Every GET row is [1, key, timestamp].
0 <= key, value, timestamp <= 10^9.
1 <= ttl <= 10^9.
Operation timestamps are nondecreasing.
Expiration times fit a signed 64-bit integer.