Implement Skip List with in-place

Question

Implement a Skip List data structure that allows for efficient insertion, deletion, and search operations in O(log n) expected time. Your implementation should support the following methods: `insert(value)`, `delete(value)`, and `search(value)`, and should handle duplicate values appropriately. Ensure that the Skip List maintains the correct probabilistic balancing during operations.

Codemia · Accepted Answer

The Skip List is a data structure that allows for efficient search, insertion, and deletion operations, achieving O(log n) expected time complexity. The key concept here is to use multiple levels of linked lists where each level acts as an express lane for the list below it. This hierarchical structure can be efficiently navigated using a probabilistic balancing technique, which is the reason for its expected logarithmic performance. In this structure, each element has a random chance of being promoted to a higher level, creating a series of linked lists that allow for rapid traversal. This method is particularly suitable for this problem since it combines the efficiency of binary search with a linked list's dynamic nature. The approach to implement a Skip List involves the following steps: 1. **Node Structure**: Create a Node class that holds a value and a list of forward pointers to other nodes at different levels. 2. **Skip List Class**: Implement a Skip List class that maintains a head pointer and a maximum level. 3. **Insertion**: - Generate a random level for the new node using a coin flip strategy. - Create the new node and link it at the appropriate levels, ensuring that the links between nodes are maintained. - Insert the new node in the lowest level sorted order. 4. **Search**: - Start from the highest level and traverse downwards to find the target value by moving right until the next node's value is greater than the target. - If the target is found, return true; otherwise, return false. 5. **Deletion**: - Similar to search, find the target node, then unlink it from all levels where it exists, ensuring that the links remain intact. 6. **Examples**: For an insert operation with the value 5, if a random level of 2 is generated, the new node will be inserted at levels 0 and 1, with appropriate links established with existing nodes. Here is a Python implementation of the Skip List with the required methods: ```python import random class Node: def __init__(self, value, level): self.value = value self.forward = [None] * (level + 1) class SkipList: def __init__(self): self.max_level = 16 self.header = Node(-1, self.max_level) self.current_level = 0 def random_level(self): level = 0 while random.random() < 0.5 and level < self.max_level: level += 1 return level def insert(self, value): update = [None] * (self.max_level + 1) current = self.header for i in range(self.current_level, -1, -1): while current.forward[i] and current.forward[i].value < value: current = current.forward[i] update[i] = current current = current.forward[0] if not current or current.value != value: new_level = self.random_level() if new_level > self.current_level: for i in range(self.current_level + 1, new_level + 1): update[i] = self.header self.current_level = new_level new_node = Node(value, new_level) for i in range(new_level + 1): new_node.forward[i] = update[i].forward[i] update[i].forward[i] = new_node def search(self, value): current = self.header for i in range(self.current_level, -1, -1): while current.forward[i] and current.forward[i].value < value: current = current.forward[i] current = current.forward[0] return current is not None and current.value == value def delete(self, value): update = [None] * (self.max_level + 1) current = self.header for i in range(self.current_level, -1, -1): while current.forward[i] and current.forward[i].value < value: current = current.forward[i] update[i] = current current = current.forward[0] if current and current.value == value: for i in range(self.current_level + 1): if update[i].forward[i] != current: break update[i].forward[i] = current.forward[i] while self.current_level > 0 and self.header.forward[self.current_level] is None: self.current_level -= 1 ``` The time complexity for search, insert, and delete operations in the Skip List is O(log n) on average due to the probabilistic nature of the levels, which allows us to skip over large sections of the list. However, in the worst case (if all nodes happen to be at the lowest level), the complexity can become O(n). The space complexity is O(n) because, in the worst case, we could have n nodes, each with multiple pointers. Given that the maximum level is set to a constant (16 in our case), the space used for pointers remains manageable. Some edge cases to consider include: 1. **Inserting Duplicate Values**: Ensure that duplicate values are allowed and handled correctly by linking duplicates at the same level. 2. **Searching Non-existent Values**: When searching for a value that doesn’t exist in the list, the method should return false without any errors. 3. **Empty List Operations**: Inserting, searching, or deleting in an empty Skip List should be handled gracefully without errors. 4. **Deletion of Non-existent Values**: Attempting to delete a value not present in the list should not alter the state of the list or throw exceptions.

Implement Skip List with in-place

Reddit

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Reddit Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string