Bytedance·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Bytedance SWE interview, coding round, one classic design question that I thought I knew cold but fumbled a bit on the implementation details under pressure.

Questions Asked (1)

Design and implement an LRU cache with a fixed capacity that supports get and put operations, both in O(1) average time. get should return -1 if the key isn't found, and put should evict the least recently used entry when the cache is at capacity.

Algorithms & Data StructuresSystem Design

Author's notes

I knew this problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map for O(1) key lookup and a doubly linked list to track usage order, with the most recently used at the head and least recently used at the tail. For get, move the accessed node to the head; for put, insert or update and move to head, evicting the tail if capacity is exceeded. This combination ensures both operations run in O(1) average time.

Pro tip: Mention that you would use dummy head and tail nodes to simplify edge cases in the linked list, and discuss thread-safety considerations if the cache might be accessed concurrently.

1. Clarify requirements and constraints

Confirm the capacity is fixed and positive, and that get and put must be O(1) average time. Ask about thread-safety requirements and whether keys/values are integers or generic types.

2. Choose data structures

Select a hash map for O(1) key-to-node lookup and a doubly linked list to maintain usage order. Explain that the hash map stores references to nodes in the list, enabling O(1) updates.

3. Define node and list operations

Describe a node with key, value, prev, and next pointers. Outline helper methods to add a node to the head (most recently used) and remove a node from the list, using dummy head and tail sentinels to avoid null checks.

4. Implement get and put

For get: if key exists, move its node to the head and return value; else return -1. For put: if key exists, update value and move to head; else create a new node, add to head, and if size exceeds capacity, remove the tail node and delete its key from the map.

5. Analyze complexity and edge cases

State that both operations are O(1) average time due to hash map and linked list operations. Discuss edge cases: capacity 0 or 1, updating existing key, and eviction when full.

Key Points to Mention

Hash map provides O(1) average lookup by key.
Doubly linked list maintains recency order with O(1) insertions and deletions.
Dummy head and tail nodes simplify list operations and edge cases.
On get, move accessed node to the head to mark it as most recently used.
On put, if at capacity, evict the tail node (least recently used) and remove its key from the map.
Time complexity: O(1) average for both get and put; space complexity: O(capacity).

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