TikTok·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

TikTok software engineer interview with a classic LRU cache problem. Nothing too wild but the O(1) constraint is where people trip up if they haven't seen it before.

Questions Asked (1)

Design and implement an LRU cache with a fixed capacity, supporting get and put operations both in O(1) time.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The problem itself is straightforward if you've seen it, but I fumbled explaining why a plain hashmap isn't enough.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (capacity, O(1) get/put, eviction policy) and then propose a hash map combined with a doubly linked list to achieve O(1) operations. Walk through the design, implement the core methods, and discuss trade-offs and edge cases.

Pro tip: Mention that you would use a sentinel head and tail node to simplify edge cases in the doubly linked list, and explicitly state that this avoids null checks and makes the code cleaner and less error-prone.

1. Clarify requirements and constraints

Confirm that the cache has a fixed capacity, that get and put must be O(1), and that the eviction policy is least recently used. Ask about thread safety if relevant.

2. Choose data structures

Explain that a hash map provides O(1) access to nodes, and a doubly linked list maintains recency order with O(1) insertion and deletion. Together they meet the O(1) requirement.

3. Design the node and cache structure

Define a node with key, value, prev, and next pointers. The cache holds a map from key to node, a capacity, and sentinel head/tail nodes to simplify list operations.

4. Implement get and put operations

For get: if key exists, move node to front (most recently used) and return value; else return -1. For put: if key exists, update value and move to front; else create node, add to front, and if over capacity, remove least recently used node (tail's prev) and delete from map.

5. Analyze complexity and discuss trade-offs

State that both operations are O(1) time and O(capacity) space. Discuss alternatives like using an ordered dictionary (if language supports) or trade-offs with other eviction policies (e.g., LFU).

Key Points to Mention

Hash map provides O(1) lookup, doubly linked list provides O(1) insertion/deletion for recency ordering.
Sentinel head and tail nodes eliminate edge cases for empty list and boundary operations.
On get, move accessed node to the front (most recently used).
On put, if capacity exceeded, evict the node at the tail (least recently used) and remove its key from the map.
Time complexity: O(1) for both get and put; space complexity: O(capacity).
Consider thread safety if the cache will be accessed concurrently (e.g., use locks or concurrent data structures).

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