How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bytedance during technical interviews.

Implement Expiring LRU Cache | Bytedance Coding Question

Implement Expiring LRU Cache

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Implement an in-memory key-value cache with least-recently-used eviction and per-entry expiration. The cache has a fixed positive `capacity`. Each inserted key has a time-to-live value. Once an entry expires, it should behave as if it does not exist and should be removed from the cache when encountered. Design a class with the following operations: ```text ExpiringCache(int capacity) int get(int key, int now) void put(int key, int value, int ttl, int now) ``` Rules: - `put(key, value, ttl, now)` inserts or updates `key` with `value`. - The entry expires at time `now + ttl`. - `get(key, now)` returns the value if the key exists and has not expired; otherwise return `-1`. - Accessing a non-expired key through `get` makes it the most recently used entry. - Updating an existing non-expired key through `put` updates its value, expiration time, and recency. - If an existing key has already expired, treat the operation as inserting a new key. - If inserting a new entry causes the number of non-expired entries to exceed `capacity`, evict the least recently used non-expired entry. - Expired entries should be deleted when detected. Target: make `get` and `put` run in `O(1)` average time, using an appropriate combination of a hash map and a doubly linked list.

Quick Answer: This question evaluates skill in designing and implementing efficient in-memory caching data structures, testing understanding of LRU eviction, per-entry TTL expiration, and the use of hash maps and linked lists for O(1) operations.

Design an in-memory key-value cache with both least-recently-used eviction and per-entry expiration. A normal LRU cache tracks recency of use. This version also gives every key a time-to-live (TTL). If a key was inserted or updated at time `now` with TTL `ttl`, then it expires at time `now + ttl` and is valid only while `current_time < now + ttl`. For this challenge, implement a function `solution(capacity, operations)` that simulates the cache and returns the results of all `get` operations. Each operation is one of: - `('put', key, value, ttl, now)` - `('get', key, now)` Cache rules: - `put(key, value, ttl, now)` inserts or updates `key` with `value`. - The key expires at time `now + ttl`. - `get(key, now)` returns the value if the key exists and has not expired; otherwise return `-1`. - Accessing a non-expired key through `get` makes it the most recently used entry. - Updating an existing non-expired key through `put` updates its value, expiration time, and recency. - If an existing key has already expired, treat the `put` as inserting a new key. - If inserting a new non-expired entry causes the number of non-expired entries to exceed `capacity`, evict the least recently used non-expired entry. - Expired entries should behave as if they do not exist and should be deleted when detected. Assume operation timestamps are non-decreasing.

Constraints

1 <= capacity <= 10^5
1 <= len(operations) <= 2 * 10^5
0 <= key, value, now <= 10^9
1 <= ttl <= 10^9
The `now` values in `operations` are non-decreasing

Examples

Input: (2, [('put', 1, 10, 5, 0), ('put', 2, 20, 5, 1), ('get', 1, 2), ('put', 3, 30, 5, 3), ('get', 2, 4), ('get', 1, 5), ('get', 3, 7)])

Expected Output: [10, -1, -1, 30]

Explanation: Key 1 is read before it expires, making it most recently used. Inserting key 3 evicts key 2 as the LRU non-expired key. At time 5, key 1 expires exactly then, so it returns -1.

Input: (2, [('put', 1, 100, 2, 0), ('put', 1, 111, 5, 1), ('get', 1, 2), ('put', 2, 200, 10, 2), ('put', 1, 123, 1, 6), ('get', 1, 6), ('get', 2, 6), ('get', 1, 7)])

Expected Output: [111, 123, 200, -1]

Explanation: The first update to key 1 happens before expiration, so it refreshes value and TTL. At time 6, the old key 1 has already expired, so that put acts like a fresh insertion. At time 7, the new version expires exactly then.

Input: (2, [('put', 1, 10, 100, 0), ('put', 2, 20, 1, 0), ('put', 3, 30, 100, 2), ('get', 1, 2), ('get', 2, 2), ('get', 3, 2)])

Expected Output: [10, -1, 30]

Explanation: Key 2 expires before key 3 is inserted, so it should be removed and should not force eviction of key 1. The cache ends up holding keys 1 and 3.

Input: (1, [('get', 1, 0), ('put', 1, 5, 1, 0), ('get', 1, 0), ('put', 2, 6, 5, 1), ('get', 1, 1), ('get', 2, 2), ('put', 2, 7, 1, 3), ('get', 2, 4)])

Expected Output: [-1, 5, -1, 6, -1]

Explanation: This checks the empty-cache case, capacity 1 behavior, and expiration at an exact boundary. Key 1 expires at time 1, so inserting key 2 does not need to evict any non-expired entry.

Input: (3, [('put', 1, 1, 10, 0), ('put', 2, 2, 3, 1), ('put', 3, 3, 10, 2), ('get', 1, 3), ('put', 4, 4, 10, 4), ('put', 5, 5, 10, 5), ('get', 2, 5), ('get', 3, 5), ('get', 1, 6), ('get', 4, 6), ('get', 5, 15)])

Expected Output: [1, -1, -1, 1, 4, -1]

Explanation: Key 2 expires at time 4 and is removed before key 4 is inserted. Later, inserting key 5 makes four active keys, so the LRU active key 3 is evicted. At time 15, key 5 expires exactly then.

Hints

For the LRU behavior, the standard approach is a hash map for O(1) key lookup plus a doubly linked list for O(1) recency updates.
Expiration can happen even for keys you do not directly access. Consider an additional structure ordered by expiration time and use lazy deletion to discard stale records.

Quick Overview

This question evaluates skill in designing and implementing efficient in-memory caching data structures, testing understanding of LRU eviction, per-entry TTL expiration, and the use of hash maps and linked lists for O(1) operations.