How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at LinkedIn.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at LinkedIn during technical interviews.

Design a Randomized Multiset | LinkedIn Coding Question

Quick Overview

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.

Design a Randomized Multiset

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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 function `solution(operations, values, seed)` that simulates a multiset of integers supporting duplicates. The multiset must support these operations in expected O(1) time: - `insert(val)`: Add one occurrence of `val`. Return `True` if `val` was not already present in the multiset, 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 from all stored occurrences, so duplicates count multiple times. For deterministic judging, model the structure exactly as follows: 1. Keep a dynamic array `data` of all stored occurrences. 2. For each value, keep an index list of all positions where that value appears in `data`. 3. When `remove(val)` is called and multiple occurrences exist, remove the occurrence whose array index is stored at the end of `val`'s index list. 4. During deletion, swap the last array element into the removed slot if needed, and update all bookkeeping in O(1). The per-value index lists do not need to stay sorted. For reproducible `getRandom()` results, do not use a library RNG. Instead maintain an integer `state`, initially equal to `seed`. - If the collection is empty, `getRandom()` returns `None`. - Otherwise update `state = (state * 1103515245 + 12345) % (2**31)`. - Return `data[state % len(data)]`. Return a list containing the result of every operation in order.

Constraints

0 <= len(operations) <= 2 * 10^5
len(operations) == len(values)
Each `operations[i]` is one of `insert`, `remove`, or `getRandom`
For `insert` and `remove`, `values[i]` is an integer in the range [-10^9, 10^9]
For `getRandom`, `values[i]` is `None`
0 <= seed < 2^31

Examples

Input: (["insert", "insert", "insert", "getRandom", "remove", "getRandom"], [1, 1, 2, None, 1, None], 1)

Expected Output: [True, False, True, 1, True, 2]

Explanation: After the three inserts, `data = [1, 1, 2]`. The first generator state picks index 0, so `getRandom()` returns 1. `remove(1)` deletes the tracked occurrence at index 1 and swaps 2 into that slot, leaving `data = [1, 2]`. The next generator state picks index 1, so the final `getRandom()` returns 2.

Input: (["getRandom", "remove", "insert", "getRandom", "remove", "getRandom"], [None, 5, -3, None, -3, None], 0)

Expected Output: [None, False, True, -3, True, None]

Explanation: The multiset starts empty, so the first `getRandom()` returns `None`. Removing 5 fails. After inserting -3, the next `getRandom()` must return -3 because it is the only stored value. Removing -3 empties the multiset again.

Hints

A plain set is not enough because duplicates matter. Think about storing every occurrence in an array so `getRandom` can choose by index.
To remove in O(1), swap the last array element into the deleted slot. An extra mapping from array index to its position inside that value's index list lets you update the moved element in O(1).