Katkat
Back

Design a Randomized Multiset

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates the ability to design and implement a randomized multiset that correctly handles duplicate integer occurrences while providing expected O(1) insert, remove, and uniform getRandom operations, testing knowledge of data structures, randomness, and performance constraints.

Implement a data structure for integers that allows duplicate values and supports the following operations in expected O(1) time:

  • insert(val): Add one occurrence of val. Return true if val was not already present in the collection, otherwise return false.
  • remove(val): Remove one occurrence of val if it exists. Return true if an element was removed, otherwise return false.
  • getRandom(): Return one stored element chosen uniformly at random from all stored occurrences.

Your design must handle duplicates correctly. Be prepared to explain important edge cases during deletion, especially when the element being removed is already the last element in the array, or when the value moved into the deleted slot is the same as the value being removed.