Bloomberg·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Bloomberg SWE coding round, one problem the whole time. The question was about building a randomized set with O(1) operations, which sounds manageable until you actually think about getRandom without a list.

Questions Asked (1)

Design and implement a RandomizedSet class that supports insert, remove, and getRandom, where each operation must run in O(1) average time.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The insert and remove with O(1) are fine with a hashmap, but getRandom is where it gets tricky.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the O(1) average time requirement and the need for random access. Propose using a dynamic array (list) for O(1) random access and a hash map for O(1) insert/remove by storing value-to-index mappings. Explain how to handle removal by swapping the target element with the last element, updating the map, and popping from the array.

Pro tip: Mention that while average O(1) is achievable, worst-case O(1) is not possible with this approach due to potential hash collisions, but it's acceptable for most practical purposes. Also, discuss how to handle duplicates and edge cases like removing the last element.

1. Clarify Requirements

Confirm that all operations must be O(1) average time, and that the set contains unique elements. Discuss whether duplicates are allowed and how to handle them.

2. Choose Data Structures

Select a dynamic array (list) for O(1) random access and a hash map (dictionary) for O(1) insert/remove by mapping values to their indices in the array.

3. Implement Insert

Check if the value already exists in the map; if not, append it to the array and add its index to the map. Return true if inserted, false otherwise.

4. Implement Remove

If the value exists, swap it with the last element in the array, update the map for the swapped element, then remove the last element from both the array and the map. Return true if removed, false otherwise.

5. Implement getRandom

Generate a random index within the array bounds and return the element at that index. Ensure uniform distribution by using a proper random number generator.

Key Points to Mention

Time complexity analysis: O(1) average for insert, remove, and getRandom due to hash map and array operations.
Space complexity: O(n) for storing n elements in both the array and hash map.
Handling duplicates: The set should not contain duplicates; insert should check existence.
Edge cases: removing the last element, removing an element not present, and inserting an existing element.
Trade-offs: Using a hash map adds overhead but enables O(1) removal; alternative approaches like balanced BST would be O(log n).
Randomness: Ensure getRandom is uniformly random by using a proper random index generation.

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