← Bytedance Interview Insights

Bytedance·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate
Apr 2026

Summary

Bytedance coding round for a software engineer role, just the one question: implement an LRU cache. Short and to the point, no fluff.

Questions Asked (1)

Q1

Implement a Least Recently Used (LRU) cache from scratch.

Algorithms & Data Structures
Author's notes

Classic question but I still fumbled the eviction logic for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: fixed capacity, O(1) get and put operations. Then explain that a hash map combined with a doubly linked list achieves this, with the map providing O(1) access to nodes and the list maintaining recency order. Walk through the implementation details, including edge cases like updating existing keys and evicting the least recently used item when capacity is exceeded.

Pro tip: Mention that you can use a dummy head and tail node to simplify edge cases in the doubly linked list, and discuss how this design is used in real systems like Redis or CPU caches. This shows practical awareness beyond textbook knowledge.

1. Clarify requirements and constraints

Confirm that the cache has a fixed capacity, supports get and put in O(1) time, and evicts the least recently used item when full. Ask about thread safety if relevant.

2. Choose data structures

Explain that a hash map (for O(1) key lookup) and a doubly linked list (for O(1) insertion, deletion, and recency ordering) together meet the requirements.

3. Design the node and list operations

Define a node with key, value, prev, and next pointers. Describe helper methods to add a node to the front (most recently used) and remove a node from anywhere in the list.

4. Implement get and put

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

5. Analyze complexity and edge cases

State that both operations are O(1) time and O(capacity) space. Discuss edge cases like capacity 0 or 1, updating existing keys, and handling null values.

Key Points to Mention

  • Hash map provides O(1) access to cache nodes by key.
  • Doubly linked list maintains recency order with O(1) insertions and deletions.
  • Dummy head and tail nodes simplify boundary conditions.
  • Eviction policy: remove the node just before the tail (least recently used).
  • Time complexity: O(1) for both get and put; space complexity: O(capacity).
  • Real-world applications: Redis, Memcached, CPU caches, database buffer pools.

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