Bytedance·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Bytedance SWE interview, got a cache design problem that looked manageable on the surface but had enough edge cases to keep me busy for the whole session.

Questions Asked (1)

Design an in-memory key-value cache with LRU eviction and per-entry expiration. Each entry has a time-to-live, expired entries should be lazily removed when accessed, and get/put should both run in O(1) average time.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I knew the LRU part cold, hashmap plus doubly linked list, done that a dozen times.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a hash map for O(1) access and a doubly linked list for LRU ordering. Explain how to handle TTL with lazy expiration and discuss trade-offs of different expiration strategies.

Pro tip: Mention that lazy expiration alone can lead to memory bloat, so consider a hybrid approach with periodic cleanup or a background thread, but keep the core operations O(1).

1. Clarify Requirements

Ask about cache size limits, concurrency needs, and whether expiration should be strictly lazy or can include active cleanup. Confirm that get/put must be O(1) average time.

2. Design Core Data Structures

Use a hash map (dictionary) for O(1) key lookup, mapping to nodes in a doubly linked list that maintains LRU order. Each node stores key, value, expiration timestamp, and prev/next pointers.

3. Implement LRU Eviction

On get, move the accessed node to the front (most recently used). On put, if key exists, update value and move to front; if new, add to front and evict the least recently used (tail) if capacity exceeded.

4. Handle TTL and Lazy Expiration

Store expiration time per entry. On get, check if expired; if so, remove the entry and return null. On put, set expiration time. Optionally, discuss active expiration strategies for memory efficiency.

5. Analyze Complexity and Trade-offs

Confirm O(1) average time for get/put. Discuss trade-offs: lazy expiration saves CPU but may use more memory; active expiration adds overhead but keeps memory bounded. Mention concurrency considerations if needed.

Key Points to Mention

Hash map + doubly linked list for O(1) get/put and LRU ordering
Lazy expiration: check TTL on access and remove if expired
Eviction policy: remove least recently used when capacity is reached
Trade-offs between lazy and active expiration (memory vs CPU)
Handling edge cases: updating existing key, expired entries during eviction
Concurrency: use locks or concurrent data structures if thread-safe cache is required

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