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.

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.

Hints

  1. 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.
  2. 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.

Loading coding console...