How should I practice LRU Cache with TTL Expiration?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Tiktok online assessment problems in FastPrep.

Is LRU Cache with TTL Expiration associated with Tiktok?

FastPrep tags this as a Tiktok coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Design

LRU Cache with TTL Expiration

● HardTiktokFULLTIMEONSITE INTERVIEW

See Tiktok 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.

Examples

01 · Example 1

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]]
return = ["10","-1","20","-1"]

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.

02 · Example 2

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]]
return = ["9","-1"]

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

Constraints

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.