Problem framing
Design an ordered set/map — insert(key), search(key), delete(key), plus range queries — that stays O(log n) without a balanced BST's rotation logic. Tests whether you reach for randomization instead of strict invariants when rotations become a liability, and whether you can compose a class API on top of a structure that isn't a tree.
| Component | Role |
|---|---|
SkipListNode | value + forward[] array of next-pointers, one per level the node was promoted to |
SkipList | head sentinel spanning maxLevel, current level, insert/search/delete |
| Level promotion | Independent coin flip per insert (p = 0.5) decides how many levels a node joins |
Class design
SkipList
insert(key), search(key) -> bool, delete(key)
head: SkipListNode (sentinel, forward[] sized maxLevel)
level: int (highest level currently in use)
SkipListNode
value, forward: SkipListNode[]Search walks from head at the top level, moving right while the next node's value is still < target, then drops one level and repeats — same "search from the top, narrow down" shape as a B-tree, without the tree.
Why this over a balanced BST
A rotation touches nodes that can be arbitrarily far from the one being inserted, which is painful to make thread-safe without locking a wide swath of the structure. A skip list's insert only ever splices in nodes local to the insertion point at each level — no rotation propagating upward. That locality is the reason production systems reach for skip lists specifically under concurrent access: Redis's sorted set (ZSET) and several LSM-tree memtable implementations (LevelDB's original design, RocksDB's default) use a skip list instead of a red-black tree for exactly this property.
Concurrency angle (the actual interview differentiator)
| Approach | Trade-off |
|---|---|
| Single global lock | Simple, correct, kills concurrent throughput |
| Per-node/per-level fine-grained locks | Higher throughput; must lock top-down in a consistent order to avoid deadlock |
Lock-free (CAS on forward pointers) | Production-grade (this is roughly what Java's ConcurrentSkipListMap does); significant complexity, mention the existence rather than derive it live |
Naming why a skip list enables the middle and right options — "insert only touches local nodes, so a lock only needs to cover the levels being spliced, not the whole structure" — is the senior-level signal here, not the raw implementation.
Common pitfalls
Forgetting to splice a new/removed node into every level it spans, not just the base list — breaks the "each level is independently sorted" invariant search correctness depends on. Not capping maxLevel — an uncapped promotion probability can in principle allocate unboundedly many levels for one node; production implementations cap at log2(expected max n).
DSA crossover
The algorithmic mechanics — search/insert/delete derivation, the promotion-probability math, and hands-on practice via LeetCode's Design Skiplist — live in the DSA roadmap's Skip Lists & Ordered Structures subtopic. This page is the class-design and concurrency framing on top of that algorithm.
Where this goes next
Ring Buffer / Circular Queue moves from an ordered-set class to a fixed-capacity streaming buffer — a different composition of "simple primitives, O(1) guarantees."
Further Reading
Practice Tasks (Optional)
Design or implement locally in any language — no autograding. Focus on class structure, extensibility, and being able to explain trade-offs out loud.
- Design SkipList class and defend it over a balanced BST40m
Design the class API (insert, search, delete, node/level structure). Then argue, in three sentences, why you'd pick a skip list over a red-black tree specifically for a concurrent ordered set — name the property that makes fine-grained locking tractable.