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 are 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).
To be specific, your design should include these functions:
bool search(int target) : Return whether the target exists in the Skiplist or not.
void add(int num): Insert a value into the SkipList. 
bool erase(int num): Remove a value in the Skiplist. If num does not exist in the Skiplist, do nothing and return false. If there exists multiple num values, removing any one of them is fine.
See more about Skiplist : https://en.wikipedia.org/wiki/Skip_list
Note that duplicates may exist in the Skiplist, your code needs to handle this situation.
Example:
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 <= 20000
At most 50000 calls will be made to search, add, and erase.
class Node(object):
    def __init__(self, val):
        self.val = val
        self.cnt = 1
        self.right = None
        self.down = None

import random
class Skiplist:

    def __init__(self):
        self.root = Node(float('-inf'))
        p = self.root
        for _ in range(31):
            p.down = Node(float('-inf'))
            p = p.down
        self.root.right = Node(float('inf'))
        uplevel = self.root
        clevel = self.root.down
        while clevel:
            clevel.right = Node(float('inf'))
            uplevel.right.down = clevel.right
            uplevel = clevel
            clevel = clevel.down

    def search(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                return p.cnt > 0
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False
            
    def add(self, num: int) -> None:
        p = self.root
        path = []
        while p:
            if p.val == num:
                while p:
                    p.cnt += 1
                    p = p.down
                return
            elif p.right.val <= num:
                p = p.right
            else:
                path.append(p)
                p = p.down
        node = Node(num)
        node.right = path[-1].right
        path[-1].right = node
        path.pop(-1)
        while path and random.random() < 0.5:
            last_level = path.pop(-1)
            new_node = Node(num)
            new_node.right = last_level.right
            last_level.right = new_node
            new_node.down = node
            node = new_node

    def erase(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                if p.cnt > 0:
                    while p:
                        p.cnt -= 1
                        p = p.down
                    return True
                else:
                    return False
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)

class Node(object):
    def __init__(self, val):
        self.val = val
        self.cnt = 1
        self.right = None
        self.down = None

import random
class Skiplist:

    def __init__(self):
        self.root = Node(float('-inf'))
        p = self.root
        for _ in range(31):
            p.down = Node(float('-inf'))
            p = p.down
        self.root.right = Node(float('inf'))
        uplevel = self.root
        clevel = self.root.down
        while clevel:
            clevel.right = Node(float('inf'))
            uplevel.right.down = clevel.right
            uplevel = clevel
            clevel = clevel.down

    def search(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                return p.cnt > 0
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False
            
    def add(self, num: int) -> None:
        p = self.root
        path = []
        while p:
            if p.val == num:
                while p:
                    p.cnt += 1
                    p = p.down
                return
            elif p.right.val <= num:
                p = p.right
            else:
                path.append(p)
                p = p.down
        node = Node(num)
        node.right = path[-1].right
        path[-1].right = node
        path.pop(-1)
        while path and random.random() < 0.5:
            last_level = path.pop(-1)
            new_node = Node(num)
            new_node.right = last_level.right
            last_level.right = new_node
            new_node.down = node
            node = new_node

    def erase(self, target: int) -> bool:
        p = self.root
        while p:
            if p.val == target:
                if p.cnt > 0:
                    while p:
                        p.cnt -= 1
                        p = p.down
                    return True
                else:
                    return False
            elif p.right.val <= target:
                p = p.right
            else:
                p = p.down
        return False


# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)
