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 O(1) insert/delete and frequency-weighted random

Quick Overview

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.

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
Target complexity is O(1) average time per operation

Examples

Input: (["add", "add", "add", "random", "delete", "random"], [5, 10, 5, 2, 5, 1])

Expected Output: [True, True, False, 5, True, 10]

Explanation: After inserting 5, 10, and 5, the internal slots are [5, 10, 5]. random(2) returns slots[2] = 5. delete(5) removes the most recently inserted remaining 5, leaving [5, 10]. random(1) then returns 10.

Input: (["add", "add", "add", "delete", "random", "add", "random"], [1, 2, 1, 2, 1, 3, 4])

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

Explanation: Deleting 2 removes it from the middle, so the last 1 is swapped into its slot. The structure becomes [1, 1], so random(1) returns 1. After adding 3, random(4) uses 4 % 3 = 1, which is still 1.

Input: (["delete", "random", "add", "add", "random", "delete", "random", "delete", "random"], [7, 0, -1, -1, 3, -1, 0, -1, 5])

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

Explanation: This checks edge cases: deleting a missing value, calling random on an empty collection, handling duplicates, and storing negative numbers.

Input: (["add", "add", "add", "add", "add", "delete", "delete", "random", "delete", "random"], [1, 2, 1, 3, 1, 2, 3, 2, 1, 1])

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

Explanation: After deleting 2, the newest 1 is swapped forward, which means the per-value position list for 1 is no longer sorted by slot index. A correct O(1) solution must still update bookkeeping properly when deleting 1 later.

Solution

def solution(operations, values):
    if len(operations) != len(values):
        raise ValueError("operations and values must have the same length")

    positions = {}
    data = []
    result = []

    for op, val in zip(operations, values):
        if op == "add":
            if val not in positions:
                positions[val] = []
            existed = len(positions[val]) > 0
            positions[val].append(len(data))
            data.append([val, len(positions[val]) - 1])
            result.append(not existed)

        elif op == "delete":
            if val not in positions or not positions[val]:
                result.append(False)
                continue

            remove_idx = positions[val].pop()
            last_val, last_pos = data[-1]
            last_idx = len(data) - 1

            if remove_idx != last_idx:
                data[remove_idx] = [last_val, last_pos]
                positions[last_val][last_pos] = remove_idx

            data.pop()

            if not positions[val]:
                del positions[val]

            result.append(True)

        elif op == "random":
            if not data:
                result.append(None)
            else:
                idx = val % len(data)
                result.append(data[idx][0])
        else:
            raise ValueError("Unknown operation: " + str(op))

    return result

Time complexity: O(n) total for n operations, which is O(1) average per operation. Space complexity: O(n).

Hints

If every occurrence is stored in an array, then frequency-weighted random becomes choosing one array slot.
For O(1) deletion, swap the removed slot with the last slot. To update bookkeeping in O(1), store for each slot both its value and where that slot is recorded inside that value's position list.

Quick Overview