Uber·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Uber SWE interview that went deep on a data structure design problem and then pivoted into concurrency pretty fast. The coding part felt manageable but the follow-up on thread safety is where things got interesting.

Questions Asked (2)

Design a FirstUnique class that supports two operations: one that returns the first unique value seen in a stream (or -1 if there isn't one), and one that appends a new value to the stream.

Algorithms & Data Structures

Author's notes

I went with a HashMap for counts and a LinkedHashSet to track insertion-ordered uniques.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the API and constraints, then propose a solution using a hash map to track counts and a doubly linked list to maintain insertion order of unique elements. Explain how showFirstUnique and add operations work in O(1) time, and discuss edge cases and potential optimizations.

Pro tip: Mention that the doubly linked list nodes can be stored in the hash map for O(1) removal, and that this design is similar to an LRU cache, showing you can apply familiar patterns to new problems.

1. Clarify requirements and constraints

Ask about the expected input types, frequency of operations, memory constraints, and whether the stream can be very large. Confirm that showFirstUnique should return -1 if no unique value exists.

2. Choose data structures

Select a hash map to track the count of each value and a doubly linked list to maintain the order of unique values. Explain why this combination allows O(1) operations.

3. Design the algorithm

Detail how add(value) updates the count and list: if value is new, add to list and map; if it becomes non-unique, remove from list. showFirstUnique() returns the head of the list or -1.

4. Analyze complexity and edge cases

State that both operations are O(1) time and O(n) space. Discuss edge cases like duplicate values, empty stream, and large streams.

5. Test and optimize

Walk through an example to verify correctness. Mention potential optimizations like using a sentinel node or handling integer overflow.

Key Points to Mention

Use a hash map to store the count of each value and a doubly linked list to maintain insertion order of unique values.
Store references to linked list nodes in the hash map for O(1) removal when a value becomes non-unique.
showFirstUnique returns the value at the head of the linked list, or -1 if the list is empty.
add(value) increments the count; if count becomes 1, append to list; if count becomes 2, remove from list.
Time complexity: O(1) for both operations; space complexity: O(n) where n is the number of unique values.
Edge cases: duplicate values, empty stream, and ensuring the list only contains unique values.

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

How would you make this class thread-safe if multiple threads are calling add() and showFirstUnique() concurrently? Walk through your locking options and the trade-offs.

System DesignTechnical Trade-offs

Author's notes

This is where I felt a bit exposed.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the class's current design and the concurrency requirements, then systematically evaluate locking strategies from coarse-grained to fine-grained. Discuss trade-offs in terms of correctness, performance, and scalability, and conclude with a recommendation based on expected read/write patterns.

Pro tip: Mention that you would first check if the class can be made thread-safe by design (e.g., using concurrent collections) before adding locks, as this often leads to better performance and simpler code.

1. Clarify Requirements and Current Design

Ask about the class's invariants, expected read/write ratio, and performance goals. Identify shared mutable state and operations that must be atomic.

2. Evaluate Locking Options

Consider coarse-grained locking (single lock for all methods), fine-grained locking (separate locks for different data structures), and lock-free/concurrent data structures. Discuss pros and cons of each.

3. Analyze Trade-offs

Compare options on correctness, contention, throughput, latency, and complexity. For example, coarse-grained locking is simple but may bottleneck; fine-grained improves concurrency but risks deadlock and complexity.

4. Recommend and Justify

Choose an approach based on the analysis, explaining why it fits the scenario. Mention potential optimizations like read-write locks if reads dominate.

5. Discuss Testing and Edge Cases

Outline how to test thread safety (stress tests, race detectors) and handle edge cases like reentrancy or lock ordering to avoid deadlocks.

Key Points to Mention

Atomicity and visibility guarantees provided by locks (e.g., synchronized, ReentrantLock)
Coarse-grained vs. fine-grained locking and their impact on contention and scalability
Using concurrent collections (e.g., ConcurrentHashMap) to reduce locking
ReadWriteLock for read-heavy workloads to allow concurrent reads
Potential for deadlock and strategies to avoid it (lock ordering, timeouts)
Performance considerations: lock contention, context switching, and throughput

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