Skip to main content

1206. Design Skiplist

hard

Build a probabilistic multi-level linked list supporting search, add, and erase in O(log n) expected time. The skiplist is the elegant alternative to balanced trees — multiple linked-list lanes stacked on top of one another, with random level promotion as the only balancing trick.

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

Problem

Design a Skiplist without using any built-in libraries. A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists. Implement the Skiplist class: Skiplist() initializes the object. bool search(int target) returns true if target exists in the Skiplist or false otherwise. void add(int num) inserts the value num into the SkipList. bool erase(int num) removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine.

Constraints

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

Examples

Example 1

Input
["Skiplist","add","add","add","search","add","search","erase","erase","search"]
[[],[1],[2],[3],[0],[4],[1],[0],[1],[1]]
Output
[null,null,null,null,false,null,true,false,true,false]

Explanation: add(1), add(2), add(3); search(0)=false; add(4); search(1)=true; erase(0)=false (not present); erase(1)=true; search(1)=false (just erased).

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Each node has a value and a forward-pointer array of length equal to its randomly assigned level (1..MAX_LEVEL). Higher-level lanes skip more nodes — that's where the O(log n) comes from.

Hint 2

Searches start at the top-left sentinel and drop a level whenever the next node at the current level overshoots. Insertions remember the rightmost node visited on each level (the 'update' array) so you can splice in the new node at every promoted level.

Hint 3

Level promotion is random: keep flipping a coin (typically p = 0.5) and increment the new node's level on each heads, up to MAX_LEVEL. Expected average level is 1/(1−p) = 2 for p = 0.5.

Solution approach

Reveal approach

Multi-level linked list with random level promotion. Pick MAX_LEVEL ≈ log2(n_max) (16 is plenty for n ≤ 5·10^4) and p = 0.5. Each node carries val and a fixed-length forward[MAX_LEVEL] array of next-pointers. A header sentinel sits at the top-left with its full forward array initialized to null. The skiplist also tracks the current top level (the highest level with any non-null forward pointer). search(target): walk from header at the top level; at each level advance while forward[level] is non-null and forward[level].val < target; then drop a level. After level 0, the candidate is forward[0]; return whether it has val == target. add(num): same descent, but at every level record update[level] = the rightmost node where you dropped down. Randomly generate the new node's level by flipping coins. Splice: for level in 0..nodeLevel, newNode.forward[level] = update[level].forward[level]; update[level].forward[level] = newNode. erase(num): same descent recording update. If forward[0].val == num, unlink it at every level it appears on by setting update[level].forward[level] = node.forward[level]. Expected O(log n) per operation; space is O(n) expected because the level distribution is geometric with mean 2.

Complexity

Time
O(log n)
Space
O(n)

Related patterns

  • linked-list
  • design
  • probabilistic
  • multi-level-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Google

Practice these live with InterviewChamp.AI

Drill Design Skiplist and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →