Design Skiplist — Probabilistic Sorted Structure

Problem Statement#

Design a skip list (without using any built-in sorted container) that supports three operations: search(target) returns true if the target exists; add(num) inserts a number (duplicates allowed); erase(num) removes one occurrence of the number and returns true if found.

Constraints:

• 0 <= num, target <= 2 * 10^4
• At most 5 * 10^4 calls to search, add, and erase

Input:  add(1), add(2), add(3), search(0), add(4), search(1), erase(1), erase(1), search(1)
Output: false, true, true, false

Input:  add(1), add(1), erase(1), search(1)
Output: true

Why This Problem Matters#

Skip lists are one of the most elegant probabilistic data structures in computer science. Redis uses a skip list for its sorted set implementation (ZADD, ZRANGE), and LevelDB's memtable uses a skip list to maintain sorted key-value pairs before flushing to disk. Google's Bigtable and Apache Cassandra also use skip-list-like structures for their write buffers.

This problem appears in hard-level FAANG interviews because implementing a skip list from scratch demonstrates mastery of linked list manipulation, probabilistic analysis, and layered data structure design. Candidates who can implement this correctly signal they understand how production databases actually work—not just surface-level API usage.

Understanding skip lists also provides intuition for why balanced BSTs (AVL, Red-Black) and sorted arrays exist: they solve the same problem of O(log N) sorted access, each with different trade-offs in implementation complexity and constant factors.

The Core Insight#

A skip list maintains multiple levels of linked lists. Level 0 is a complete sorted linked list. Higher levels are "express lanes" where each node has a 50% chance of being promoted to the next level. This gives expected O(log N) height and O(log N) search time.

Search starts at the top-left and moves right while next.val < target, then drops down a level when it cannot move right. This simultaneously finds the correct position for search, add, and erase.

The update array tracks the rightmost node at each level that is to the left of the target position—these are the nodes whose next pointers must be updated during add and erase.

Visual Dry Run#

Search(5): start L3, drop to L2 (5 > head.next=null? drop), reach L0, find 5.

Solution (Optimal)#

import random
 
class SkiplistNode:
    def __init__(self, val, level):
        self.val = val
        self.next = [None] * level
 
class Skiplist:
    MAX_LEVEL = 16
 
    def __init__(self):
        self.head = SkiplistNode(-float('inf'), self.MAX_LEVEL)
        self.level = 1
 
    def _random_level(self):
        lvl = 1
        while random.random() < 0.5 and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl
 
    def _find_update(self, target):
        update = [self.head] * self.MAX_LEVEL
        cur = self.head
        for i in range(self.level - 1, -1, -1):
            while cur.next[i] and cur.next[i].val < target:
                cur = cur.next[i]
            update[i] = cur
        return update
 
    def search(self, target: int) -> bool:
        update = self._find_update(target)
        node = update[0].next[0]
        return node is not None and node.val == target
 
    def add(self, num: int) -> None:
        update = self._find_update(num)
        lvl = self._random_level()
        if lvl > self.level:
            for i in range(self.level, lvl):
                update[i] = self.head
            self.level = lvl
        node = SkiplistNode(num, lvl)
        for i in range(lvl):
            node.next[i] = update[i].next[i]
            update[i].next[i] = node
 
    def erase(self, num: int) -> bool:
        update = self._find_update(num)
        node = update[0].next[0]
        if not node or node.val != num:
            return False
        for i in range(self.level):
            if update[i].next[i] != node:
                break
            update[i].next[i] = node.next[i]
        while self.level > 1 and not self.head.next[self.level - 1]:
            self.level -= 1
        return True

class SkiplistNode {
    constructor(val, level) {
        this.val = val;
        this.next = new Array(level).fill(null);
    }
}
 
class Skiplist {
    constructor() {
        this.MAX = 16;
        this.level = 1;
        this.head = new SkiplistNode(-Infinity, this.MAX);
    }
 
    _randLevel() {
        let l = 1;
        while (Math.random() < 0.5 && l < this.MAX) l++;
        return l;
    }
 
    _findUpdate(target) {
        const u = new Array(this.MAX).fill(this.head);
        let c = this.head;
        for (let i = this.level - 1; i >= 0; i--) {
            while (c.next[i] && c.next[i].val < target) c = c.next[i];
            u[i] = c;
        }
        return u;
    }
 
    search(t) {
        const u = this._findUpdate(t);
        return u[0].next[0]?.val === t;
    }
 
    add(n) {
        const u = this._findUpdate(n);
        const l = this._randLevel();
        if (l > this.level) {
            for (let i = this.level; i < l; i++) u[i] = this.head;
            this.level = l;
        }
        const node = new SkiplistNode(n, l);
        for (let i = 0; i < l; i++) {
            node.next[i] = u[i].next[i];
            u[i].next[i] = node;
        }
    }
 
    erase(n) {
        const u = this._findUpdate(n);
        const node = u[0].next[0];
        if (!node || node.val !== n) return false;
        for (let i = 0; i < this.level; i++) {
            if (u[i].next[i] !== node) break;
            u[i].next[i] = node.next[i];
        }
        while (this.level > 1 && !this.head.next[this.level - 1]) this.level--;
        return true;
    }
}

Time: O(log N) expected for search, add, erase — worst case O(N) with adversarial randomness
Space: O(N log N) expected — each node spans O(log N) levels on average

Common Mistakes#

• Forgetting to shrink self.level after erase when top levels become empty—the skip list wastes time searching empty levels
• In add, not updating self.level before setting update[i] = self.head for new levels—causes incorrect update pointers at the new levels
• Breaking the erase loop too early: stop when update[i].next[i] != node, but level 0 must always be updated
• Using <= target instead of < target in the traversal—this causes skipping over duplicate values during search
• Not initialising update with the head sentinel—uniniialised pointers at unused levels cause null pointer exceptions

Interview Tips#

• Always explain the skip list structure visually: draw the levels with head sentinels before coding
• State the probabilistic guarantee: with MAX_LEVEL=16 and p=0.5, the structure supports 2^16 = 65536 elements at O(log N) guaranteed with high probability
• Mention Redis: "Redis sorted sets use a skip list, which is why I know this structure well"
• Highlight the update array pattern as the common thread through all three operations

Follow-up Questions#

• Why does Redis use a skip list instead of a balanced BST for sorted sets? (Skip lists are simpler to implement lock-free; BST rebalancing is notoriously hard to make concurrent)
• How would you make this skip list thread-safe? (Lock-free skip lists use CAS operations on next pointers; simpler approach uses a read-write lock)
• What is the expected height of a skip list with N elements? (log base 2 of N with high probability)
• How would you implement range queries (get all elements between a and b)? (Find update for a, then walk level 0 until val > b)
• What is the worst-case scenario for a skip list? (All nodes promoted to max level—O(N) per operation, same as a linked list)

Key Takeaways#

• A skip list provides O(log N) expected search, insert, and delete using probabilistic level assignment
• Each node has a random height: level 1 always, level 2 with probability 0.5, level 3 with probability 0.25, etc.
• The update array records the rightmost predecessor at each level—shared by search, add, and erase
• In erase, break the pointer-update loop as soon as update[i].next[i] != node (higher levels may not reference this node)
• Shrink self.level after erase to avoid wasteful traversal of empty top levels
• Redis sorted sets, LevelDB memtable, and Apache HBase all use skip lists in production
• The expected space is O(N log N) and worst-case time is O(N), but these rarely occur in practice with good randomness