Skip lists for probabilistic search in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to describe the basic structure of a skip list node.

Data Structures Theory

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

Drag options to blanks, or click blank then click option'

Alevel

Bvalue

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed size like 1 or 0 for the forward list.

The 'forward' list holds references to nodes at different levels. Its size depends on the node's level.

2fill in blank

medium

Complete the code to generate a random level for a new node in a skip list.

Data Structures Theory

def random_level(p=0.5, max_level=16):
    level = 1
    while random.random() < [1] and level < max_level:
        level += 1
    return level

Drag options to blanks, or click blank then click option'

Ap

Brandom.random()

Clevel

Dmax_level

Attempts:

3 left

💡 Hint

Common Mistakes

Using max_level or level instead of the probability 'p' in the condition.

The probability 'p' controls how likely it is to increase the level of a node.

3fill in blank

hard

Fix the error in the search function to correctly traverse levels in a skip list.

Data Structures Theory

def search(head, target, max_level):
    current = head
    for i in range(max_level - 1, -1, -1):
        while current.forward[[1]] and current.forward[i].value < target:
            current = current.forward[i]
    current = current.forward[0]
    if current and current.value == target:
        return True
    return False

Drag options to blanks, or click blank then click option'

Amax_level

B0

Ctarget

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed index like 0 instead of the loop variable 'i'.

The index in the forward list should be 'i' to check the correct level during traversal.

4fill in blank

hard

Fill both blanks to correctly update pointers when inserting a new node in a skip list.

Data Structures Theory

def insert(head, value, max_level):
    update = [None] * max_level
    current = head
    for i in range(max_level - 1, -1, -1):
        while current.forward[i] and current.forward[i].value < value:
            current = current.forward[i]
        update[[1]] = current
    level = random_level()
    new_node = Node(value, level)
    for i in range(level):
        new_node.forward[i] = update[[2]].forward[i]
        update[i].forward[i] = new_node

Drag options to blanks, or click blank then click option'

Ai

Blevel

C0

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using different indices for update and pointer assignment.

The index 'i' is used to track the current level for updating pointers during insertion.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps node levels to 1 for nodes with levels greater than 0.

Data Structures Theory

level_counts = [1]: [2] for node in nodes if node.level [3] 0

Drag options to blanks, or click blank then click option'

A{node.level

B1

C>

Dnode.level

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect dictionary syntax or wrong comparison operators.

This comprehension creates a dictionary mapping each unique node level greater than zero to 1, indicating the presence of nodes at those levels.