How do you implement a skip list and explain its expected O(log N) behavior?

1. Question

You need an ordered dictionary that supports key lookup, insertion, deletion, and range scans. The data set grows dynamically, and the interviewer wants average operations near O(log N) without requiring an AVL or red-black tree. Design a skip list and analyze randomness, boundaries, and memory layout.

2. Constraints and clarifications

• Decide whether keys are unique; if not, define overwrite, counting, or stable ordering.
• Choose a maximum level and promotion probability p; build indexes upward from a bottom linked list.
• Search, insertion, and deletion maintain a predecessor for every level; range iteration follows the bottom list.
• Discuss the single-threaded structure first. Concurrency requires additional locking, versioning, or a proof for a lock-free algorithm.

3. Core idea

Each node owns a randomly sized array of forward pointers. Search starts at the head of the highest level: advance while the next key is below the target, otherwise descend one level. Insertion records predecessors, chooses a random height, and splices the node into each level. Deletion uses the same predecessor array to unlink it. Sparse upper levels give O(N) expected pointers and O(log N) expected search, insertion, and deletion.

4. Reference implementation

randomLevel(rng, p, maxLevel):
  level = 1
  while level < maxLevel and rng.uniform01() < p:
    level += 1
  return level

findPredecessors(key):
  update = array(maxLevel)
  node = head
  for level from maxLevel - 1 down to 0:
    while node.forward[level] != nil and node.forward[level].key < key:
      node = node.forward[level]
    update[level] = node
  return update

insert(key, value):
  update = findPredecessors(key)
  if update[0].forward[0].key == key:
    update[0].forward[0].value = value
    return
  node = Node(key, value, randomLevel(rng, p, maxLevel))
  for level in 0 .. node.height - 1:
    node.forward[level] = update[level].forward[level]
    update[level].forward[level] = node

Check for nil before reading a key and ensure the new height never exceeds maxLevel. Deletion reconnects every level that points to the target with its successor. If the highest level becomes empty, lower the active level count without moving nodes.

5. Complexity and worst case

With a fixed promotion probability and independent random source, level and path length are logarithmic in expectation and expected space is O(N). If randomness fails or an adversary can predict levels, the structure can degenerate into a linked list and operations become O(N). Use a high-quality random source, cap the height, rebuild periodically, or choose a deterministic balanced tree for adversarial workloads.

6. Verification and concurrency trade-offs

• Test ordered, duplicate, empty, and extreme keys for lookup, update, deletion, and range iteration.
• Measure height distribution, average path length, and pointer count across several N values.
• Replay random operation sequences against a reference ordered map and compare contents and order.
• For concurrency, explain lock granularity, logical deletion, memory reclamation, and ABA risk; wrapping pointer writes in one lock is not a lock-free design.

7. Common mistakes

• Implementing search without predecessor arrays, forcing insertion or deletion to rescan the list.
• Ignoring duplicate-key policy and producing unstable range order.
• Treating expected O(log N) as a worst-case guarantee without discussing randomness and adversarial input.
• Using a fixed-height array that wastes memory or allowing unbounded heights that overflow the array.

8. Interview scoring points

Searches from high levels downward

The candidate explains each level's advance condition, when to descend, and why the bottom list contains every element.

Maintains predecessors correctly

The candidate stores an update array for every level and handles overwrite, nil pointers, and shrinking the highest active level.

Explains probabilistic complexity

The candidate states expected O(log N) time, expected O(N) space, and the conditions that cause O(N) degeneration.

Identifies concurrency boundaries

The candidate discusses locks, versions, logical deletion, memory reclamation, and ABA instead of treating single-threaded code as concurrent.