Implement Skip List with with follow-up

Question

Implement a Skip List data structure that supports insert, delete, and search operations with an average time complexity of O(log n). Your implementation should handle duplicate values and maintain a sorted order of elements. The input will consist of a series of operations, and the output should reflect the results of search operations, indicating whether a value exists in the list.

Codemia · Accepted Answer

A Skip List is a probabilistic data structure that allows for fast search, insertion, and deletion operations, with an average time complexity of O(log n). The structure consists of multiple layers of linked lists, where each higher layer acts as an express lane for the layers below, effectively allowing for a logarithmic reduction in the search space. In this problem, we need to implement a Skip List that maintains sorted order and can handle duplicate values. The specific pattern here is the use of layers to reduce the search time, which aligns well with the requirements for efficient search, insert, and delete operations. 1. **Initialization**: Create a `Node` class that holds a value and a list of forward pointers. Create the `SkipList` class that maintains a head node and a maximum level. 2. **Insert Operation**: - Generate a random level for the new node. - Traverse the list to find the position to insert the new node at each level, updating pointers accordingly. - Handle duplicates by allowing multiple nodes with the same value at each level. 3. **Delete Operation**: - Similar to insert, traverse the list to find the node to delete, adjusting pointers to bypass the node being deleted. 4. **Search Operation**: - Start from the highest level and traverse down to find the node, returning true if found, false otherwise. 5. **Example**: Consider inserting values [3, 6, 7, 9, 12, 19, 17, 26, 21, 25]. The Skip List will dynamically adjust its structure to maintain sorted order and handle duplicates, such as inserting '3' multiple times. ```python import random class Node: def __init__(self, value, level): self.value = value self.forward = [None] * (level + 1) class SkipList: def __init__(self, max_level): self.max_level = max_level self.header = Node(-1, max_level) self.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): current = self.header update = [None] * (self.max_level + 1) for i in range(self.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 is None or current.value != value: new_level = self.random_level() if new_level > self.level: for i in range(self.level + 1, new_level + 1): update[i] = self.header self.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 delete(self, value): current = self.header update = [None] * (self.max_level + 1) for i in range(self.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 is not None and current.value == value: for i in range(self.level + 1): if update[i].forward[i] != current: break update[i].forward[i] = current.forward[i] while self.level > 0 and self.header.forward[self.level] is None: self.level -= 1 def search(self, value): current = self.header for i in range(self.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 ``` The average time complexity for search, insert, and delete operations is O(log n) due to the layered structure that allows skipping over sections of the list. The space complexity is O(n) as we need to store each element in the Skip List. In the worst case, if the random level generation results in all nodes being at the lowest level, the time complexity can degrade to O(n), but this is highly unlikely with a good randomization strategy. 1. **Inserting Duplicate Values**: Ensure that the implementation can handle inserting the same value multiple times, maintaining the correct order and structure. 2. **Deleting Non-Existent Values**: Attempting to delete a value that isn't in the Skip List should not cause errors and should be gracefully handled. 3. **Searching for Non-Existent Values**: Searching for a value not present in the list should return false without exceptions. 4. **Empty Skip List**: Performing search, insert, and delete operations on an empty Skip List should be handled correctly without any issues.

Implement Skip List with with follow-up

Mastercard

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

Mastercard Software 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