Skip List (Go)
Topics: skip list, probabilistic ordered map, range scan
Problem
Implement a skip list — a probabilistic ordered map with O(log n) expected Insert/Get and
ordered range scans. It's the structure behind Redis sorted sets and LevelDB's memtable, and
a popular alternative to balanced trees because there's no rotation/rebalancing.
func New() *SkipList
func (s *SkipList) Get(key int) (int, bool)
func (s *SkipList) Insert(key, val int)
func (s *SkipList) Range(lo, hi int) []Pair // ascending, lo <= key <= hi
Each node gets a random tower height; the higher levels are "express lanes" that skip over many
nodes, so search drops down level by level.
Insert adds or updates a key. Record, per level, the last node before the key (the update
path), give the new node a random height (randLevel, provided), splice it in at each of its
levels, and raise the list's level if its tower is the tallest so far.Get searches from the top level down.Range finds the first node >= lo, then walks level 0 until > hi.
Key concepts
- Towers + express lanes: ~½ of nodes reach level 2, ~¼ level 3, … giving logarithmic search
without any rebalancing.
- The update path: the array of "where we dropped down" at each level is exactly where to splice
the new node.
- Deterministic by design here: a fixed-seed xorshift drives the coin flips so tests are stable;
correctness never depends on the randomness, only performance.
The node type, Pair, New, and randLevel are provided; you implement Get, Insert, Range.
Run
go test -v ./challenges/skip-list/go/
Sign in to submit your solution.