TikTok·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

TikTok software engineer interview that was pretty much a classic LRU cache problem. Nothing too surprising but there were a lot of follow-up angles they pushed on, so it wasn't just 'code it and move on'.

Questions Asked (1)

Design and implement an in-memory LRU cache with O(1) get and put operations. Walk through your data structure choices, how you maintain access order, and how updates to existing keys are handled.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I went with the standard hashmap plus doubly linked list combo, which they seemed fine with.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (capacity, eviction policy, thread-safety) and then propose a hash map combined with a doubly linked list to achieve O(1) operations. Explain how the hash map stores key-to-node references and the linked list maintains access order, with the most recently used at the head. Walk through get and put operations, covering edge cases like updating existing keys and evicting the least recently used when at capacity.

Pro tip: Mention that you would use a doubly linked list with sentinel head and tail nodes to simplify edge cases and avoid null checks, and discuss how you would make it thread-safe if needed (e.g., using a mutex or concurrent data structures).

1. Clarify Requirements and Constraints

Ask about cache capacity, expected operations, thread-safety needs, and whether keys/values are generic. Confirm that O(1) time complexity is required for both get and put.

2. Choose Data Structures

Propose a hash map (dictionary) for O(1) key lookup and a doubly linked list to maintain access order. Explain that the hash map maps keys to nodes in the linked list.

3. Define Node and Cache Structure

Describe the node structure (key, value, prev, next) and the cache structure (hash map, head and tail pointers, capacity, current size). Mention using sentinel nodes to simplify operations.

4. Implement get and put Operations

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

5. Analyze Complexity and Edge Cases

Confirm O(1) time for both operations due to hash map and linked list. Discuss edge cases: updating existing key, evicting when full, capacity 0 or 1, and thread-safety if required.

Key Points to Mention

Hash map provides O(1) access to nodes, doubly linked list maintains access order with O(1) insertions/deletions.
Most recently used item is at the head; least recently used is at the tail.
On get, move accessed node to head to mark it as most recently used.
On put, if key exists, update value and move to head; if new, add to head and evict tail if over capacity.
Use sentinel head and tail nodes to avoid null checks and simplify edge cases.
Consider thread-safety: use locks or concurrent data structures if multiple threads access the cache.

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