Design O(1) insert/delete and frequency-weighted random
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Design a data structure that supports the following operations in **average** \(O(1)\) time:
1. `add(x) -> bool`
- Inserts value `x` into the collection.
- Returns `true` if `x` was **not already present** in the collection before this call; otherwise returns `false`.
- **Duplicates are allowed**.
2. `delete(x) -> bool`
- Removes **one occurrence** of value `x` from the collection (if present).
- Returns `true` if an occurrence was removed; otherwise returns `false`.
3. `random() -> int`
- Returns a random element from the collection such that the probability of returning a value is **proportional to its frequency**.
- Equivalently, if the multiset currently contains `N` total elements counting duplicates, `random()` should pick **uniformly among the N occurrences**.
## Example
If the collection contains `[5, 5, 7]`, then:
- `P(random() = 5) = 2/3`
- `P(random() = 7) = 1/3`
## Notes / Constraints
- You may assume values fit in 32-bit signed integers.
- Aim for **average** \(O(1)\) time per operation and \(O(N)\) space overall.
Quick Answer: This question evaluates data structure design skills around maintaining multiset state with average O(1) insertions and deletions while supporting frequency-weighted random sampling, testing concepts such as hashing, index management, and randomized selection under duplicates.
Implement a deterministic version of a frequency-weighted randomized multiset.
The collection stores every occurrence of a number in an internal dynamic array called `slots`.
- `add(x)`: append one occurrence of `x` to `slots`. Return `True` if `x` was not present before this operation, otherwise return `False`.
- `delete(x)`: remove one occurrence of `x`. If multiple copies of `x` exist, remove the most recently inserted remaining copy of `x`. To keep the operation O(1), remove it by swapping its slot with the last element of `slots` and then popping the last element. Return `True` if a copy was removed, otherwise `False`.
- `random(ticket)`: if the collection currently contains `m` total occurrences, return the value stored at index `ticket % m` in `slots`. If the collection is empty, return `None`.
Because each occurrence occupies its own slot, choosing a slot uniformly makes values appear with probability proportional to their frequency.
Given two arrays `operations` and `values`, process the operations in order and return a list of outputs for every operation.
Constraints
- 1 <= len(operations) == len(values) <= 2 * 10^5
- Each operation is one of "add", "delete", or "random"
- -10^9 <= values[i] <= 10^9