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

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: ```python 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. ```hint 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 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. ``` ### 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? ### What a Strong Answer Covers - A layout in which `get_random` picks a uniformly random position, and removal fills the gap without shifting elements - Per-value bookkeeping that finds an occurrence and updates the moved element's position in O(1), including when the removed occurrence is the last element or the moved element has the same value - Correct return values, and a short argument that the sampling probability is k / n - A complexity analysis that accounts for hashing strings, and the memory cost per occurrence - Edge cases: an empty collection, removing an absent value, removing the last occurrence of a value ### 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.