Commure·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026Remote

Summary

Commure SWE interview that went deep on a single design problem. The whole session was basically one extended question about caching with a twist, and they kept pushing on edge cases I hadn't fully thought through.

Questions Asked (1)

Design and implement an LRU cache that also supports per-key TTL expiration. It should handle get(key), put(key, value, ttl), skip returning expired entries, and evict least-recently-used when at capacity. Walk through your data structures and complexity.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

Started with the standard hashmap plus doubly linked list setup and felt pretty good about it, then they asked how expiry interacts with eviction order and I stumbled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., TTL semantics, concurrency, eviction policy) and then propose a design combining a hash map for O(1) key lookup with a doubly linked list for O(1) LRU eviction. Explain how to integrate TTL by storing expiration timestamps and lazily removing expired entries on access, with optional background cleanup. Finally, analyze time and space complexity and discuss trade-offs such as lazy vs. eager expiration.

Pro tip: Mention that you would use a min-heap or time-ordered data structure for efficient expiration, but note that lazy deletion on access is often sufficient and simpler; this shows you understand practical trade-offs. Also, proactively discuss thread-safety if the cache is used in a concurrent environment.

1. Clarify Requirements and Constraints

Ask about TTL semantics (e.g., should expired entries be removed immediately or lazily?), concurrency needs, and whether the cache is expected to be thread-safe. Confirm that get should not return expired entries and that put should evict LRU when at capacity.

2. Choose Core Data Structures

Propose a hash map (dictionary) for O(1) key lookup and a doubly linked list to maintain access order for LRU eviction. Each node in the list stores key, value, and expiration timestamp.

3. Design Operations (get and put)

For get: check if key exists, if expired remove it and return null, else move node to front (most recently used) and return value. For put: if key exists update value and TTL and move to front; else create new node, add to front, and if capacity exceeded evict least recently used (tail).

4. Handle TTL Expiration

On each access, check if the node's expiration time has passed; if so, remove it and treat as miss. Optionally, implement a background thread or periodic cleanup to remove expired entries proactively, but note the trade-offs.

5. Analyze Complexity and Trade-offs

State that get and put are O(1) time on average, and space is O(capacity). Discuss trade-offs: lazy expiration may leave stale entries until accessed, while eager expiration requires additional overhead; concurrency may require locks or concurrent data structures.

Key Points to Mention

Hash map provides O(1) average time for key lookup, and doubly linked list provides O(1) for moving nodes and evicting LRU.
TTL can be implemented by storing an expiration timestamp per entry and checking it on access (lazy expiration).
Expired entries should be removed on access and not returned; they also should not count towards capacity if possible.
LRU eviction: when capacity is reached, remove the least recently used item (tail of the list).
Thread-safety considerations: use locks or concurrent data structures if the cache is shared across threads.
Trade-offs: lazy vs. eager expiration, memory overhead of timestamps, and potential need for a background cleaner.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.