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 Nimble.

What role is this question designed for?

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

Implement a TTL LRU Cache | Nimble Coding Question

Implement a TTL LRU Cache

Company: Nimble

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Design and implement an in-memory bounded cache with per-entry expiration and LRU eviction. The cache stores `uint32_t` keys and `std::string` values. Each entry has an expiration timestamp computed from a time-to-live value. ### API Implement the following methods for a class `BoundedExpiringCache`: ```cpp class BoundedExpiringCache { public: BoundedExpiringCache( size_t capacity, double default_ttl, std::function<double()> time_fn ); std::optional<std::string> get(uint32_t key); void put( uint32_t key, const std::string& value, std::optional<double> ttl = std::nullopt ); bool remove(uint32_t key); void clear(); size_t size() const; private: void evict(); }; ``` ### Requirements 1. `capacity` is the maximum number of entries the cache may hold. 2. `default_ttl` is the default time-to-live in seconds for inserted entries. 3. `time_fn` returns the current time in seconds and should be used instead of directly reading the system clock. 4. `get(key)`: - Return the value if the key exists and has not expired. - Return `std::nullopt` if the key is missing or expired. - If the key is expired, remove it. - A successful `get` counts as a use and should update LRU order. 5. `put(key, value, ttl)`: - Insert a new key or update an existing key. - Updating an existing key should update the value, reset its expiration, and mark it as recently used. - If `ttl` is provided, use it for this entry; otherwise use `default_ttl`. - After insertion or update, enforce the capacity limit. 6. `remove(key)` removes the key if present and returns whether it existed. 7. `clear()` removes all entries. 8. `size()` returns the number of entries currently stored in the cache. ### Eviction Policy When the cache exceeds capacity: 1. Expired entries must never be returned by `get`. 2. The cache should prefer removing expired entries before evicting valid entries, but you should be prepared to explain the tradeoff between globally finding expired entries and maintaining constant-time operations. 3. Among unexpired entries, evict the least recently used entry. ### Performance Target Aim for `O(1)` average time for `get`, `put`, and `remove`, and `O(1)` amortized eviction under a reasonable lazy-expiration strategy. You may use standard C++ containers such as `std::unordered_map`, `std::list`, `std::map`, or `std::priority_queue`. Be prepared to justify your data structure choices and explain whether it is possible to both globally remove every expired entry before any valid entry and still guarantee `O(1)` average or amortized time with a hash map plus LRU list alone.

Quick Answer: This question evaluates understanding of in-memory cache design, including per-entry TTL expiration, LRU eviction, and the data structure and complexity trade-offs required to achieve O(1) average operations.

Implement `solution(capacity, default_ttl, operations)` to simulate a bounded in-memory cache with per-entry expiration and LRU eviction. For this judged version, each cache method call is represented by a timestamped operation, so you do not need to read the real clock. An entry written at time `t` with TTL `x` expires at time `t + x`, and it is considered expired for any operation whose timestamp is greater than or equal to that expiration time. A successful `get` marks the entry as most recently used. Updating an existing key replaces its value, resets its expiration time, and also marks it as most recently used. When a `put` would make the cache exceed `capacity`, expired entries at the current time must be removed first; if the cache is still too large, evict the least recently used remaining entry. `size` should count only unexpired entries at that operation time.

Constraints

0 <= capacity <= 200000
1 <= len(operations) <= 200000
Operation timestamps are in non-decreasing order
0 < default_ttl <= 10^9 and any provided ttl satisfies 0 < ttl <= 10^9
0 <= key <= 2^32 - 1
The total length of all value strings is at most 200000

Examples

Input: (2, 5, [('put', 1, 'x', 'a'), ('get', 2, 'x'), ('get', 6, 'x'), ('size', 6)])

Expected Output: ['a', None, 0]

Explanation: `x` is written at time 1 with expiry 6. It is still valid at time 2, but expired at time 6, so the final size is 0.

Input: (2, 5, [('put', 1, 'x', 'a'), ('get', 2, 'x'), ('put', 3, 'y', 'b', 1), ('get', 4, 'y'), ('get', 4, 'x'), ('put', 5, 'z', 'c'), ('get', 5, 'z'), ('size', 5)])

Expected Output: ['a', None, 'a', 'c', 2]

Explanation: `y` has TTL 1, so it expires at time 4. `x` remains valid, `z` is added later, and the cache contains `x` and `z` at the end.

Input: (2, 10, [('put', 1, 'a', 1), ('put', 2, 'b', 2), ('get', 3, 'a'), ('put', 4, 'c', 3), ('get', 5, 'b'), ('get', 5, 'a'), ('get', 5, 'c'), ('size', 5)])

Expected Output: [1, None, 1, 3, 2]

Explanation: Accessing `a` makes it most recently used, so when `c` is inserted into a full cache, `b` is the least recently used key and gets evicted.

Input: (2, 2, [('put', 1, 'a', 10), ('put', 2, 'b', 20, 10), ('put', 3, 'c', 30, 10), ('get', 3, 'a'), ('get', 3, 'b'), ('get', 3, 'c'), ('size', 3)])

Expected Output: [None, 20, 30, 2]

Explanation: `a` expires exactly at time 3, so it must be removed before inserting `c`. That means no unexpired key needs to be evicted.

Input: (2, 3, [('put', 1, 'a', 'old'), ('put', 2, 'b', 'keep'), ('put', 3, 'a', 'new', 5), ('put', 4, 'c', 'extra'), ('get', 4, 'b'), ('get', 4, 'a'), ('get', 7, 'a'), ('get', 8, 'a'), ('size', 8)])

Expected Output: [None, 'new', 'new', None, 0]

Explanation: Updating `a` changes its value, extends its lifetime, and makes it most recently used. `b` becomes the LRU entry and is evicted when `c` is inserted.

Input: (0, 5, [('put', 1, 'x', 'ignored'), ('get', 1, 'x'), ('size', 2)])

Expected Output: [None, 0]

Explanation: A cache with capacity 0 cannot store any entries.

Hints

Use a hash map for direct access by key, and keep recency in a structure that can move an entry to the most-recent end in O(1).
Expired entries are not guaranteed to be near the LRU end. A separate min-heap of expiration times lets you remove them lazily without scanning the whole cache.

Quick Overview

This question evaluates understanding of in-memory cache design, including per-entry TTL expiration, LRU eviction, and the data structure and complexity trade-offs required to achieve O(1) average operations.