DoorDash·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

DoorDash technical phone screen centered entirely on a classic data structure design problem. The question had a debugging twist which made it a bit more stressful than a clean implementation from scratch.

Questions Asked (1)

Design a data structure that supports insert, remove, and getRandom in average O(1) time. You're given a buggy implementation; find and fix the bugs, then explain why getRandom produces a uniform distribution.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The core idea clicked for me pretty fast: hash map for O(1) lookup, dynamic array for O(1) random access, and the swap-with-last trick on remove so you don't leave holes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by outlining the standard O(1) design: a dynamic array for O(1) random access and a hash map from value to index for O(1) lookup. Then systematically trace through the buggy code to identify common pitfalls like incorrect index updates during removal or flawed random index generation. Finally, explain that uniform distribution arises because each element occupies exactly one array slot and getRandom selects an index uniformly at random.

Pro tip: When debugging, always test edge cases like removing the last element or removing an element that was just swapped; these often reveal index update bugs. Also, mention that using a cryptographically secure random number generator is unnecessary here—a simple PRNG suffices for average O(1) and uniform distribution.

1. Clarify requirements and constraints

Confirm that all operations must be average O(1), duplicates are allowed, and getRandom should return each element with equal probability. Ask if the data structure needs to handle null values or if the input size is bounded.

2. Describe the standard design

Explain using an array (or ArrayList) to store elements and a hash map mapping each value to its index in the array. Insert appends to the array and adds to the map; remove swaps the target with the last element, updates the map, and removes the last element; getRandom picks a random index from the array.

3. Identify bugs in the given implementation

Common bugs include: not updating the index of the swapped element in the map, not handling removal of the last element correctly, using a random index that can be out of bounds, or failing to update the map when removing. Trace through each operation with a small example to spot inconsistencies.

4. Fix the bugs and verify correctness

Correct the index updates in the map during removal, ensure the random index is within bounds, and handle edge cases like empty structure. Walk through insert, remove, and getRandom on a sample sequence to confirm O(1) and correctness.

5. Explain uniform distribution

Argue that since each element is stored exactly once in the array, and getRandom selects an index uniformly at random from 0 to n-1, each element has probability 1/n of being chosen. The swap-remove operation maintains this property by keeping the array compact.

Key Points to Mention

Use a dynamic array for O(1) random access and a hash map for O(1) value-to-index lookup.
Swap-remove technique: swap the element to remove with the last element, update the map for the swapped element, then pop the last element.
Common bugs: forgetting to update the map for the swapped element, incorrect index handling when removing the last element, or using an off-by-one random index.
Uniform distribution is guaranteed because each element occupies exactly one array slot and getRandom picks an index uniformly at random.
Average O(1) time for insert, remove, and getRandom relies on hash map operations being O(1) on average and array operations being O(1).
Edge cases: removing from an empty structure, removing the only element, and handling duplicates correctly.

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