Design Skiplist — Solution in Python, Java & C++
Design Skiplist solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on linked list and design.
Design Skiplist is a hard coding problem on linked list and design, asked in Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Linked List, Design
- Asked at: Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Implement a skiplist without using any built-in ordered library. A skiplist keeps its values in sorted linked lists stacked in levels: the bottom level holds every value, and each value is also copied up into the next level with probability 1/2. A search starts at the top level and drops down a level whenever the next value would overshoot, so search, add and erase all take O(log n) expected time.
The same value may be stored more than once. Write the class Skiplist:
Skiplist()creates an empty skiplist.boolean search(int target)returns whethertargetis stored.void add(int num)storesnum(another copy if it is already there).boolean erase(int num)removes one copy ofnumand returnstrue, or returnsfalse(and changes nothing) ifnumis not stored.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["Skiplist","add","add","add","search","erase","search","erase","search","erase","search"]
[[],[7],[7],[3],[7],[7],[7],[7],[7],[7],[3]]
Output: [null,null,null,null,true,true,true,true,false,false,true]
Explanation: 7 is stored twice. The first erase removes one copy, so 7 is still found; the second removes the other. A third erase finds nothing to remove. 3 was never touched.
Example 2
Input: ["Skiplist","search","add","add","search","erase","search"]
[[],[0],[0],[20000],[20000],[0],[0]]
Output: [null,false,null,null,true,true,false]
Explanation: 0 and 20000 are the smallest and largest values allowed.
Constraints
0 <= num, target <= 2 * 10^4At most 5 * 10^4 calls are made in total to search, add and erase
Hints for Design Skiplist
Hint 1
Start from a sorted linked list: search is O(n) because you can only step one node at a time. Add express lanes — higher levels that skip over many nodes.
Hint 2
Give each new node a random height: level 1 always, and each further level with probability 1/2 (up to a cap such as 16). A head node with the full height starts every level.
Hint 3
All three operations begin the same way: from the top level down, move right while the next value is smaller than the key, and remember the last node visited on each level. Those are the nodes whose
nextpointers an insertion or deletion rewires.
How to solve Design Skiplist
A skiplist is a sorted linked list with probabilistic express lanes. Walking from the top lane down, every operation finds, on each level, the last node before the key — the "update path" — in O(log n) expected steps; inserting or deleting a node is then only a matter of splicing it into or out of those lanes.
Approach
- Keep a head node with
L = 16forward pointers (enough for far more than 5 · 10^4 values). path(key): start at the head on levelL - 1; on each level move right while the next node's value is< key, record the current node aspath[level], then go down a level.search(target): the node afterpath[0]on level 0 is the first value>= target; report whether it equalstarget.add(num): pick a heighth(1, plus one more level with probability 1/2 each time, at mostL). For levels0..h-1, setnode.next[lv] = path[lv].next[lv]andpath[lv].next[lv] = node.erase(num): letnodebe the node afterpath[0]on level 0; if it is missing or holds another value, returnfalse. Otherwise, on each of its levels, setpath[lv].next[lv] = node.next[lv], and returntrue.
Why it works
Every level is a sorted sub-list of the level below, so moving right while values are smaller never skips a value >= key, and dropping a level only refines the position; path[0] is therefore the last node of the whole list below key. Because heights double the gap between express stops on average, each level is crossed in O(1) expected steps, giving O(log n) expected work. With duplicates, the node after path[0] is the first copy, and on each of its levels it is also the first node >= num, so path[lv].next[lv] is exactly that node.
Complexity
- Time —
O(log n) expected per operation - Space —
O(n) expected (about two pointers per value)
Pitfalls
- Use strict
<while walking right; with<=, a search would step past the copies it is looking for. eraseremoves one copy only and must reportfalsewithout touching the list when the value is absent.- The coin flips only affect speed: the stored values, and so every answer, are the same whatever the random heights are.
Reference solution
Python
import random
class SkipNode:
__slots__ = ("value", "nxt")
def __init__(self, value, height):
self.value = value
self.nxt = [None] * height
class Skiplist:
LEVELS = 16
def __init__(self):
self.head = SkipNode(-1, self.LEVELS)
def _path(self, key): # on every level, the last node with value < key
path = [None] * self.LEVELS
cur = self.head
for lv in range(self.LEVELS - 1, -1, -1):
while cur.nxt[lv] is not None and cur.nxt[lv].value < key:
cur = cur.nxt[lv]
path[lv] = cur
return path
def search(self, target: int) -> bool:
node = self._path(target)[0].nxt[0]
return node is not None and node.value == target
def add(self, num: int) -> None:
path = self._path(num)
height = 1
while height < self.LEVELS and random.random() < 0.5:
height += 1
node = SkipNode(num, height)
for lv in range(height):
node.nxt[lv] = path[lv].nxt[lv]
path[lv].nxt[lv] = node
def erase(self, num: int) -> bool:
path = self._path(num)
node = path[0].nxt[0]
if node is None or node.value != num:
return False
for lv in range(len(node.nxt)):
if path[lv].nxt[lv] is node:
path[lv].nxt[lv] = node.nxt[lv]
return TrueJava
class Skiplist {
private static final int LEVELS = 16;
private static class Node {
int value;
Node[] nxt;
Node(int value, int height) { this.value = value; nxt = new Node[height]; }
}
private final Node head = new Node(-1, LEVELS);
private final Random rnd = new Random();
public Skiplist() {
}
private Node[] path(int key) { // on every level, the last node with value < key
Node[] path = new Node[LEVELS];
Node cur = head;
for (int lv = LEVELS - 1; lv >= 0; lv--) {
while (cur.nxt[lv] != null && cur.nxt[lv].value < key) cur = cur.nxt[lv];
path[lv] = cur;
}
return path;
}
public boolean search(int target) {
Node node = path(target)[0].nxt[0];
return node != null && node.value == target;
}
public void add(int num) {
Node[] path = path(num);
int height = 1;
while (height < LEVELS && rnd.nextBoolean()) height++;
Node node = new Node(num, height);
for (int lv = 0; lv < height; lv++) {
node.nxt[lv] = path[lv].nxt[lv];
path[lv].nxt[lv] = node;
}
}
public boolean erase(int num) {
Node[] path = path(num);
Node node = path[0].nxt[0];
if (node == null || node.value != num) return false;
for (int lv = 0; lv < node.nxt.length; lv++) {
if (path[lv].nxt[lv] == node) path[lv].nxt[lv] = node.nxt[lv];
}
return true;
}
}C++
class Skiplist {
static const int LEVELS = 16;
struct Node {
int value;
vector<Node*> nxt;
Node(int v, int h) : value(v), nxt(h, nullptr) {}
};
Node* head = new Node(-1, LEVELS);
void path(int key, Node** out) { // on every level, the last node with value < key
Node* cur = head;
for (int lv = LEVELS - 1; lv >= 0; lv--) {
while (cur->nxt[lv] && cur->nxt[lv]->value < key) cur = cur->nxt[lv];
out[lv] = cur;
}
}
public:
Skiplist() {}
bool search(int target) {
Node* p[LEVELS];
path(target, p);
Node* node = p[0]->nxt[0];
return node && node->value == target;
}
void add(int num) {
Node* p[LEVELS];
path(num, p);
int height = 1;
while (height < LEVELS && (rand() & 1)) height++;
Node* node = new Node(num, height);
for (int lv = 0; lv < height; lv++) {
node->nxt[lv] = p[lv]->nxt[lv];
p[lv]->nxt[lv] = node;
}
}
bool erase(int num) {
Node* p[LEVELS];
path(num, p);
Node* node = p[0]->nxt[0];
if (!node || node->value != num) return false;
for (int lv = 0; lv < (int)node->nxt.size(); lv++) {
if (p[lv]->nxt[lv] == node) p[lv]->nxt[lv] = node->nxt[lv];
}
delete node;
return true;
}
};JavaScript
var SK_LEVELS = 16;
function SkipNode(value, height) {
this.value = value;
this.nxt = new Array(height);
for (var i = 0; i < height; i++) this.nxt[i] = null;
}
var Skiplist = function() {
this.head = new SkipNode(-1, SK_LEVELS);
};
Skiplist.prototype.path = function(key) { // on every level, the last node with value < key
var path = new Array(SK_LEVELS), cur = this.head;
for (var lv = SK_LEVELS - 1; lv >= 0; lv--) {
while (cur.nxt[lv] !== null && cur.nxt[lv].value < key) cur = cur.nxt[lv];
path[lv] = cur;
}
return path;
};
Skiplist.prototype.search = function(target) {
var node = this.path(target)[0].nxt[0];
return node !== null && node.value === target;
};
Skiplist.prototype.add = function(num) {
var path = this.path(num), height = 1;
while (height < SK_LEVELS && Math.random() < 0.5) height++;
var node = new SkipNode(num, height);
for (var lv = 0; lv < height; lv++) {
node.nxt[lv] = path[lv].nxt[lv];
path[lv].nxt[lv] = node;
}
};
Skiplist.prototype.erase = function(num) {
var path = this.path(num), node = path[0].nxt[0];
if (node === null || node.value !== num) return false;
for (var lv = 0; lv < node.nxt.length; lv++) {
if (path[lv].nxt[lv] === node) path[lv].nxt[lv] = node.nxt[lv];
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.