Katkat
Back

Design O(1) Randomized Multiset

LinkedInSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that supports efficient insertion, deletion, and uniform random sampling by combining dynamic arrays with hash maps to achieve constant time complexity.

Problem Statement

Design a data structure RandomizedMultiset that supports storing duplicate elements and provides efficient access to a random element. Your implementation must support the following operations in average O(1) time complexity:

  • insert(val): Inserts a value into the collection. Returns true if the collection did not already contain the value.
  • remove(val): Removes an instance of val from the collection if present. Returns true if the collection contained the specified element.
  • getRandom(): Returns a random element from the current collection. The probability of returning any element should be uniform based on the total number of items currently in the set.

Requirements

  • Use a dynamic array to store the elements to allow O(1) access by index.
  • Use a hash map to map each value to a set of indices where it exists in the array.
  • Ensure that when removing an element, you swap the target element with the last element in the array to maintain O(1) performance.

Example

# Initialization
rms = RandomizedMultiset()
rms.insert(1)  # returns True
rms.insert(1)  # returns True
rms.insert(2)  # returns True
rms.getRandom() # returns 1 or 2 with appropriate frequency
rms.remove(1)  # returns True
rms.getRandom() # returns 1 or 2

Edge Cases

  • Removing an element that does not exist.
  • Removing the last element in the array.
  • Handling sequences of operations that reduce the collection to a single element or empty.

Hints

Hint 1

Use a dynamic array (like a list) to store the elements and a hash map that maps each value to a set of indices where that value appears in the array.

Hint 2

When removing an element, swap it with the last element in the array to keep the array packed, then update the hash map entry for the swapped value.

Hint 3

Be careful to update the index of the swapped element in the hash map before removing the original index of the deleted element.

Follow-up questions

  • How would you modify the data structure if every inserted element had a TTL (Time-To-Live) and must be removed if a 'cleanUp' method is called after the TTL has expired?
  • If the 'getRandom' method needs to be weighted (i.e., some elements have a higher probability of being chosen), how would the design change?
  • How does the performance of this structure change in a multi-threaded environment, and what concurrency primitives would you use to ensure safety?