Katkat
Back

Design O(1) random-sampling set

xAIMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates a candidate's competency in data-structure design, randomized algorithms, and algorithmic complexity analysis within the Coding & Algorithms domain, with a focus on achieving expected O(1) operations for insert, remove, and uniform sampling.

Design a data structure that supports insert(x), remove(x), and get_random() that returns a uniformly random element among the present items, all in expected O(

  1. time. Detail the algorithms and data structures you would use, how you handle deleting the last element and gaps, and how you would test the uniformity of get_random(). Discuss extensions such as supporting duplicates or thread-safety and the impact on complexity.