#1206

Design Skiplist

expert · 1205 · lc hard +32 · 59.6% accepted · 724 likes · top 57%

Description

Implement a Skiplist from scratch without using any built-in libraries.

A skiplist is a probabilistic data structure built on layered sorted linked lists that achieves O(log(n)) expected time for add, erase, and search — comparable to balanced BSTs but simpler to code.

Implement the Skiplist class:

- Skiplist() creates an empty skiplist.

- bool search(int target) returns true if target exists in the skiplist, false otherwise.

- void add(int num) inserts num into the skiplist.

- bool erase(int num) removes one occurrence of num and returns true. Returns false if num is absent. If duplicates exist, removing any one is acceptable.

The skiplist must correctly handle duplicate values.

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]

Example 2:

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.

Code

class Skiplist:

    def __init__(self):
        

    def search(self, target: int) -> bool:
        

    def add(self, num: int) -> None:
        

    def erase(self, num: int) -> bool:
        


# 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 Skiplist:

    def __init__(self):
        

    def search(self, target: int) -> bool:
        

    def add(self, num: int) -> None:
        

    def erase(self, num: int) -> bool:
        


# 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)