LinkedIn·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

LinkedIn SWE interview that was basically a harder version of the classic insert/delete/getRandom problem, except they bolted on TTL semantics and wanted a real design discussion. Pretty gnarly for a coding round.

Questions Asked (1)

Design a data structure that supports insert(value, ttl), remove(value), and getRandom() in O(1) amortized time, where each inserted item has a time-to-live after which it should be treated as logically removed. Discuss how you'd handle duplicates of the same value with different TTLs, and compare lazy expiration against active eviction strategies like a priority queue or timer wheel.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

So this is LC 381 but with TTL thrown on top, which sounds manageable until you actually try to keep getRandom truly O(1).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by designing the core data structure for O(1) insert, remove, and getRandom without TTL, then layer on TTL handling using lazy expiration. Discuss duplicate values with different TTLs by storing unique entries (e.g., value+timestamp) and using a hash map to track active entries. Compare lazy expiration with active eviction strategies, highlighting trade-offs in complexity and performance.

Pro tip: Emphasize that lazy expiration keeps operations O(1) amortized by deferring cleanup to getRandom or background threads, but be prepared to discuss how to avoid unbounded memory growth. Mention that active eviction can provide stricter TTL guarantees but adds overhead and complexity.

1. Core data structure without TTL

Design a structure using a dynamic array (for O(1) random access) and a hash map (for O(1) lookup/removal) to support insert, remove, and getRandom in O(1) amortized time.

2. Integrate TTL with lazy expiration

Store expiration timestamps with each entry. On getRandom, skip and remove expired entries; on remove, check if the entry is expired and treat as removed. This keeps operations O(1) amortized.

3. Handle duplicates with different TTLs

Allow multiple entries for the same value by treating each insertion as a unique entry (e.g., with a unique ID or timestamp). Use the hash map to map value to a set of entry IDs, and ensure remove(value) removes all or a specific entry based on requirements.

4. Compare lazy vs. active eviction

Discuss lazy expiration (simple, O(1) amortized, but memory may grow) versus active eviction using a priority queue (min-heap by expiration) or timer wheel (bucketed time slots). Active eviction provides timely removal but adds O(log n) or O(1) overhead per operation and requires background threads.

5. Address scalability and concurrency

Mention how to handle concurrent access (e.g., locks, lock-free structures) and how to scale with sharding or partitioning. Discuss memory management and potential need for periodic cleanup.

Key Points to Mention

Use a dynamic array and hash map for O(1) insert, remove, and getRandom.
Lazy expiration defers removal until access, maintaining O(1) amortized time.
Duplicates with different TTLs require unique entry identifiers and a mapping from value to entries.
Active eviction strategies (priority queue, timer wheel) offer timely removal but add overhead.
Trade-offs: lazy expiration may cause memory bloat; active eviction may impact performance.
Consider concurrency and scalability for production systems.

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