Design Skiplist

▶

Steps

setup

Initialize Skiplist

Create an empty skiplist with size 0, probability 0.5, head node with value -1 at level 0, and current max level 0.

💡 Initialization sets the foundation: head node acts as starting point for all levels, and size tracks number of elements for dynamic level calculation.

Line:

self.size = 0
self.P = 0.5
self.head = Node(-1, 0)
self.level = 0

💡 Skiplist starts empty with one level and a dummy head node to simplify insertions and searches.

insert

Add first node with value 1

Start adding node with value 1. Calculate max level as log2(size+1)=1 and prepare update array for level 0.

💡 Update array tracks nodes before insertion points at each level; here only level 0 exists.

Line:

update = [None] * (self.max_level() + 1)
curr = self.head
for i in range(self.level, -1, -1):
    while curr.forward[i] and curr.forward[i].val < num:
        curr = curr.forward[i]
    update[i] = curr

💡 Traversal finds position to insert at level 0, which is right after head since list is empty.

insert

Determine random level for new node (value 1)

Generate random level for new node. Max level is 1, random level generated is 0 (no promotion).

💡 Random level determines how many forward pointers new node will have, affecting skiplist height.

Line:

lvl = self.random_level()

💡 New node will be inserted only at level 0, simplest case.

insert

Insert new node with value 1 at level 0

Create new node with value 1 and level 0. Update head's forward pointer at level 0 to point to new node.

💡 Linking new node into skiplist updates forward pointers to maintain sorted order.

Line:

new_node = Node(num, lvl)
new_node.forward[0] = update[0].forward[0]
update[0].forward[0] = new_node

💡 Insertion updates pointers so head points to new node, and new node points to what head pointed before (null).

insert

Update skiplist size and level after adding 1

Increment size to 1 and update current max level to 0 (log2(2)=1 but capped at 0).

💡 Size and level track skiplist height and help determine promotion probabilities.

Line:

self.size += 1
self.level = max(self.level, lvl)

💡 Size increment triggers possible level increase; here level remains 0.

insert

Add second node with value 2

Traverse from top level 0 to find insertion point for 2. Update array records node before insertion at level 0.

💡 Traversal moves forward while next node's value is less than 2 to find correct insertion point.

Line:

curr = self.head
for i in range(self.level, -1, -1):
    while curr.forward[i] and curr.forward[i].val < num:
        curr = curr.forward[i]
    update[i] = curr

💡 Traversal stops at node with value 1, which is before insertion point for 2.

insert

Determine random level for new node (value 2)

Random level generated for new node with value 2 is 1, which is higher than current level 0.

💡 New node will have two levels, requiring skiplist level to increase and update array to be extended.

Line:

lvl = self.random_level()

💡 Node promotion increases skiplist height dynamically.

insert

Update skiplist level and update array for new level

Increase skiplist level from 0 to 1. Set update[1] to head node to link new node at new top level.

💡 Higher level pointers must be initialized to head to maintain skiplist structure.

Line:

if lvl > self.level:
    for i in range(self.level + 1, lvl + 1):
        update[i] = self.head
    self.level = lvl

💡 Skiplist height grows dynamically with node promotions.

insert

Insert new node with value 2 at levels 0 and 1

Create node with value 2 and level 1. Link it at levels 0 and 1 by updating forward pointers of update nodes.

💡 Multiple level pointers allow faster traversal; linking at all levels is essential.

Line:

new_node = Node(num, lvl)
for i in range(lvl + 1):
    new_node.forward[i] = update[i].forward[i]
    update[i].forward[i] = new_node

💡 New node inserted with correct multi-level links, skiplist structure updated.

insert

Update size after adding 2

Increment size to 2. Current level remains 1 as new node's level matches skiplist level.

💡 Size update keeps track of total elements for dynamic max level calculation.

Line:

self.size += 1

💡 Size increment triggers future level recalculations.

insert

Add third node with value 3

Traverse from top level 1 to find insertion point for 3. Update array records nodes before insertion at levels 1 and 0.

