← Uber Interview Insights

Uber·Frontend Engineer·Technical Phone Screen·Intermediate

Intermediate
Mar 2026

Summary

Uber frontend engineer coding screen, one question, nothing too wild. The more memorable part was realizing mid-interview that my interviewer seemed to be conducting the whole thing from bed.

Questions Asked (1)

Q1

Design a data structure that supports insert, delete, and getRandom in O(1) average time.

Algorithms & Data Structures
Author's notes

Classic problem, I'd seen it before, but the O(1) getRandom part still takes a second to click.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Combine a hash map for O(1) insert/delete with a dynamic array for O(1) random access. When deleting, swap the target element with the last element in the array, update the hash map, then pop the last element. This maintains O(1) average time for all operations.

Pro tip: Mention that this design is used in real-world systems like load balancers and caches for random eviction, and discuss how it handles duplicates if allowed. Also, clarify that getRandom returns each element with equal probability.

1. Clarify requirements

Ask if duplicates are allowed, if getRandom should return each element with equal probability, and if the data structure needs to handle other operations. Confirm that average O(1) is acceptable.

2. Choose data structures

Select a hash map (dictionary) to store value-to-index mappings for O(1) lookup, and a dynamic array (list) to store elements for O(1) random access.

3. Implement insert

Append the new element to the array and record its index in the hash map. If duplicates are allowed, the hash map should map value to a set of indices.

4. Implement delete

To delete a value, retrieve its index from the hash map. Swap it with the last element in the array, update the hash map for the swapped element, then remove the last element from the array and the value from the hash map.

5. Implement getRandom

Generate a random index between 0 and array length - 1 and return the element at that index. This gives each element an equal probability.

Key Points to Mention

  • Hash map provides O(1) average time for insert and delete by mapping values to indices.
  • Dynamic array provides O(1) random access for getRandom.
  • Swap-with-last technique avoids shifting elements, keeping delete O(1).
  • Handling duplicates: use a hash map from value to a set of indices, and update the set on swap/delete.
  • Time complexity: all operations are O(1) average, O(n) worst-case for hash map collisions.
  • Space complexity: O(n) for storing n elements.

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