Skip List Insert & Search
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.
ops = [["insert",5,1],["insert",3,2],["insert",8,0],["search",3],["search",4],["search",8]][True, False, True]- A node inserted at height
happears on levels0…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.
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.
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.
- 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 level0…hset the new node’s forward pointer toupdate[level].forward[level]and pointupdate[level].forward[level]at the new node. - A search succeeds iff, after descending to level 0, the very next node equals the target value.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.