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

What role is this question designed for?

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

Design set with O(1) random access | Google Coding Question

Design set with O(1) random access

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design a data structure ("FancySet") that stores unique integers and supports the following operations, each in average O(1) time: - `add(x)`: Insert value `x` if it is not already present. Return whether the insert happened. - `delete(x)`: Remove value `x` if it exists. Return whether a deletion happened. - `getRandom()`: Return a uniformly random element currently in the set. Requirements / follow-ups: - All operations should be average O(1). - Handle corner cases such as calling `getRandom()` on an empty set (define and justify behavior). - Discuss how you would make this data structure thread-safe. Compare using a single lock for the whole set vs finer-grained locking (e.g., element-level locks), and explain trade-offs.

Quick Answer: This question evaluates skill in designing a composite data structure that supports average O(1) insertion, deletion, and uniform random access, and tests understanding of hashing, indexing, randomness, and concurrency control.

Design a data structure called FancySet that stores unique integers and supports these operations in average O(1) time: add(x), delete(x), and getRandom(). For this coding problem, implement a function `solution(operations, values, seed)` that simulates a newly created empty FancySet and returns the result of every operation. Use the standard dynamic-array + hash-map behavior: - Store current elements in an array-like list. - Store each element's current index in a hash map. - When deleting an element that is not at the end of the list, move the last element into the removed slot, then pop the last slot. To make test cases deterministic, `getRandom()` does not use the language's built-in RNG. Instead, keep an internal 32-bit state initialized to `seed`. When `getRandom()` is called on a non-empty set, update the state with: `state = (1664525 * state + 1013904223) mod 2^32` and return the element at index `state % current_size` from the current internal list. If `getRandom()` is called on an empty set, return `None` and do not advance the state. In a real interview, picking a random index from the array gives uniform random access; the fixed generator above is only for reproducible grading. Follow-up discussion (not graded by the code runner): explain how you would make FancySet thread-safe, and compare using one lock for the whole structure versus finer-grained locking.

Constraints

1 <= len(operations) <= 2 * 10^5
len(values) == len(operations)
Each operation is one of 'add', 'delete', or 'getRandom'
For 'add' and 'delete', values[i] contains exactly one integer; for 'getRandom', values[i] is []
-10^9 <= x <= 10^9
All operations should run in O(1) average time

Examples

Input: (['add','add','getRandom','delete','getRandom','add','getRandom'], [[1],[2],[],[1],[],[2],[]], 7)

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

Explanation: After inserting 1 and 2, the first deterministic random choice picks index 0, so it returns 1. Deleting 1 leaves only 2. Adding 2 again fails because it is already present.

Input: (['getRandom','add','add','delete','delete','getRandom'], [[],[5],[5],[7],[5],[]], 1)

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

Explanation: Calling getRandom on an empty set returns None. Adding 5 twice inserts it only once. Deleting 7 fails because it is not present. After deleting 5, the set becomes empty again.

Input: (['add','add','add','delete','delete','getRandom'], [[-1],[10],[4],[10],[4],[]], 99)

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

Explanation: Deleting 10 swaps 4 into its slot. Deleting 4 after that checks whether the moved index was updated correctly. Only -1 remains, so getRandom returns -1.

Input: (['getRandom','add','add','getRandom','delete','getRandom'], [[],[8],[9],[],[8],[]], 1)

Expected Output: [None, True, True, 8, True, 9]

Explanation: The first getRandom is on an empty set, so it returns None and does not advance the random state. The next getRandom on [8, 9] therefore uses the initial seed and picks 8. After deleting 8, only 9 remains.

Input: (['add','add','add','getRandom','delete','getRandom'], [[4],[5],[6],[],[5],[]], 2)

Expected Output: [True, True, True, 6, True, 4]

Explanation: With seed 2, the first random index for [4, 5, 6] is 2, so it returns 6. Deleting 5 swaps 6 into index 1, leaving [4, 6]. The next deterministic random choice picks index 0, so it returns 4.

Hints

You need both fast membership/index lookup and fast access by numeric position. What two data structures combine to give that?
Deleting from the middle of an array is expensive unless you replace the removed element with the last element and update that last element's stored index.

Quick Overview

This question evaluates skill in designing a composite data structure that supports average O(1) insertion, deletion, and uniform random access, and tests understanding of hashing, indexing, randomness, and concurrency control.