Design Skiplist
<p>Design a <strong>Skiplist</strong> without using any built-in libraries.</p>

<p>A <strong>skiplist</strong> is a data structure that takes <code>O(log(n))</code> 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.</p>

<p>For example, we have a Skiplist containing <code>[30,40,50,60,70,90]</code> and we want to add <code>80</code> and <code>45</code> into it. The Skiplist works this way:</p>

<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1200-1299/1206.Design%20Skiplist/images/1506_skiplist.gif" style="width: 500px; height: 173px;" /><br />
<small>Artyom Kalinin [CC BY-SA 3.0], via <a href="https://commons.wikimedia.org/wiki/File:Skip_list_add_element-en.gif" target="_blank" title="Artyom Kalinin [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons">Wikimedia Commons</a></small></p>

<p>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 <code>O(n)</code>. It can be proven that the average time complexity for each operation is <code>O(log(n))</code> and space complexity is <code>O(n)</code>.</p>

<p>See more about Skiplist: <a href="https://en.wikipedia.org/wiki/Skip_list" target="_blank">https://en.wikipedia.org/wiki/Skip_list</a></p>

<p>Implement the <code>Skiplist</code> class:</p>

<ul>
	<li><code>Skiplist()</code> Initializes the object of the skiplist.</li>
	<li><code>bool search(int target)</code> Returns <code>true</code> if the integer <code>target</code> exists in the Skiplist or <code>false</code> otherwise.</li>
	<li><code>void add(int num)</code> Inserts the value <code>num</code> into the SkipList.</li>
	<li><code>bool erase(int num)</code> Removes the value <code>num</code> from the Skiplist and returns <code>true</code>. If <code>num</code> does not exist in the Skiplist, do nothing and return <code>false</code>. If there exist multiple <code>num</code> values, removing any one of them is fine.</li>
</ul>

<p>Note that duplicates may exist in the Skiplist, your code needs to handle this situation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input</strong>
[&quot;Skiplist&quot;, &quot;add&quot;, &quot;add&quot;, &quot;add&quot;, &quot;search&quot;, &quot;add&quot;, &quot;search&quot;, &quot;erase&quot;, &quot;erase&quot;, &quot;search&quot;]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
<strong>Output</strong>
[null, null, null, null, false, null, true, false, true, false]

<strong>Explanation</strong>
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.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= num, target &lt;= 2 * 10<sup>4</sup></code></li>
	<li>At most <code>5 * 10<sup>4</sup></code> calls will be made to <code>search</code>, <code>add</code>, and <code>erase</code>.</li>
</ul>
Design; Linked List
class Node {
    val: number;
    next: (Node | null)[];

    constructor(val: number, level: number) {
        this.val = val;
        this.next = Array(level).fill(null);
    }
}

class Skiplist {
    private static maxLevel: number = 32;
    private static p: number = 0.25;
    private head: Node;
    private level: number;

    constructor() {
        this.head = new Node(-1, Skiplist.maxLevel);
        this.level = 0;
    }

    search(target: number): boolean {
        let curr = this.head;
        for (let i = this.level - 1; i >= 0; i--) {
            curr = this.findClosest(curr, i, target);
            if (curr.next[i] && curr.next[i]!.val === target) {
                return true;
            }
        }
        return false;
    }

    add(num: number): void {
        let curr = this.head;
        const level = this.randomLevel();
        const node = new Node(num, level);
        this.level = Math.max(this.level, level);

        for (let i = this.level - 1; i >= 0; i--) {
            curr = this.findClosest(curr, i, num);
            if (i < level) {
                node.next[i] = curr.next[i];
                curr.next[i] = node;
            }
        }
    }

    erase(num: number): boolean {
        let curr = this.head;
        let ok = false;

        for (let i = this.level - 1; i >= 0; i--) {
            curr = this.findClosest(curr, i, num);
            if (curr.next[i] && curr.next[i]!.val === num) {
                curr.next[i] = curr.next[i]!.next[i];
                ok = true;
            }
        }

        while (this.level > 1 && this.head.next[this.level - 1] === null) {
            this.level--;
        }

        return ok;
    }

    private findClosest(curr: Node, level: number, target: number): Node {
        while (curr.next[level] && curr.next[level]!.val < target) {
            curr = curr.next[level]!;
        }
        return curr;
    }

    private randomLevel(): number {
        let level = 1;
        while (level < Skiplist.maxLevel && Math.random() < Skiplist.p) {
            level++;
        }
        return level;
    }
}

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