How do you design a Data Structure that supports insert, delete, search, and getRandom in O(1)?

Difficulty: 6/10

hash map, dynamic array, random access

O(1) Randomized Set

Use a dynamic array plus a hash map from value to its array index. The array provides O(1) random access and random selection. The hash map provides O(1) average lookup. For deletion, swap the element to remove with the last array element, update its index in the map, and remove the last slot.

javascript

1
Search: O(1) average.
2
Insert: O(1) amortized.
3
Delete: O(1) average.
4
getRandom: O(1).
5
Random selection is uniform when selecting uniformly from array indices.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions