Implement O(1) randomized multiset
Overview
This question evaluates a candidate's competency in designing and analyzing randomized data structures that support O(1) average-time add, remove, and multiplicity-weighted getRandom operations, emphasizing hashing, index management, and probabilistic reasoning about sampling by multiplicity.
TikTok
Jul 17, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
Write code for a data structure that supports add(x), remove(x), and getRandom() in average O(
- time where duplicates are allowed, and getRandom returns an element with probability proportional to its multiplicity. Explain your design, analyze time/space complexity, and discuss edge cases and randomized testing.