Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Phone screen for a Software Engineer role at Uber. The coding part was straightforward but the real interview was the design conversation that followed, which felt like it mattered a lot more than getting the code right.

Questions Asked (1)

Implement an LRU Cache with get and put operations in O(1) time.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

Finished the implementation in about 25 minutes, no major issues.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map for O(1) access to cache entries and a doubly linked list to maintain the order of usage, with the most recently used at the head and least recently used at the tail. On get, move the accessed node to the head; on put, add new nodes to the head and evict the tail when capacity is exceeded.

Pro tip: Mention that you would use a doubly linked list instead of a singly linked list to achieve O(1) removal of a node given its reference, and discuss how to handle edge cases like updating an existing key or capacity of zero.

1. Clarify requirements and constraints

Confirm that both get and put must be O(1), and discuss assumptions like positive capacity, thread-safety, and whether keys/values are integers or generic.

2. Choose data structures

Select a hash map for O(1) key lookup and a doubly linked list for O(1) insertion, deletion, and reordering of nodes.

3. Design node and cache structure

Define a node with key, value, prev, and next pointers. The cache maintains a map from key to node, a head and tail sentinel, and a capacity.

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 size exceeds capacity, remove tail node and its key from map.

5. Analyze complexity and edge cases

Explain that both operations are O(1) time and O(capacity) space. Discuss edge cases: capacity 0, updating existing key, and eviction when full.

Key Points to Mention

Hash map provides O(1) access to cache nodes by key.
Doubly linked list allows O(1) removal and insertion of nodes, maintaining usage order.
Most recently used (MRU) at head, least recently used (LRU) at tail for easy eviction.
On get, move accessed node to head to mark it as recently used.
On put, add new node to head; if capacity exceeded, remove tail and delete its key from map.
Use sentinel nodes (dummy head and tail) to simplify edge cases in linked list operations.

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