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 xAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at xAI during technical interviews.

Design O(1) random-sampling set | xAI Coding Question

Quick Overview

This question evaluates a candidate's competency in data-structure design, randomized algorithms, and algorithmic complexity analysis within the Coding & Algorithms domain, with a focus on achieving expected O(1) operations for insert, remove, and uniform sampling.

Design O(1) random-sampling set

Company: xAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Design a data structure that supports insert(x), remove(x), and get_random() that returns a uniformly random element among the present items, all in expected O( 1) time. Detail the algorithms and data structures you would use, how you handle deleting the last element and gaps, and how you would test the uniformity of get_random(). Discuss extensions such as supporting duplicates or thread-safety and the impact on complexity.

Quick Answer: This question evaluates a candidate's competency in data-structure design, randomized algorithms, and algorithmic complexity analysis within the Coding & Algorithms domain, with a focus on achieving expected O(1) operations for insert, remove, and uniform sampling.

Implement a simulation of a randomized set data structure with no duplicate values. It must support insert(x), remove(x), and get_random() in expected O(1) time. To make testing deterministic, each get_random operation is given an integer index r; your get_random should return the element currently stored at index r in the internal dense array. In a real randomized set, r would be chosen uniformly at random from 0 to current_size - 1, which makes every present item equally likely. You must maintain the dense array using the standard swap-with-last deletion strategy so removals do not leave gaps.

Constraints

0 <= len(commands) == len(values) <= 200000
commands[i] is one of "insert", "remove", or "get_random"
-1000000000 <= values[i] <= 1000000000 for insert/remove operations
For every get_random operation, the set is non-empty and 0 <= values[i] < current set size
Duplicate values are not stored; inserting an existing value must not change the set

Examples

Input: (["insert", "insert", "get_random", "remove", "get_random", "insert", "remove"], [1, 2, 0, 1, 0, 2, 3])

Expected Output: [1, 1, 1, 1, 2, 0, 0]

Explanation: Insert 1 and 2. Random index 0 returns 1. Removing 1 swaps 2 into the only slot, so the next random index 0 returns 2. Inserting duplicate 2 fails, and removing absent 3 fails.

Input: ([], [])

Expected Output: []

Explanation: No operations produce no results.

Input: (["insert", "get_random", "remove", "insert", "insert", "remove", "get_random"], [10, 0, 10, 20, 30, 30, 0])

Expected Output: [1, 10, 1, 1, 1, 1, 20]

Explanation: This checks singleton behavior and deleting the last element. After removing 30 from [20, 30], only 20 remains.

Input: (["insert", "insert", "insert", "insert", "remove", "get_random", "get_random", "remove", "get_random"], [4, 5, 6, 7, 5, 1, 2, 7, 1])

Expected Output: [1, 1, 1, 1, 1, 7, 6, 1, 6]

Explanation: After inserting [4,5,6,7], removing 5 swaps 7 into index 1, making the dense array [4,7,6]. Random indices 1 and 2 return 7 and 6. Removing 7 then swaps 6 into index 1.

Input: (["insert", "insert", "insert", "get_random", "remove", "get_random", "insert", "get_random"], [-1, 0, -1, 1, -1, 0, -2, 1])

Expected Output: [1, 1, 0, 0, 1, 0, 1, -2]

Explanation: Negative numbers and zero are valid. The duplicate insert of -1 fails. After removing -1, 0 remains; then -2 is inserted at index 1.

Input: (["remove", "insert", "insert", "remove", "remove", "insert", "get_random"], [42, 1000000000, -1000000000, 42, 1000000000, -1000000000, 0])

Expected Output: [0, 1, 1, 0, 1, 0, -1000000000]

Explanation: Removing absent values returns 0. Boundary integer values are supported. After removing 1000000000, -1000000000 is swapped into index 0; inserting it again fails as a duplicate.

Solution

def solution(commands, values):
    items = []
    index = {}
    results = []

    for cmd, arg in zip(commands, values):
        if cmd == "insert":
            if arg in index:
                results.append(0)
            else:
                index[arg] = len(items)
                items.append(arg)
                results.append(1)

        elif cmd == "remove":
            if arg not in index:
                results.append(0)
            else:
                remove_idx = index[arg]
                last_value = items[-1]

                items[remove_idx] = last_value
                index[last_value] = remove_idx

                items.pop()
                del index[arg]
                results.append(1)

        elif cmd == "get_random":
            results.append(items[arg])

        else:
            raise ValueError("unknown command: " + str(cmd))

    return results

Time complexity: O(q) total for q operations; each insert, remove, and get_random operation runs in expected O(1) time.. Space complexity: O(m) auxiliary space for m currently stored elements, plus O(q) space for the returned results..

Hints

A dynamic array gives O(1) access by random index, but cannot remove arbitrary elements in O(1) unless you avoid preserving order.
Keep a hash map from value to its index in the array. To remove a value, move the last array element into the removed value's slot, update that moved element's index, then pop the last position.

Quick Overview