💡 Traversal moves forward at highest level possible to efficiently find insertion point.

Line:

curr = self.head
for i in range(self.level, -1, -1):
    while curr.forward[i] and curr.forward[i].val < num:
        curr = curr.forward[i]
    update[i] = curr

💡 Traversal stops at node 2 at both levels, correct insertion point found.

insert

Determine random level for new node (value 3)

Random level generated for new node with value 3 is 0, no promotion beyond level 0.

💡 Random level controls node height, affecting skiplist balance.

Line:

lvl = self.random_level()

💡 Node inserted only at base level 0.

insert

Insert new node with value 3 at level 0

Create node with value 3 at level 0. Link it after node 2 at level 0.

💡 Pointer updates maintain sorted order and skiplist structure.

Line:

new_node = Node(num, lvl)
new_node.forward[0] = update[0].forward[0]
update[0].forward[0] = new_node

💡 Node 3 inserted at base level, linked after node 2.

insert

Update size after adding 3

Increment size to 3. Skiplist level remains 1.

💡 Size update is essential for dynamic max level calculation.

Line:

self.size += 1

💡 Size now reflects three elements in skiplist.

search

Search for value 0 (absent)

Start search at top level 1 from head. Move forward while next node's value < 0; none found, move down to level 0.

💡 Search uses top-down traversal to quickly skip nodes greater than target.

Line:

curr = self.head
for i in range(self.level, -1, -1):
    while curr.forward[i] and curr.forward[i].val < target:
        curr = curr.forward[i]

💡 No nodes less than 0 found; search moves down to base level.

search

Check node after head at level 0 for value 0

At level 0, move to next node with value 1, which is greater than 0, so target not found.

💡 Search ends when next node's value is not equal to target.

Line:

curr = curr.forward[0]
return curr is not None and curr.val == target

💡 Search returns false for absent value.

insert

Add node with value 4

Traverse from top level 1 to find insertion point for 4. Update array records node 3 at level 0 and 1.

💡 Traversal efficiently finds insertion point after node 3.

Line:

curr = self.head
for i in range(self.level, -1, -1):
    while curr.forward[i] and curr.forward[i].val < num:
        curr = curr.forward[i]
    update[i] = curr

💡 Update array points to node 3 for insertion at both levels.

insert

Determine random level for new node (value 4)

Random level generated for new node with value 4 is 0, no promotion.

💡 Random level controls node height.

Line:

lvl = self.random_level()

💡 Node 4 inserted only at base level.

insert

Insert new node with value 4 at level 0

Create node 4 at level 0. Link it after node 3 at level 0.

💡 Pointer updates maintain sorted order.

Line:

new_node = Node(num, lvl)
new_node.forward[0] = update[0].forward[0]
update[0].forward[0] = new_node

💡 Node 4 inserted at base level.

insert

Update size after adding 4

Increment size to 4. Skiplist level remains 1.

💡 Size update is essential for dynamic max level calculation.

Line:

self.size += 1

💡 Size now reflects four elements in skiplist.

import random
import math

class Node:
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * (level + 1)

class Skiplist:
    def __init__(self):
        self.size = 0  # STEP 1
        self.P = 0.5
        self.head = Node(-1, 0)
        self.level = 0

    def max_level(self):
        return max(1, int(math.log2(self.size + 1)))

    def random_level(self):
        lvl = 0
        max_lvl = self.max_level()
        while random.random() < self.P and lvl < max_lvl:
            lvl += 1
        return lvl

    def search(self, target: int) -> bool:
        curr = self.head  # STEP 15
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < target:
                curr = curr.forward[i]
        curr = curr.forward[0]  # STEP 16
        return curr is not None and curr.val == target

    def add(self, num: int) -> None:
        update = [None] * (self.max_level() + 1)  # STEP 2,6,11,17
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr
        lvl = self.random_level()  # STEP 3,7,12,18
        if lvl > self.level:  # STEP 8
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl
        new_node = Node(num, lvl)  # STEP 4,9,13,19
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
        self.size += 1  # STEP 5,10,14,20

    def erase(self, num: int) -> bool:
        update = [None] * (self.level + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr
        curr = curr.forward[0]
        if curr is None or curr.val != num:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] != curr:
                break
            update[i].forward[i] = curr.forward[i]
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1
        self.size -= 1
        return True

