Design O(1) random-sampling set

Q: Design O(1) random-sampling set

This is a Coding & Algorithms interview question from xAI for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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(

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.

Design O(1) random-sampling set

Comments (0)