Bytedance·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePass

Jun 2026Remote

Summary

Bytedance SWE coding round, roughly an hour. The problem was a hard-level LeetCode variant and I didn't finish cleanly, but somehow passed anyway.

Questions Asked (1)

Implement an LRU Cache with TTL support, where each entry can have its own expiration time passed at call time. Handle expired entries correctly across get and put operations.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is already a hard problem on its own and adding TTL made it significantly more involved.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements: TTL per entry, eviction policy (LRU), and expected operations. Then design a data structure combining a hash map for O(1) access and a doubly linked list for LRU order, with lazy expiration on access and optional background cleanup. Discuss trade-offs between eager vs lazy expiration and how to handle expired entries during get and put.

Pro tip: Mention that you would use lazy expiration to avoid overhead, but also consider a background thread for proactive cleanup to prevent memory bloat—showing awareness of real-world production concerns. Also, highlight that TTL should be checked on both get and put to ensure expired entries are not returned or counted towards capacity.

1. Clarify Requirements and Constraints

Ask about expected operations (get, put), TTL granularity, concurrency needs, and whether TTL is set per entry or globally. Confirm that expired entries should be treated as non-existent.

2. Choose Core Data Structures

Use a hash map for O(1) key lookup and a doubly linked list to maintain LRU order. Each node stores key, value, and expiration timestamp.

3. Implement Get with Lazy Expiration

On get, check if the entry exists and if it's expired. If expired, remove it and return null; otherwise, move it to the front (most recently used) and return the value.

4. Implement Put with Capacity and TTL Handling

On put, if key exists, update value and expiration, and move to front. If new, check capacity: evict least recently used (and expired entries if any) before inserting. Set expiration timestamp based on TTL.

5. Discuss Expiration Strategies and Trade-offs

Explain lazy expiration vs. background cleanup. Lazy is simpler but may leave expired entries until accessed; background cleanup prevents memory bloat but adds complexity. Mention thread-safety if needed.

Key Points to Mention

O(1) time complexity for get and put using hash map + doubly linked list.
Lazy expiration: check TTL on access and remove if expired.
Eviction policy: LRU eviction when capacity is exceeded, but expired entries should be removed first.
TTL per entry: each put call can specify a different TTL, stored as expiration timestamp.
Handling expired entries during put: if updating an expired key, treat as new insertion.
Trade-offs: memory overhead of timestamps, potential stale entries with lazy expiration, and concurrency considerations.

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