📊

Design Skiplist - Watch the Algorithm Execute, Step by Step

Watching each pointer move and level adjustment live reveals the skiplist's layered linked list structure and probabilistic balancing, which is hard to grasp from code alone.

setup

-1

traverse

-1

expand

-1

connect

-1

→

1

advance

-1

→

1

traverse

-1

→

1

expand

-1

→

1

expand

-1

→

1

connect

-1

→

1

→

2

advance

-1

→

1

→

2

traverse

-1

→

1

→

2

expand

-1

→

1

→

2

connect

-1

→

1

→

2

→

3

advance

-1

→

1

→

2

→

3

compare

-1

→

1

→

2

→

3

compare

-1

→

1

→

2

→

3

Result: false

traverse

-1

→

1

→

2

→

3

expand

-1

→

1

→

2

→

3

connect

-1

→

1

→

2

→

3

→

4

advance

-1

→

1

→

2

→

3

→

4

Key Takeaways

✓ Skiplist uses multiple levels of linked lists to achieve fast search, insert, and erase operations.

This layered structure is hard to visualize from code alone but becomes clear when watching pointer updates at each level.

✓ Node promotion via random level generation dynamically adjusts skiplist height for balance.

Seeing how random_level affects node insertion levels clarifies how skiplist probabilistically balances itself.

✓ Search and erase operations traverse top-down levels, skipping large sections efficiently.

Watching traversal pointers move at different levels reveals the skiplist's speed advantage over simple linked lists.

Practice

1. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

2. Examine the following buggy code snippet for the MedianFinder class. Which line contains the subtle bug that can cause incorrect median calculation?

medium

A. Condition 'if self.low_size > self.high_size:' for balancing heaps

B. Line that pushes to high heap and increments high_size

C. Line that pushes to low heap and increments low_size

D. Condition 'elif self.high_size > self.low_size + 1:' for balancing heaps

Solution

1. Step 1: Understand balancing condition

   The heaps must be balanced so that their sizes differ by at most 1.

2. Step 2: Identify incorrect condition

   The condition 'if self.low_size > self.high_size:' moves an element from low to high even when sizes differ by only 1, causing imbalance.

3. Step 3: Correct condition

   The condition should be 'if self.low_size > self.high_size + 1:' to ensure size difference is more than 1 before balancing.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Balancing condition must check if low_size > high_size + 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Balancing heaps too aggressively
• Incorrect size difference checks

3. Consider the following buggy LFUCache get method. Which line contains the subtle bug that can cause incorrect eviction behavior?

def get(self, key: int) -> int:
    if key not in self.key_val_freq:
        return -1
    val, freq = self.key_val_freq[key]
    del self.freq_keys[freq][key]
    if not self.freq_keys[freq]:
        del self.freq_keys[freq]
        # BUG: missing update of min_freq here
    self.freq_keys[freq + 1][key] = None
    self.key_val_freq[key] = (val, freq + 1)
    return val

What is the bug?

medium

A. Missing update of min_freq after deleting freq_keys[freq]

B. Line deleting freq_keys[freq] when empty

C. Line deleting key from freq_keys[freq]

D. Line adding key to freq_keys[freq + 1]

Solution

1. Step 1: Identify the role of min_freq

   min_freq tracks the smallest frequency present in the cache, needed for correct eviction.

2. Step 2: Check frequency list deletion

   When freq_keys[freq] becomes empty and is deleted, if freq equals min_freq, min_freq must be incremented to freq + 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing min_freq update causes stale min_freq and wrong eviction [OK]

Hint: min_freq must update when freq list empties [OK]

Common Mistakes:

• Forgetting to update min_freq after freq list deletion
• Confusing key deletion with frequency list deletion
• Assuming min_freq updates automatically

4. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)