Bytedance·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

Bytedance SWE interview that was essentially one meaty coding problem: build an LFU cache from scratch with O(1) ops. Not a warmup question.

Questions Asked (1)

Design and implement an LFU cache with a given capacity. It should support get and put operations in O(1) average time, and evict the least frequently used key on overflow, breaking ties by least recently used.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The eviction policy is where people trip up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then propose a design using a hash map for O(1) key lookup and a frequency-indexed doubly linked list to maintain LRU order within each frequency. Explain how get and put operations update frequencies and handle eviction, and analyze time and space complexity.

Pro tip: Mention that LFU is prone to cache pollution from stale frequently-used items; you can address this by using a frequency aging mechanism or a max-heap with lazy deletion, showing awareness of real-world trade-offs.

1. Clarify Requirements and Edge Cases

Ask about capacity constraints, expected operation mix, and whether keys/values are integers. Discuss edge cases like capacity 0, updating existing keys, and tie-breaking.

2. Design Data Structures

Propose a hash map from key to node, and a frequency map from frequency to a doubly linked list of nodes (maintaining LRU order). Also maintain a min frequency pointer for O(1) eviction.

3. Implement Core Operations

For get: if key exists, update its frequency and move it to the appropriate frequency list, then return value. For put: if key exists, update value and frequency; else insert new node with frequency 1, and if over capacity, evict the LRU node from the min frequency list.

4. Analyze Complexity and Trade-offs

Explain that both operations are O(1) average due to hash map lookups and constant-time list manipulations. Discuss space complexity O(capacity) and potential improvements like using a balanced tree for frequencies if needed.

5. Test with Examples

Walk through a small example (e.g., capacity 2) to demonstrate correct eviction and tie-breaking. Mention how to handle concurrent access if relevant.

Key Points to Mention

Use a hash map for O(1) key access and a frequency-indexed doubly linked list for O(1) updates and eviction.
Maintain a min frequency pointer to quickly find the least frequently used list for eviction.
Tie-breaking by LRU: within each frequency list, maintain insertion order (or move to tail on access) so the head is the LRU.
On get or put, increment the node's frequency and move it to the next frequency list, updating min frequency if necessary.
Eviction: remove the head of the min frequency list and delete the key from the hash 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.