Problem (verbatim)
Design a data structure that supports insert, delete, search, and getRandom in constant time.
Use a dynamic array + hash map (value → index).
- insert(x): if absent, push to end; map
xto its index. - search(x): check map.
- delete(x): swap the element at
index(x)with the last element, update the swapped element’s index in the map, pop the back, removexfrom map. - getRandom(): pick a uniform random index in
[0..size-1]and return the array element.
All operations are amortized O(1); space O(n).
Pitfall: on delete, update the swapped element’s index before popping to keep indices and uniform randomness correct.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Tiktok, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
END
