Prompt and scope
Implement an ordered set of integer keys with search, insert, and delete. The structure should use expected O(log n) operations and avoid the rotations required by a balanced tree. State whether duplicates are rejected or counted; this article chooses a set, so inserting an existing key is a no-op.
The question appears in public interview reports and implementation discussions, including a Google interview prompt and a LeetCode interview post. The coding signal is maintaining multiple forward-pointer levels and proving their invariants, not memorizing a library class.
What the interviewer evaluates
- Whether you keep level zero as the complete sorted list and every higher level as a subsequence of it.
- Whether insertion and deletion update every predecessor level without losing the base-list link.
- Whether you distinguish expected
O(log n)from an unluckyO(n)operation and test random-level boundaries.
Redis uses a skip-list representation for one sorted-set encoding, while MIT’s algorithm notes describe the probabilistic analysis. Those are implementation and theory evidence; they do not imply that every workload should replace a tree with a skip list.
Clarifications before answering
- Set or multiset? A set rejects duplicate keys; a multiset needs a count or unique node identity.
- Do callers need rank or range queries? Rank needs span or width metadata; the base question needs membership only.
- Is deterministic replay required? Inject a seeded random source for tests, while production uses an unbiased generator.
- What is the memory limit? Each node has a variable number of forward pointers, so the level cap and probability affect memory.
A 30-second answer
“I keep a sentinel with a forward pointer for each level and a sorted level-zero list. Search starts at the highest level and moves while the next key is smaller; it records the last predecessor at every level. Insert chooses a random height, splices the new node after those predecessors, and does nothing for an existing key. Delete uses the same predecessor array and unlinks the target at every level where it appears, then lowers the active height when top lists become empty. With geometric height probability, search, insert, and delete are expected O(log n) and space is expected O(n); a pathological random sequence can still take O(n).”
Step-by-step deep answer
Step 1: Define the invariant.
Level zero contains every key in strictly increasing order. Level i + 1 is a subsequence of level i, and each node’s forward pointers are ordered by key. A sentinel has MAX_LEVEL pointers and no user key. The active level is the highest non-empty list.
Step 2: Search while collecting predecessors.
Start at the sentinel’s highest active level. Move forward while the next node exists and its key is less than the target. Drop one level and continue. Store the last node visited in update[i]; after level zero, update[0].next[0] is either the target or its insertion position.
Step 3: Insert with a random height.
Draw a geometric height, for example by repeatedly promoting with probability p = 1/2, capped at MAX_LEVEL. If the candidate at level zero has the key, return false. For every level below the new height, set the new node’s pointer to the predecessor’s next pointer, then point the predecessor at the new node. Extend the active level if needed.
type Node = { key: number; next: Array<Node | null> };
class SkipSet {
private readonly maxLevel = 16;
private readonly head: Node = { key: Number.NEGATIVE_INFINITY, next: [] };
private level = 1;
constructor() {
this.head.next = Array(this.maxLevel).fill(null);
}
private randomLevel(): number {
let h = 1;
while (h < this.maxLevel && Math.random() < 0.5) h += 1;
return h;
}
search(key: number): boolean {
let node = this.head;
for (let i = this.level - 1; i >= 0; i -= 1) {
while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
}
return node.next[0]?.key === key;
}
insert(key: number): boolean {
const update = Array<Node>(this.maxLevel);
let node = this.head;
for (let i = this.level - 1; i >= 0; i -= 1) {
while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
update[i] = node;
}
if (update[0].next[0]?.key === key) return false;
const height = this.randomLevel();
if (height > this.level) {
for (let i = this.level; i < height; i += 1) update[i] = this.head;
this.level = height;
}
const fresh: Node = { key, next: Array(height).fill(null) };
for (let i = 0; i < height; i += 1) {
fresh.next[i] = update[i].next[i];
update[i].next[i] = fresh;
}
return true;
}
delete(key: number): boolean {
const update = Array<Node>(this.maxLevel);
let node = this.head;
for (let i = this.level - 1; i >= 0; i -= 1) {
while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
update[i] = node;
}
const target = update[0].next[0];
if (!target || target.key !== key) return false;
for (let i = 0; i < this.level; i += 1) {
if (update[i].next[i] !== target) break;
update[i].next[i] = target.next[i] ?? null;
}
while (this.level > 1 && !this.head.next[this.level - 1]) this.level -= 1;
return true;
}
}Step 4: Delete every occurrence of the target node.
The predecessor array identifies the target’s predecessor at each level. Unlink only levels where update[i].next[i] is that target; higher levels may not contain it. Afterwards, reduce the active level while the sentinel’s top pointer is empty.
Step 5: Analyze complexity and memory.
With promotion probability p strictly between zero and one, expected height is constant and expected search path length is logarithmic. Search, insert, and delete are expected O(log n); a bad random sequence has O(n) worst case. Expected pointer count is n/(1-p) up to constants, so p = 1/2 trades roughly two pointers per node for shorter paths.
Step 6: Test structure, randomness, and boundaries.
Use a seeded generator in tests. Check empty search/delete, first and last keys, duplicates, deleting the only node, deleting across levels, negative values, and repeated insert/delete cycles. After every operation, traverse level zero and compare with a reference Set; verify each higher level is sorted and every node also appears at level zero. Run many seeds to catch height and pointer corruption.
High-quality sample answer
“I model a set with a sentinel and a sorted level-zero chain. Every higher level is a subsequence of level zero. Search descends from the highest active level and records the predecessor at each level. Insert rejects an existing key, chooses a geometric random height, and splices the node after those predecessors. Delete finds the same predecessor array, unlinks the target from every level where it appears, and trims empty top levels.
The operations are expected O(log n) with O(n) expected space, but O(n) worst-case time remains possible when random heights are unlucky. I would use a seeded random source for deterministic tests, compare level zero with a reference set after every operation, and assert sortedness plus subsequence invariants for all upper levels.”
Common mistakes
- Updating only level zero → upper-level search can skip or retain the key → splice or unlink every level containing the node.
- Treating the random height as a guarantee → a pathological sequence can produce a linear path → state expected and worst-case bounds.
- Allowing duplicate nodes unintentionally → search and delete semantics become ambiguous → choose set or multiset behavior before coding.
- Failing to trim empty top levels → searches inspect stale levels and bookkeeping drifts → lower the active level after deletion.
- Testing only final membership → a corrupted upper pointer can remain hidden → check ordering and subsequence invariants after every operation.
Follow-ups and responses
Follow-up 1: How would you support duplicate keys?
Choose a contract. A multiset can store a count in each key node, making repeated insert and delete update the count, or store a unique sequence number in the comparison key. Count nodes when memory permits; unique identities are useful when deleting one specific occurrence.
Follow-up 2: How do you add rank queries?
Store a span or width beside every forward pointer. During search, accumulate spans as you move right; insertion and deletion update the affected spans at every level. The simple set implementation does not have enough metadata to answer rank in logarithmic time.
Follow-up 3: When would you choose a balanced tree instead?
Use a balanced tree when worst-case bounds, deterministic iteration shape, or rich ordered operations matter more than implementation simplicity. A skip list fits when expected logarithmic performance, easy concurrent variants, or a pointer-based ordered index is acceptable. Measure memory overhead and workload rather than claiming one structure is universally faster.