Katkat
Back

Randomized String Multiset With Average O(1) Insert, Remove and Weighted Random Pick

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Design a collection of strings that allows duplicates and supports insert, remove and a random pick in average constant time, where each stored occurrence is equally likely to be returned. It tests hash map and array layout, index bookkeeping on removal, and how string keys change the cost analysis.

Design a data structure that holds a collection of strings in which the same string may be stored several times, and that supports the following operations in average O(1) time each:

class RandomizedStringBag:
 def insert(self, val: str) -> bool: ...
 def remove(self, val: str) -> bool: ...
 def get_random(self) -> str: ...
  • insert(val) adds one occurrence of val, even if val is already present. It returns True if val was not present before the call, and False otherwise.
  • remove(val) removes one occurrence of val if there is one. It returns True if an occurrence was removed, and False if val was not present.
  • get_random() returns one stored element at random, with every stored occurrence equally likely: a string stored k times among n stored occurrences in total is returned with probability k / n.

The interviewer presented this as the familiar integer version of the problem with one difference: the elements are strings instead of numbers.

Clarifying Questions

  • What should get_random do when the collection is empty?
  • Does O(1) treat hashing and comparing a string as constant time, or should the analysis account for string length?
  • Can strings be long, and are heavy duplicates expected, so that memory per occurrence matters?
  • Will the structure be used from several threads at once?

Hints

Hint 1

Picking at random: Think about which layout makes choosing a uniformly random occurrence a single step, and what deleting from the middle of that layout would cost.

Hint 2

Finding an occurrence fast: To delete one occurrence of a value in constant time, you must already know where some occurrence of it is. Decide what to remember per distinct string, and what has to change when an element moves.

Follow-up questions

  • Change `get_random` so that every distinct string is equally likely, regardless of how many times it is stored.
  • Add `remove_all(val)`, which removes every occurrence of `val`. What does it cost?
  • The strings are long and heavily duplicated. How do you avoid storing a copy per occurrence?
  • Make the structure safe to use from several threads.