Senior LevelData Structures & Algorithms
What is a Skip List and how does it achieve O(log N) operations probabilistically?
ā Interview Prompt: Explain Skip List structure, probabilistic balancing via coin flipping, O(log N) expected search/insert/delete, and comparison to balanced BSTs.
A Skip List is a probabilistic data structure layering multiple linked lists, achieving $O(\log N)$ expected time for search, insert, and delete without complex rotations.
Structure:
ā¢
Level 0: Standard sorted linked list.
ā¢
Level $i$: Contains a randomly selected subset (~50%) of level $i-1$ elements.
ā¢
Expected $O(\log N)$ levels.
Search: $O(\log N)$ expected
Start at the topmost list; move right until the next element is too large, then drop down one level.
Insert:
Random coin flips determine how many levels the new node promotes to.
vs Balanced BSTs:
ā¢
Skip Lists are simpler to implement (no rotations).
ā¢
Concurrent skip lists are easier to lock-free-implement (used in Java ConcurrentSkipListMap).
Code Implementation Example
typescript
const MAX_LEVEL = 16;
class SkipNode {
val: number;
next: (SkipNode | null)[];
constructor(val: number, level: number) {
this.val = val;
this.next = new Array(level + 1).fill(null);
}
}
class SkipList {
private head = new SkipNode(-Infinity, MAX_LEVEL);
private level = 0;
private randomLevel(): number {
let l = 0;
while (Math.random() < 0.5 && l < MAX_LEVEL) l++;
return l;
}
search(target: number): boolean {
let node = this.head;
for (let l = this.level; l >= 0; l--) {
while (node.next[l] && node.next[l]!.val < target)
node = node.next[l]!;
}
return node.next[0]?.val === target;
}
}š”Skip List search descending levels ā O(log N) expected.
šÆ Interview Key Takeaway
Skip Lists provide O(log N) expected operations via probabilistic coin-flip promotion. Used in Redis sorted sets and Java ConcurrentSkipListMap.
#DSA#Skip List#Probabilistic#Data Structures#Senior
Back to all Data Structures & Algorithms Questionsā