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. Given the following code snippet for the optimal UndergroundSystem implementation, what is the value of travel_time when checkOut(1, "Leyton", 20) is called after checkIn(1, "Paradise", 3) and checkIn(2, "Leyton", 10)?

class Node:
    def __init__(self, id, station, time):
        self.id = id
        self.station = station
        self.time = time
        self.next = None

class UndergroundSystem:
    def __init__(self):
        self.head = None
        self.route_data = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        new_node = Node(id, stationName, t)
        new_node.next = self.head
        self.head = new_node

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        prev = None
        curr = self.head
        while curr:
            if curr.id == id:
                travel_time = t - curr.time
                route = (curr.station, stationName)
                if route not in self.route_data:
                    self.route_data[route] = [0, 0]
                self.route_data[route][0] += travel_time
                self.route_data[route][1] += 1
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                return
            prev = curr
            curr = curr.next

easy

A. 10

B. 17

C. 7

D. 20

Solution

1. Step 1: Trace checkIn calls

   First, checkIn(1, "Paradise", 3) adds Node(id=1, station="Paradise", time=3) at head. Then checkIn(2, "Leyton", 10) adds Node(id=2, station="Leyton", time=10) at head.

2. Step 2: Trace checkOut(1, "Leyton", 20)

   Traverse linked list from head: Node with id=2 (not match), then Node with id=1 (match). travel_time = 20 - 3 = 17.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Check-in time for id=1 is 3, checkout time is 20, difference is 17 [OK]

Hint: Subtract check-in time from checkout time for travel_time [OK]

Common Mistakes:

• Using wrong node's time due to linked list order

2. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

3. 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

4. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

def remove(self, val: int) -> bool:
    if val not in self.idx_map or not self.idx_map[val]:
        return false
    remove_idx = self.idx_map[val].pop()
    last_val = self.nums[-1]
    self.nums[remove_idx] = last_val
    self.idx_map[last_val].add(remove_idx)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Solution

1. Step 1: Understand index updates during removal

   When swapping last_val into remove_idx, we must update idx_map[last_val] by adding remove_idx and discarding the old index (len(nums)-1).

2. Step 2: Identify missing discard

   The code adds remove_idx to idx_map[last_val] but does not discard the old index, causing stale indices and incorrect removals later.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing discard leads to incorrect index tracking [OK]

Hint: Always discard old indices after swapping during removal [OK]

Common Mistakes:

• Forgetting to discard old index after swap
• Removing wrong element from idx_map
• Incorrect pop from idx_map[val]

5. Suppose the UndergroundSystem is extended to allow multiple check-ins by the same passenger without requiring a check-out first (i.e., passengers can start multiple trips before finishing any). Which modification to the data structure or algorithm is necessary to handle this correctly?

hard

A. Keep a stack of check-in nodes per passenger id to track multiple active trips.

B. Use a hash map from passenger id to a single check-in node, overwriting previous check-ins.

C. Store all check-ins in a linked list and traverse fully on each checkOut to find the earliest unmatched check-in.

D. Disallow multiple check-ins by the same passenger to avoid complexity.

Solution

1. Step 1: Understand the problem extension

   Passengers can have multiple active trips simultaneously, so a single check-in per id is insufficient.

2. Step 2: Choose data structure to track multiple check-ins

   A stack per passenger id allows tracking multiple check-ins in order, enabling correct matching on checkOut.

3. Step 3: Why other options fail

   Overwriting check-ins loses data (A). Traversing full list each time (C) is inefficient. Disallowing multiple check-ins (D) is not a solution.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack per id supports multiple active trips correctly [OK]

Hint: Stack per id tracks multiple active check-ins [OK]

Common Mistakes:

• Overwriting check-in info loses data