Problem Brief

LRU Cache with TTL Expiration

FULLTIMEONSITE INTERVIEW

See Tiktok online assessment and hiring insights

Implement a fixed-capacity LRU cache that also supports per-entry TTL expiration.

You are given the cache capacity, an array of operation names, and a parallel array of integer arguments. Process the operations in order and return one output string for each get operation.

Each operation has a timestamp as its first argument. Timestamps are non-decreasing.

put has arguments [time, key, value, ttl]. It inserts or updates key with value. The key expires at absolute time time + ttl. Updating an existing key replaces both its value and expiration time. A successful put makes the key most recently used.

get has arguments [time, key]. If the key exists and has not expired, return its value as a string and make the key most recently used. Otherwise, return "-1".

Before processing each operation, remove every expired key. A key is expired when current time >= expiration time.

If a put causes the cache to exceed capacity after expired keys have been removed, evict the least recently used remaining key.

Function Description

Complete solveLRUCacheTTL. It has the following parameters:

int capacity: the maximum number of live keys in the cache

String[] operations: each value is either "put" or "get"

int[][] arguments: arguments for each operation, using the formats above

Return a String[] containing the outputs of all get operations in order.

1Example 1

Input

capacity = 2, operations = ["put","put","get","put","get","get","get"], arguments = [[0,1,10,5],[1,2,20,10],[2,1],[6,3,30,5],[6,1],[7,2],[12,3]]

Output

["10","-1","20","-1"]

Explanation

Key 1 expires at time 5, so it is gone before the operation at time 6. Keys 2 and 3 expire at time 11, so the final get at time 12 misses.

2Example 2

Input

capacity = 1, operations = ["put","put","get","put","get"], arguments = [[0,5,7,3],[2,5,9,10],[4,5],[5,6,1,10],[6,5]]

Output

["9","-1"]

Explanation

The second put updates key 5 and extends its expiration. Later, inserting key 6 into a capacity-1 cache evicts key 5.

Constraints

Limits and guarantees your solution can rely on.

1 <= capacity <= 10^5

1 <= operations.length == arguments.length <= 10^5

operations[i] is either "put" or "get"

For put, arguments[i] has length 4: [time, key, value, ttl]

For get, arguments[i] has length 2: [time, key]

Timestamps are non-decreasing and all TTL values are positive.

Use an O(operations.length) or O(operations.length log operations.length) approach.