Coding Interview: How Do You Implement a Sparse Set with O(1) Operations?

Problem and scope

Given a bounded integer universe [0, U), implement a set with insert(x), remove(x), contains(x), clear(), and iteration over current members. The first four operations must be worst-case O(1); iteration takes O(k) for k current members. Duplicates are rejected, and removing a missing value is a no-op.

Public interview records include this form of question in a Pure Storage discussion. The core test is the dense/sparse-array invariant, not memorizing a library class.

What the interviewer is testing

• Whether you state that a fixed universe is required; the O(1) claim does not extend to arbitrary integers for free.
• Whether you maintain dense[sparse[x]] == x and use it to prevent stale-index false positives.
• Whether deletion swaps with the last element, keeping the dense prefix contiguous and iteration at O(k).
• Whether you state O(U) space and recognize when a hash set or bitmap is more appropriate.

Clarifications before coding

1. Is U known, and can the solution allocate two arrays of length U? This is the resource precondition.
2. Must iterate() be sorted? This design returns all members but does not promise order.
3. Are stable iterators or concurrent access required? Those requirements change swap-delete and synchronization semantics.
4. Must clear() avoid scanning U? The prompt requires constant time, so it only resets size.

30-second answer

“I keep a sparse index array of length U, a dense array of length U, and the current size. An element x is present exactly when sparse[x] < size and dense[sparse[x]] == x. Insert writes x at dense[size] and records the index; remove overwrites its slot with the last element and fixes that element’s index; clear only sets size to zero. The four core operations are worst-case O(1), iteration over the dense prefix is O(k), and space is O(U).”

Step-by-step deep dive

Step 1: State the invariant.

dense[0..size) contains every member exactly once. For a member x, sparse[x] is its position in dense and dense[sparse[x]] == x. A non-member may retain an old sparse value, so contains cannot check only whether the index is in range.

Step 2: Lookup and insertion.

contains(x) checks 0 <= x < U, then validates sparse[x] < size and the reverse link. Insert calls contains first; if absent, it writes x to dense[size], sets sparse[x] = size, and increments size.

Step 3: Swap-delete.

If x is at position i, let last = dense[size - 1]. Write last to dense[i], update sparse[last] = i, and decrement size. There is no need to clear sparse[x]: after size changes, the reverse-link check makes the stale entry invalid. Deleting the last element follows the same logic.

Step 4: Constant-time clear and linear iteration.

clear() sets size = 0; old array contents are no longer read as members. Iteration scans only dense[0] through dense[size - 1], so it costs O(k), not O(U).

Step 5: Complexity and boundaries.

contains, insert, remove, and clear are worst-case O(1); iteration is O(k); space is O(U). GCC documents the representation as useful for a fixed universe and cache-friendly enumeration. If the universe is unknown, must grow, or is too large for memory, a hash set or bitmap may fit better.

Step 6: Test the invariant.

Compare every random operation with a reference Set. Cover an empty set, duplicate insertion, removing a missing value, removing a middle and last element, reuse after clear, and values 0 and U-1. After each operation, verify that the dense prefix has no duplicates and every member’s reverse link is valid.

High-quality sample answer

“The bounded universe [0, U) lets me trade two arrays for deterministic constant-time operations. Dense stores a compact prefix of current members, while sparse maps a value back to its dense index. Membership must check the bounds, index < size, and reverse link; checking the sparse number alone is unsafe. Remove swaps in the last element and updates its sparse index, while clear resets only size. Updates and lookup are worst-case O(1), iteration is O(k), and space is O(U). If the universe is uncontrolled, I would choose a hash set or bitmap instead.”

Common mistakes

• Checking only sparse[x] < size → a missing value can retain a plausible index → also check dense[sparse[x]] == x.
• Shifting all later elements on removal → removal becomes O(U) or O(k) → swap with the last element.
• Filling arrays during clear → clear becomes O(U) → reset only size.
• Ignoring the bounded universe → out-of-bounds access or unacceptable memory → confirm [0, U) and capacity first.
• Calling iteration O(1) → obtaining a view is constant time, but consuming all members is O(k) → separate the two costs.

Follow-up questions and answers

Follow-up 1: How would you support arbitrary integers?

Coordinate-compress the values into [0, U) first. If the value domain keeps growing or cannot be scanned up front, a hash set is more natural, but its constant-time claim is amortized or expected rather than the worst-case guarantee in this prompt.

Follow-up 2: How would you preserve iteration order?

Swap-delete changes the dense order. Preserving insertion order requires an additional linked list or stable array, which changes deletion and space costs. Confirm whether order is part of the interface contract before adding it.

Follow-up 3: When would you choose a bitmap?

Choose a bitmap when membership is the only operation, the universe is moderate, and one bit per value matters. Choose a sparse set when fast enumeration is also important; the right choice depends on U, cardinality, and access patterns.