Katkat
Back

Implement O(1) randomized multiset

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement O(1) randomized multiset evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Write code for a data structure that supports add(x), remove(x), and getRandom() in average O(

  1. 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.