CODING CHALLENGE · N°46

Skip List Insert & Search

Hard Data StructuresLinked ListSearch

A skip list gives you O(log n) search and insert with nothing but linked lists and a coin flip — the probabilistic structure behind Redis sorted sets and LevelDB’s memtable. Express lanes on top let you skip over most nodes. Here the node heights are given, so it’s fully deterministic. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement a skip list supporting insert(value, height) and search(value). A skip list is a set of sorted linked lists stacked in levels: level 0 holds every node; each higher level is an "express lane" holding a subset. Normally the height of a new node is random; here the height is given so the result is deterministic. You get a list of ops like ["insert", 5, 1] (value 5 at height 1, i.e. present on levels 0 and 1) and ["search", 5]. Return the list of boolean results of every search.

EXAMPLE 1

Input ops = [["insert",5,1],["insert",3,2],["insert",8,0],["search",3],["search",4],["search",8]]

Output [True, False, True]

search descends the express lanes, then confirms on level 0

CONSTRAINTS

A node inserted at height h appears on levels 0…h (so height 0 = level 0 only).
Within every level the nodes stay sorted by value — insert into the correct position on each of its levels.
Search starts at the top level and, at each level, moves right while the next value is smaller than the target, then drops down a level; the target is present iff the level-0 successor equals it.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement skiplist_ops(ops): keep a head sentinel with forward pointers per level. To insert, record the rightmost node you pass on each level (the "update" path), then splice the new node in on levels 0…height. To search, descend the same way and check the level-0 successor.

HINTS — 4 IDEAS

Use a fixed maximum number of levels (e.g. 16). The head is a sentinel whose forward[i] points to the first node on level i.
For both insert and search, walk from the top level down: at each level advance while next.value < target, then drop down — recording where you stopped on each level (the "update" array) for insert.
To insert at height h, for each level 0…h set the new node’s forward pointer to update[level].forward[level] and point update[level].forward[level] at the new node.
A search succeeds iff, after descending to level 0, the very next node equals the target value.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

A skip list stacks sorted linked lists; higher levels skip more nodes, giving O(log n) search. To insert, walk down from the top level, recording the predecessor at each level where you drop down. Flip a coin to pick the new node’s height (halving the probability per level), then splice it in at every level up to that height, updating the recorded predecessors.

Complexity

Expected O(log n) for search and insert; expected O(n) space.

Common mistakes

Not tracking the update/predecessor pointer for each level before splicing.
A wrong height distribution — each extra level should be half as likely.
Forgetting to raise the list’s max level when a tall node is inserted.

Where this shows up

Skip lists are a simpler, more concurrency-friendly alternative to balanced trees — Redis sorted sets are built on them. Their randomized balancing achieves the same O(log n) as AVL or red-black trees without any of the rotation bookkeeping, which is why they are popular in lock-free designs.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA