Skip to main content

25. Design Skiplist

hardAsked at Redis

Implement a probabilistic skiplist supporting search, add and erase in O(log n) average; Redis loves it because the skiplist is the storage layer behind every ZSET in the engine.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement Skiplist with search(target) returning boolean, add(num) and erase(num) returning whether the value existed and was removed. All operations must run in O(log n) average. Do not use TreeSet or any sorted library.

Constraints

  • 0 <= num <= 2 * 10^4
  • Up to 5 * 10^4 calls

Examples

Example 1

Input
add(1); add(2); add(3); search(0)=false; add(4); search(1)=true; erase(0)=false; erase(1)=true; search(1)=false
Output
see explanation

Approaches

1. Sorted array

Binary-search-insert into a sorted JS array.

Time
O(n) per add/erase
Space
O(n)
// Use Array.findIndex + splice; works but O(n) shifts.

Tradeoff:

2. Probabilistic multi-level linked list

Each node holds an array of forward pointers, one per level. On add flip a coin to decide level (Redis uses 1/4 probability and a 32-level cap). Search walks levels top-down. Add/erase rewire forward pointers at each level. This is Redis ZSL_MAXLEVEL=32 verbatim.

Time
O(log n) avg
Space
O(n) avg, O(n log n) worst
const P = 0.25, MAX_LEVEL = 32;
class Skiplist {
  constructor() { this.head = { val: -1, next: new Array(MAX_LEVEL).fill(null) }; this.level = 0; }
  randomLevel() { let lv = 0; while (Math.random() < P && lv < MAX_LEVEL - 1) lv++; return lv; }
  search(target) {
    let cur = this.head;
    for (let i = this.level; i >= 0; i--) while (cur.next[i] && cur.next[i].val < target) cur = cur.next[i];
    cur = cur.next[0];
    return !!(cur && cur.val === target);
  }
  add(num) { /* find update[] per level, splice in a new node at randomLevel() */ }
  erase(num) { /* find update[] per level, unlink first occurrence, return true/false */ }
}

Tradeoff:

Redis-specific tips

Redis interviewers grade for naming the constants from t_zset.c: ZSKIPLIST_MAXLEVEL=32, ZSKIPLIST_P=0.25, the back-pointer-only-on-level-0 trick, and why skiplists beat balanced BSTs (range scans, simpler concurrency, smaller code).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Design Skiplist and other Redis interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →