Introduction

In this blog post, we will explore how to solve the LeetCode problem "1206" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Design a Skiplist without using any built-in libraries. A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists. For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way: Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n). See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list Implement the Skiplist class: Skiplist() Initializes the object of the skiplist. bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise. void add(int num) Inserts the value num into the SkipList. bool erase(int num) Removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine. Note that duplicates may exist in the Skiplist, your code needs to handle this situation. Example 1: Input ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] Output [null, null, null, null, false, null, true, false, true, false] Explanation Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // return False skiplist.add(4); skiplist.search(1); // return True skiplist.erase(0); // return False, 0 is not in skiplist. skiplist.erase(1); // return True skiplist.search(1); // return False, 1 has already been erased. Constraints: 0 <= num, target <= 2 104 At most 5 104 calls will be made to search, add, and erase.

Explanation

• Probabilistic Level Assignment: Each new node is assigned a random level. The probability of a node being promoted to the next higher level is typically 0.5. This probabilistic approach ensures a balanced structure on average.
  • Update Array: During insertion and deletion, maintain an "update" array that stores the pointers to the nodes that need to be updated at each level. This array efficiently guides the modification of the skiplist structure.
  • Efficient Search: The search, add, and erase operations leverage the multi-level structure of the skiplist for logarithmic time complexity. The search starts from the highest level and proceeds downwards, significantly reducing the number of nodes visited.

• Runtime Complexity: O(log n) average for search, add, and erase. Storage Complexity: O(n)

Code

    import random

class Skiplist:
    def __init__(self):
        self.MAX_LEVEL = 32  # Maximum level for the skiplist
        self.P = 0.5  # Probability of a node being promoted to the next level
        self.level = 0  # Current level of the skiplist
        self.head = SkiplistNode(-1, self.MAX_LEVEL)

    def random_level(self):
        level = 0
        while random.random() < self.P and level < self.MAX_LEVEL - 1:
            level += 1
        return level

    def search(self, target):
        node = self.head
        for i in range(self.level, -1, -1):
            while node.forward[i] and node.forward[i].val < target:
                node = node.forward[i]
        return node.forward[0] is not None and node.forward[0].val == target

    def add(self, num):
        update = [None] * self.MAX_LEVEL
        node = self.head
        for i in range(self.level, -1, -1):
            while node.forward[i] and node.forward[i].val < num:
                node = node.forward[i]
            update[i] = node

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

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

    def erase(self, num):
        update = [None] * self.MAX_LEVEL
        node = self.head
        for i in range(self.level, -1, -1):
            while node.forward[i] and node.forward[i].val < num:
                node = node.forward[i]
            update[i] = node

        if node.forward[0] is not None and node.forward[0].val == num:
            for i in range(self.level + 1):
                if update[i].forward[i] != node.forward[0]:
                    break
                update[i].forward[i] = node.forward[0].forward[i]

            while self.level > 0 and self.head.forward[self.level] is None:
                self.level -= 1
            return True
        else:
            return False


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