Design Skiplist

🎯

Design Skiplist

hardDESIGNAmazonGoogle

Imagine you need a data structure that supports fast search, insertion, and deletion, but you want to avoid the complexity of balanced trees. Skiplist offers a probabilistic alternative that is easier to implement and efficient.

💡 This problem is about designing a probabilistic data structure that balances simplicity and efficiency. Beginners often struggle because it combines linked lists with randomization and multiple levels, which is less intuitive than arrays or trees.

📋

Problem Statement

Design a Skiplist without using any built-in libraries. A Skiplist is a data structure that allows fast search, insertion, and deletion operations in average O(log n) time. Implement the Skiplist class with the following methods: - boolean search(int target): Returns true if the target exists in the Skiplist, otherwise false. - void add(int num): Inserts the number into the Skiplist. - boolean erase(int num): Removes one occurrence of num from the Skiplist if present. Returns true if the number existed and was erased, false otherwise. The Skiplist should use multiple levels of linked lists with probabilistic promotion of nodes to higher levels.

1 ≤ number of operations ≤ 10^5-2 * 10^4 ≤ num, target ≤ 2 * 10^4At most 5 levels in the Skiplist (typical max level)

💡

Example

Input"add(1), add(2), add(3), search(0), add(4), search(1), erase(0), erase(1), search(1)"

Outputfalse, true, false, false

Initially, 1, 2, 3 are added. Searching 0 returns false. Adding 4, searching 1 returns true. Erasing 0 returns false since 0 not present. Erasing 1 returns true. Searching 1 now returns false.

• search in an empty Skiplist → false
• erase a number not present → false
• add duplicate numbers and erase one occurrence → true
• search for minimum and maximum possible values → correct result

⚠️

Common Mistakes

Not updating all levels during erase

Node remains in higher levels causing incorrect search results

✅ Ensure erase updates forward pointers at all levels where node appears

Incorrect random level generation exceeding max level

Array index out of bounds or corrupted structure

✅ Limit random level to max allowed level

Not adjusting current max level after erase

Top levels remain even if empty, wasting space and slowing operations

✅ Decrease current max level when top levels become empty

Using fixed max level without considering size

Wastes memory or reduces performance for large or small datasets

✅ Dynamically adjust max level based on Skiplist size

Forgetting dummy head node

Insertion and deletion logic becomes complex with many edge cases

✅ Use a dummy head node with max level pointers

🧠

Brute Force (Single Level Linked List)

💡 Starting with a simple linked list helps understand the core operations without the complexity of multiple levels or randomization. It clarifies the baseline performance and why Skiplist improves on it.

Intuition

Use a single sorted linked list to perform search, add, and erase operations by traversing nodes linearly.

Algorithm

1. Initialize a singly linked list with a dummy head.
2. For search, traverse nodes until target is found or passed.
3. For add, find the correct position and insert a new node.
4. For erase, find the node and remove it by adjusting pointers.

💡 This approach is straightforward but inefficient for large inputs because every operation requires linear traversal.

</>

Code

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Skiplist:
    def __init__(self):
        self.head = Node(-1)  # dummy head

    def search(self, target: int) -> bool:
        curr = self.head.next
        while curr and curr.val < target:
            curr = curr.next
        return curr is not None and curr.val == target

    def add(self, num: int) -> None:
        prev = self.head
        while prev.next and prev.next.val < num:
            prev = prev.next
        new_node = Node(num, prev.next)
        prev.next = new_node

    def erase(self, num: int) -> bool:
        prev = self.head
        while prev.next and prev.next.val < num:
            prev = prev.next
        if prev.next and prev.next.val == num:
            prev.next = prev.next.next
            return True
        return False

# Driver code
if __name__ == '__main__':
    skiplist = Skiplist()
    skiplist.add(1)
    skiplist.add(2)
    skiplist.add(3)
    print(skiplist.search(0))  # False
    skiplist.add(4)
    print(skiplist.search(1))  # True
    print(skiplist.erase(0))   # False
    print(skiplist.erase(1))   # True
    print(skiplist.search(1))  # False

Line Notes

class Node:Defines a basic linked list node structure to hold values and next pointers.

self.head = Node(-1)Dummy head simplifies edge cases for insertion and deletion by providing a fixed starting point.

while curr and curr.val < target:Traverse nodes until we find the target or pass it, ensuring search correctness.

prev.next = new_nodeInsert new node by adjusting pointers to maintain sorted order.

if prev.next and prev.next.val == num:Check if node to erase exists before removal to avoid errors.

class Skiplist {
    private class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; this.next = null; }
    }
    private Node head;

    public Skiplist() {
        head = new Node(-1); // dummy head
    }

    public boolean search(int target) {
        Node curr = head.next;
        while (curr != null && curr.val < target) {
            curr = curr.next;
        }
        return curr != null && curr.val == target;
    }

    public void add(int num) {
        Node prev = head;
        while (prev.next != null && prev.next.val < num) {
            prev = prev.next;
        }
        Node newNode = new Node(num);
        newNode.next = prev.next;
        prev.next = newNode;
    }

    public boolean erase(int num) {
        Node prev = head;
        while (prev.next != null && prev.next.val < num) {
            prev = prev.next;
        }
        if (prev.next != null && prev.next.val == num) {
            prev.next = prev.next.next;
            return true;
        }
        return false;
    }

    // Main method for testing
    public static void main(String[] args) {
        Skiplist skiplist = new Skiplist();
        skiplist.add(1);
        skiplist.add(2);
        skiplist.add(3);
        System.out.println(skiplist.search(0)); // false
        skiplist.add(4);
        System.out.println(skiplist.search(1)); // true
        System.out.println(skiplist.erase(0));  // false
        System.out.println(skiplist.erase(1));  // true
        System.out.println(skiplist.search(1)); // false
    }
}

Line Notes

private class Node {Inner class to represent linked list nodes with value and next pointer.

head = new Node(-1);Dummy head node to simplify insert and delete operations by avoiding null checks.

while (curr != null && curr.val < target)Traverse nodes to find target or position for search.

prev.next = newNode;Insert new node by adjusting pointers to maintain sorted order.

if (prev.next != null && prev.next.val == num)Check existence before erase to avoid errors.

#include <iostream>
using namespace std;

class Skiplist {
    struct Node {
        int val;
        Node* next;
        Node(int v) : val(v), next(nullptr) {}
    };
    Node* head;
public:
    Skiplist() {
        head = new Node(-1); // dummy head
    }

    bool search(int target) {
        Node* curr = head->next;
        while (curr && curr->val < target) {
            curr = curr->next;
        }
        return curr && curr->val == target;
    }

    void add(int num) {
        Node* prev = head;
        while (prev->next && prev->next->val < num) {
            prev = prev->next;
        }
        Node* newNode = new Node(num);
        newNode->next = prev->next;
        prev->next = newNode;
    }

    bool erase(int num) {
        Node* prev = head;
        while (prev->next && prev->next->val < num) {
            prev = prev->next;
        }
        if (prev->next && prev->next->val == num) {
            Node* toDelete = prev->next;
            prev->next = toDelete->next;
            delete toDelete;
            return true;
        }
        return false;
    }
};

int main() {
    Skiplist skiplist;
    skiplist.add(1);
    skiplist.add(2);
    skiplist.add(3);
    cout << boolalpha << skiplist.search(0) << endl; // false
    skiplist.add(4);
    cout << skiplist.search(1) << endl; // true
    cout << skiplist.erase(0) << endl;  // false
    cout << skiplist.erase(1) << endl;  // true
    cout << skiplist.search(1) << endl; // false
    return 0;
}

Line Notes

struct Node {Defines node structure for linked list with value and next pointer.

head = new Node(-1);Dummy head node to avoid edge cases in insertion and deletion.

while (curr && curr->val < target)Traverse nodes to find target or position during search.

prev->next = newNode;Insert new node by pointer manipulation to maintain sorted order.

delete toDelete;Free memory of erased node to avoid memory leaks.

class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Skiplist {
    constructor() {
        this.head = new Node(-1); // dummy head
    }

    search(target) {
        let curr = this.head.next;
        while (curr && curr.val < target) {
            curr = curr.next;
        }
        return curr !== null && curr.val === target;
    }

    add(num) {
        let prev = this.head;
        while (prev.next && prev.next.val < num) {
            prev = prev.next;
        }
        const newNode = new Node(num, prev.next);
        prev.next = newNode;
    }

    erase(num) {
        let prev = this.head;
        while (prev.next && prev.next.val < num) {
            prev = prev.next;
        }
        if (prev.next && prev.next.val === num) {
            prev.next = prev.next.next;
            return true;
        }
        return false;
    }
}

// Test
const skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
console.log(skiplist.search(0)); // false
skiplist.add(4);
console.log(skiplist.search(1)); // true
console.log(skiplist.erase(0));  // false
console.log(skiplist.erase(1));  // true
console.log(skiplist.search(1)); // false

Line Notes

class Node {Defines node structure for linked list with value and next pointer.

this.head = new Node(-1);Dummy head simplifies insertion and deletion by avoiding null checks.

while (curr && curr.val < target)Traverse nodes to find target or position during search.

prev.next = newNode;Insert new node by pointer adjustment to maintain sorted order.

if (prev.next && prev.next.val === num)Check existence before erasing node to avoid errors.

⏱

Complexity

TimeO(n) per operation

SpaceO(n) for storing nodes

Each operation requires traversing the linked list which can be up to n nodes long, so linear time per operation.

💡 For n=1000, each operation might scan up to 1000 nodes, which is slow compared to logarithmic alternatives.

Interview Verdict: Accepted but inefficient for large inputs

This approach works correctly but is too slow for large datasets, motivating the need for Skiplist's multi-level design.

🧠

Skiplist with Multiple Levels and Randomized Promotion

💡 This approach introduces the core Skiplist concept: multiple levels of linked lists with probabilistic node promotion to achieve average O(log n) operations.

Intuition

Maintain several layers of sorted linked lists where higher layers skip more nodes, allowing faster search by jumping ahead. Nodes are promoted to higher levels randomly.

Algorithm

1. Initialize a head node with maximum level pointers.
2. For search, start from top level and move forward while next node is less than target, then drop down levels.
3. For add, find insertion points at each level, insert new node, and randomly promote it to higher levels.
4. For erase, find and remove node at all levels where it appears.

💡 The challenge is managing multiple pointers per node and ensuring consistent updates across levels.

</>

Code

import random

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

class Skiplist:
    MAX_LEVEL = 4
    P = 0.5

    def __init__(self):
        self.head = Node(-1, self.MAX_LEVEL)
        self.level = 0

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

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

    def add(self, num: int) -> None:
        update = [None] * (self.MAX_LEVEL + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr
        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl
        new_node = Node(num, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def erase(self, num: int) -> bool:
        update = [None] * (self.MAX_LEVEL + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr
        curr = curr.forward[0]
        if curr is None or curr.val != num:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] != curr:
                continue
            update[i].forward[i] = curr.forward[i]
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1
        return True

# Driver code
if __name__ == '__main__':
    skiplist = Skiplist()
    skiplist.add(1)
    skiplist.add(2)
    skiplist.add(3)
    print(skiplist.search(0))  # False
    skiplist.add(4)
    print(skiplist.search(1))  # True
    print(skiplist.erase(0))   # False
    print(skiplist.erase(1))   # True
    print(skiplist.search(1))  # False

Line Notes

self.forward = [None] * (level + 1)Each node has multiple forward pointers for each level to enable multi-level traversal.

while random.random() < self.P and lvl < self.MAX_LEVEL:Randomly decide node's level to balance the Skiplist and maintain probabilistic height.

for i in range(self.level, -1, -1):Start search from top level down to bottom to efficiently find target or insertion point.

update[i] = currTrack nodes at each level before insertion point to update pointers during add or erase.

while self.level > 0 and self.head.forward[self.level] is None:Decrease current max level if top levels become empty to optimize structure.

import java.util.Random;

class Skiplist {
    private static final int MAX_LEVEL = 4;
    private static final double P = 0.5;

    private class Node {
        int val;
        Node[] forward;
        Node(int val, int level) {
            this.val = val;
            forward = new Node[level + 1];
        }
    }

    private Node head;
    private int level;
    private Random rand;

    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        level = 0;
        rand = new Random();
    }

    private int randomLevel() {
        int lvl = 0;
        while (rand.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    public boolean search(int target) {
        Node curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        return curr != null && curr.val == target;
    }

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        int lvl = randomLevel();
        if (lvl > level) {
            for (int i = level + 1; i <= lvl; i++) {
                update[i] = head;
            }
            level = lvl;
        }
        Node newNode = new Node(num, lvl);
        for (int i = 0; i <= lvl; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i <= level; i++) {
            if (update[i].forward[i] != curr) continue;
            update[i].forward[i] = curr.forward[i];
        }
        while (level > 0 && head.forward[level] == null) {
            level--;
        }
        return true;
    }

    public static void main(String[] args) {
        Skiplist skiplist = new Skiplist();
        skiplist.add(1);
        skiplist.add(2);
        skiplist.add(3);
        System.out.println(skiplist.search(0)); // false
        skiplist.add(4);
        System.out.println(skiplist.search(1)); // true
        System.out.println(skiplist.erase(0));  // false
        System.out.println(skiplist.erase(1));  // true
        System.out.println(skiplist.search(1)); // false
    }
}

Line Notes

Node[] forward;Array of forward pointers for each level to enable multi-level traversal.

while (rand.nextDouble() < P && lvl < MAX_LEVEL)Randomly determine node's level for balancing the Skiplist structure.

for (int i = level; i >= 0; i--)Traverse from top level down during search and insert for efficiency.

update[i] = curr;Keep track of nodes before insertion points at each level to update pointers.

while (level > 0 && head.forward[level] == null)Adjust current max level if top levels become empty to optimize.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

class Skiplist {
    struct Node {
        int val;
        Node** forward;
        Node(int v, int level) {
            val = v;
            forward = new Node*[level + 1];
            for (int i = 0; i <= level; i++) forward[i] = nullptr;
        }
        ~Node() { delete[] forward; }
    };
    Node* head;
    int level;
    static const int MAX_LEVEL = 4;
    static constexpr float P = 0.5;

    int randomLevel() {
        int lvl = 0;
        while (((float) rand() / RAND_MAX) < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

public:
    Skiplist() {
        srand(time(nullptr));
        level = 0;
        head = new Node(-1, MAX_LEVEL);
    }

    bool search(int target) {
        Node* curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < target) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        return curr && curr->val == target;
    }

    void add(int num) {
        Node* update[MAX_LEVEL + 1];
        Node* curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        int lvl = randomLevel();
        if (lvl > level) {
            for (int i = level + 1; i <= lvl; i++) {
                update[i] = head;
            }
            level = lvl;
        }
        Node* newNode = new Node(num, lvl);
        for (int i = 0; i <= lvl; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }

    bool erase(int num) {
        Node* update[MAX_LEVEL + 1];
        Node* curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];
        if (!curr || curr->val != num) return false;
        for (int i = 0; i <= level; i++) {
            if (update[i]->forward[i] != curr) continue;
            update[i]->forward[i] = curr->forward[i];
        }
        delete curr;
        while (level > 0 && head->forward[level] == nullptr) {
            level--;
        }
        return true;
    }
};

int main() {
    Skiplist skiplist;
    skiplist.add(1);
    skiplist.add(2);
    skiplist.add(3);
    cout << boolalpha << skiplist.search(0) << endl; // false
    skiplist.add(4);
    cout << skiplist.search(1) << endl; // true
    cout << skiplist.erase(0) << endl;  // false
    cout << skiplist.erase(1) << endl;  // true
    cout << skiplist.search(1) << endl; // false
    return 0;
}

Line Notes

Node** forward;Dynamic array of forward pointers for each level to enable multi-level traversal.

while (((float) rand() / RAND_MAX) < P && lvl < MAX_LEVEL)Randomly assign node level for balancing the Skiplist.

for (int i = level; i >= 0; i--)Traverse from top level down for search and insert to improve efficiency.

update[i] = curr;Track nodes before insertion points at each level to update pointers.

delete curr;Free memory of erased node to prevent memory leaks.

class Node {
    constructor(val, level) {
        this.val = val;
        this.forward = new Array(level + 1).fill(null);
    }
}

class Skiplist {
    constructor() {
        this.MAX_LEVEL = 4;
        this.P = 0.5;
        this.level = 0;
        this.head = new Node(-1, this.MAX_LEVEL);
    }

    randomLevel() {
        let lvl = 0;
        while (Math.random() < this.P && lvl < this.MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }

    search(target) {
        let curr = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (curr.forward[i] && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        return curr !== null && curr.val === target;
    }

    add(num) {
        const update = new Array(this.MAX_LEVEL + 1);
        let curr = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (curr.forward[i] && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        const lvl = this.randomLevel();
        if (lvl > this.level) {
            for (let i = this.level + 1; i <= lvl; i++) {
                update[i] = this.head;
            }
            this.level = lvl;
        }
        const newNode = new Node(num, lvl);
        for (let i = 0; i <= lvl; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    erase(num) {
        const update = new Array(this.MAX_LEVEL + 1);
        let curr = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (curr.forward[i] && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        if (!curr || curr.val !== num) return false;
        for (let i = 0; i <= this.level; i++) {
            if (update[i].forward[i] !== curr) continue;
            update[i].forward[i] = curr.forward[i];
        }
        while (this.level > 0 && this.head.forward[this.level] === null) {
            this.level--;
        }
        return true;
    }
}

// Test
const skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
console.log(skiplist.search(0)); // false
skiplist.add(4);
console.log(skiplist.search(1)); // true
console.log(skiplist.erase(0));  // false
console.log(skiplist.erase(1));  // true
console.log(skiplist.search(1)); // false

Line Notes

this.forward = new Array(level + 1).fill(null);Each node has multiple forward pointers for levels to enable multi-level traversal.

while (Math.random() < this.P && lvl < this.MAX_LEVEL)Randomly assign node level to balance the Skiplist structure.

for (let i = this.level; i >= 0; i--)Traverse from top level down for search and insert to improve efficiency.

update[i] = curr;Track nodes before insertion points at each level to update pointers during add or erase.

while (this.level > 0 && this.head.forward[this.level] === null)Reduce max level if top levels become empty to optimize structure.

⏱

Complexity

TimeAverage O(log n) per operation

SpaceO(n) for nodes and pointers

Randomized levels reduce the number of nodes traversed, achieving logarithmic average time complexity.

💡 For n=1000, operations typically scan about 10 nodes instead of 1000, greatly improving speed.

Interview Verdict: Accepted and efficient average case

This is the standard Skiplist design used in practice, balancing simplicity and performance.

🧠

Skiplist with Dynamic Max Level and Probability Tuning

💡 This approach improves flexibility by dynamically adjusting max levels based on size and tuning promotion probability for better performance.

Intuition

Instead of fixed max level, calculate max level from current size to optimize space and speed. Adjust promotion probability accordingly.

Algorithm

1. Maintain current size of Skiplist and compute max level as log2(size).
2. Adjust promotion probability to 0.5 or other values for balancing.
3. During add, use dynamic max level and probability for node promotion.
4. Search and erase remain similar but respect dynamic levels.

💡 This adds complexity but can yield better performance for varying input sizes.

</>

Code

import random
import math

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

class Skiplist:
    def __init__(self):
        self.size = 0
        self.P = 0.5
        self.head = Node(-1, 0)
        self.level = 0

    def max_level(self):
        return max(1, int(math.log2(self.size + 1)))

    def random_level(self):
        lvl = 0
        max_lvl = self.max_level()
        while random.random() < self.P and lvl < max_lvl:
            lvl += 1
        return lvl

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

    def add(self, num: int) -> None:
        update = [None] * (self.max_level() + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr
        lvl = self.random_level()
        if lvl > self.level:
            for i in range(self.level + 1, lvl + 1):
                update[i] = self.head
            self.level = lvl
        new_node = Node(num, lvl)
        for i in range(lvl + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node
        self.size += 1

    def erase(self, num: int) -> bool:
        update = [None] * (self.max_level() + 1)
        curr = self.head
        for i in range(self.level, -1, -1):
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            update[i] = curr
        curr = curr.forward[0]
        if curr is None or curr.val != num:
            return False
        for i in range(self.level + 1):
            if update[i].forward[i] != curr:
                continue
            update[i].forward[i] = curr.forward[i]
        while self.level > 0 and self.head.forward[self.level] is None:
            self.level -= 1
        self.size -= 1
        return True

# Driver code
if __name__ == '__main__':
    skiplist = Skiplist()
    skiplist.add(1)
    skiplist.add(2)
    skiplist.add(3)
    print(skiplist.search(0))  # False
    skiplist.add(4)
    print(skiplist.search(1))  # True
    print(skiplist.erase(0))   # False
    print(skiplist.erase(1))   # True
    print(skiplist.search(1))  # False

Line Notes

self.size = 0Track number of elements to compute max level dynamically for adaptive structure.

def max_level(self):Calculate max level based on current size to optimize space and speed.

while random.random() < self.P and lvl < max_lvl:Randomly promote node up to dynamic max level to balance Skiplist.

self.size += 1Increment size after insertion to update max level for future operations.

self.size -= 1Decrement size after deletion to update max level and maintain structure.

import java.util.Random;

class Skiplist {
    private int size;
    private final double P = 0.5;

    private class Node {
        int val;
        Node[] forward;
        Node(int val, int level) {
            this.val = val;
            forward = new Node[level + 1];
        }
    }

    private Node head;
    private int level;
    private Random rand;

    public Skiplist() {
        size = 0;
        head = new Node(-1, 0);
        level = 0;
        rand = new Random();
    }

    private int maxLevel() {
        return Math.max(1, (int)(Math.log(size + 1) / Math.log(2)));
    }

    private int randomLevel() {
        int lvl = 0;
        int maxLvl = maxLevel();
        while (rand.nextDouble() < P && lvl < maxLvl) {
            lvl++;
        }
        return lvl;
    }

    public boolean search(int target) {
        Node curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        return curr != null && curr.val == target;
    }

    public void add(int num) {
        Node[] update = new Node[maxLevel() + 1];
        Node curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        int lvl = randomLevel();
        if (lvl > level) {
            for (int i = level + 1; i <= lvl; i++) {
                update[i] = head;
            }
            level = lvl;
        }
        Node newNode = new Node(num, lvl);
        for (int i = 0; i <= lvl; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
        size++;
    }

    public boolean erase(int num) {
        Node[] update = new Node[maxLevel() + 1];
        Node curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr.forward[i] != null && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        if (curr == null || curr.val != num) {
            return false;
        }
        for (int i = 0; i <= level; i++) {
            if (update[i].forward[i] != curr) continue;
            update[i].forward[i] = curr.forward[i];
        }
        while (level > 0 && head.forward[level] == null) {
            level--;
        }
        size--;
        return true;
    }

    public static void main(String[] args) {
        Skiplist skiplist = new Skiplist();
        skiplist.add(1);
        skiplist.add(2);
        skiplist.add(3);
        System.out.println(skiplist.search(0)); // false
        skiplist.add(4);
        System.out.println(skiplist.search(1)); // true
        System.out.println(skiplist.erase(0));  // false
        System.out.println(skiplist.erase(1));  // true
        System.out.println(skiplist.search(1)); // false
    }
}

Line Notes

private int size;Track number of elements for dynamic max level calculation.

return Math.max(1, (int)(Math.log(size + 1) / Math.log(2)));Calculate max level based on current size to adapt Skiplist height.

while (rand.nextDouble() < P && lvl < maxLvl)Randomly promote node up to dynamic max level for balancing.

size++;Increment size after insertion to update max level.

size--;Decrement size after deletion to maintain accurate size.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;

class Skiplist {
    struct Node {
        int val;
        Node** forward;
        Node(int v, int level) {
            val = v;
            forward = new Node*[level + 1];
            for (int i = 0; i <= level; i++) forward[i] = nullptr;
        }
        ~Node() { delete[] forward; }
    };
    Node* head;
    int level;
    int size;
    static constexpr float P = 0.5;

    int maxLevel() {
        return max(1, (int)log2(size + 1));
    }

    int randomLevel() {
        int lvl = 0;
        int maxLvl = maxLevel();
        while (((float) rand() / RAND_MAX) < P && lvl < maxLvl) {
            lvl++;
        }
        return lvl;
    }

public:
    Skiplist() {
        srand(time(nullptr));
        size = 0;
        level = 0;
        head = new Node(-1, 0);
    }

    bool search(int target) {
        Node* curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < target) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        return curr && curr->val == target;
    }

    void add(int num) {
        Node* update[64];
        Node* curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        int lvl = randomLevel();
        if (lvl > level) {
            for (int i = level + 1; i <= lvl; i++) {
                update[i] = head;
            }
            level = lvl;
        }
        Node* newNode = new Node(num, lvl);
        for (int i = 0; i <= lvl; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
        size++;
    }

    bool erase(int num) {
        Node* update[64];
        Node* curr = head;
        for (int i = level; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];
        if (!curr || curr->val != num) return false;
        for (int i = 0; i <= level; i++) {
            if (update[i]->forward[i] != curr) continue;
            update[i]->forward[i] = curr->forward[i];
        }
        delete curr;
        while (level > 0 && head->forward[level] == nullptr) {
            level--;
        }
        size--;
        return true;
    }
};

int main() {
    Skiplist skiplist;
    skiplist.add(1);
    skiplist.add(2);
    skiplist.add(3);
    cout << boolalpha << skiplist.search(0) << endl; // false
    skiplist.add(4);
    cout << skiplist.search(1) << endl; // true
    cout << skiplist.erase(0) << endl;  // false
    cout << skiplist.erase(1) << endl;  // true
    cout << skiplist.search(1) << endl; // false
    return 0;
}

Line Notes

int size;Track number of elements for dynamic max level calculation.

return max(1, (int)log2(size + 1));Calculate max level based on current size to adapt Skiplist height.

while (((float) rand() / RAND_MAX) < P && lvl < maxLvl)Randomly promote node up to dynamic max level for balancing.

size++;Increment size after insertion to update max level.

size--;Decrement size after deletion to maintain accurate size.

class Node {
    constructor(val, level) {
        this.val = val;
        this.forward = new Array(level + 1).fill(null);
    }
}

class Skiplist {
    constructor() {
        this.level = 0;
        this.size = 0;
        this.P = 0.5;
        this.head = new Node(-1, 0);
    }

    maxLevel() {
        return Math.max(1, Math.floor(Math.log2(this.size + 1)));
    }

    randomLevel() {
        let lvl = 0;
        let maxLvl = this.maxLevel();
        while (Math.random() < this.P && lvl < maxLvl) {
            lvl++;
        }
        return lvl;
    }

    search(target) {
        let curr = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (curr.forward[i] && curr.forward[i].val < target) {
                curr = curr.forward[i];
            }
        }
        curr = curr.forward[0];
        return curr !== null && curr.val === target;
    }

    add(num) {
        const update = new Array(this.maxLevel() + 1);
        let curr = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (curr.forward[i] && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        const lvl = this.randomLevel();
        if (lvl > this.level) {
            for (let i = this.level + 1; i <= lvl; i++) {
                update[i] = this.head;
            }
            this.level = lvl;
        }
        const newNode = new Node(num, lvl);
        for (let i = 0; i <= lvl; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
        this.size++;
    }

    erase(num) {
        const update = new Array(this.maxLevel() + 1);
        let curr = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (curr.forward[i] && curr.forward[i].val < num) {
                curr = curr.forward[i];
            }
            update[i] = curr;
        }
        curr = curr.forward[0];
        if (!curr || curr.val !== num) return false;
        for (let i = 0; i <= this.level; i++) {
            if (update[i].forward[i] !== curr) continue;
            update[i].forward[i] = curr.forward[i];
        }
        while (this.level > 0 && this.head.forward[this.level] === null) {
            this.level--;
        }
        this.size--;
        return true;
    }
}

// Test
const skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
console.log(skiplist.search(0)); // false
skiplist.add(4);
console.log(skiplist.search(1)); // true
console.log(skiplist.erase(0));  // false
console.log(skiplist.erase(1));  // true
console.log(skiplist.search(1)); // false

Line Notes

this.size = 0;Track number of elements for dynamic max level calculation.

return Math.max(1, Math.floor(Math.log2(this.size + 1)));Calculate max level based on current size to adapt Skiplist height.

while (Math.random() < this.P && lvl < maxLvl)Randomly promote node up to dynamic max level for balancing.

this.size++;Increment size after insertion to update max level.

this.size--;Decrement size after deletion to maintain accurate size.

⏱

Complexity

TimeAverage O(log n) per operation with adaptive max level

SpaceO(n) with dynamic pointer arrays

Dynamic max level adapts to size, potentially improving space and time efficiency for large inputs.

💡 For n=10000, max level ~14, so operations traverse fewer nodes than fixed small max level.

Interview Verdict: Accepted and adaptive for large scale

This approach is more complex but can yield better performance and memory usage in practice.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, approach 2 (standard Skiplist) is the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Single Level Linked List)	O(n) per operation	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Skiplist with Multiple Levels and Randomized Promotion	Average O(log n)	O(n)	No	Yes	Code this approach for best balance of clarity and performance
3. Skiplist with Dynamic Max Level and Probability Tuning	Average O(log n) with adaptive tuning	O(n)	No	Yes	Mention as optimization for large scale, rarely code in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe brute force single linked list approach and its limitations.Step 3: Introduce Skiplist multi-level design with randomization.Step 4: Discuss dynamic max level tuning for large inputs.Step 5: Code the chosen approach and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

Interviewer tests your understanding of linked list pointers, probabilistic data structures, and ability to implement complex pointer manipulations correctly and efficiently.

Common Follow-ups

• How to handle duplicates? → Allow multiple nodes with same value, erase removes one occurrence.
• What is the worst-case time complexity? → O(n) if unlucky randomization, but average O(log n).

💡 Follow-ups test your understanding of Skiplist nuances and edge cases.

🔍

Pattern Recognition

When to Use

1) Need O(log n) search, insert, delete; 2) Want simpler alternative to balanced trees; 3) Problem mentions probabilistic or multi-level linked lists; 4) Custom data structure design question.

Signature Phrases

'Design a data structure that supports search, add, erase in O(log n) average time''Use multiple levels of linked lists with probabilistic promotion'

NOT This Pattern When

Balanced BST or AVL tree design problems which use strict balancing instead of probabilistic levels.

Similar Problems

Design Linked List - basic linked list operationsDesign HashMap - custom data structure designDesign Balanced BST - alternative O(log n) search structure

Practice

1. You are given a list of buildings represented as triplets (left, right, height). The goal is to output the skyline formed by these buildings as a list of key points where the height changes. Which algorithmic approach guarantees an optimal solution with time complexity O(n log n)?

easy

A. Divide and conquer approach that recursively merges skylines of building subsets

B. Dynamic programming approach that stores maximum heights for subproblems

C. Greedy approach that iteratively picks the tallest building at each x-coordinate

D. Brute force simulation by iterating over all x-coordinates and tracking max height

Solution

1. Step 1: Understand problem requirements

   The problem requires merging multiple building outlines into a single skyline efficiently.

2. Step 2: Evaluate algorithmic approaches

   Greedy and brute force approaches either fail to guarantee optimal time or are inefficient. Dynamic programming is not a natural fit here. Divide and conquer merges smaller skylines efficiently in O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer merges sorted skylines efficiently [OK]

Hint: Divide and conquer merges sorted skylines in O(n log n) [OK]

Common Mistakes:

• Thinking greedy or brute force is optimal
• Confusing DP with skyline merging

2. What is the time complexity of the checkOut operation in the optimal UndergroundSystem implementation that uses a linked list for check-ins, assuming n is the number of active check-ins at the time of checkout?

medium

A. O(1) because the linked list head always points to the correct check-in node

B. O(n) due to updating route data hash map entries

C. O(log n) because the linked list is sorted by check-in time

D. O(n) because it may need to traverse the linked list to find the matching check-in node

Solution

1. Step 1: Identify linked list traversal

   The checkOut method traverses the linked list from head to find the node with matching id, which can take up to O(n) time.

2. Step 2: Analyze route data update

   Updating the hash map for route data is O(1) average, so it does not dominate complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Traversal over n nodes dominates, so O(n) time [OK]

Hint: Linked list traversal dominates checkOut time [OK]

Common Mistakes:

• Assuming O(1) because head is used directly

3. What is the worst-case time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list where each node may have a child list, and why?

medium

A. O(n) because each node is visited once.

B. O(n) with O(n) auxiliary space for recursion stack.

C. O(n log n) due to repeated merging of child lists.

D. O(n^2) because finding the tail of each child list requires traversing child nodes repeatedly.

Solution

1. Step 1: Identify the costly operation

   Finding the tail of each child list requires traversing that child list fully.

2. Step 2: Analyze nested traversal effect

   Since this tail-finding happens for multiple nodes, total time can be quadratic in number of nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Repeated tail traversal causes O(n^2) time in worst case [OK]

Hint: Repeated tail search causes quadratic time [OK]

Common Mistakes:

• Assuming linear time because each node is visited once
• Confusing recursion stack space with iterative approach

4. What is the average time complexity of the remove operation in the optimized Insert Delete GetRandom O(1) with duplicates data structure that uses a hash map of element to linked list nodes and a list of elements?

medium

A. O(n) because we need to find the element's index in the list before removal.

B. O(log n) due to maintaining the linked list structure during removals.

C. O(1) worst-case because linked list removals and hash map lookups are constant time.

D. O(1) average because the hash map provides direct access to an element's node for removal.

Solution

1. Step 1: Identify data structure operations

   Removal uses hash map to get a node reference in O(1) average time, then removes node from doubly linked list in O(1).

2. Step 2: Clarify average vs worst-case

   Hash map lookups are average O(1), but worst-case can degrade. Linked list removal is always O(1). So overall average is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map + linked list enables average O(1) removals [OK]

Hint: Hash map + linked list enables average O(1) removals [OK]

Common Mistakes:

• Confusing average and worst-case complexities
• Assuming linked list removal is O(log n)
• Thinking index search is needed

5. Suppose the UndergroundSystem is extended to allow multiple check-ins by the same passenger without requiring a check-out first (i.e., passengers can start multiple trips before finishing any). Which modification to the data structure or algorithm is necessary to handle this correctly?

hard

A. Keep a stack of check-in nodes per passenger id to track multiple active trips.

B. Use a hash map from passenger id to a single check-in node, overwriting previous check-ins.

C. Store all check-ins in a linked list and traverse fully on each checkOut to find the earliest unmatched check-in.

D. Disallow multiple check-ins by the same passenger to avoid complexity.

Solution

1. Step 1: Understand the problem extension

   Passengers can have multiple active trips simultaneously, so a single check-in per id is insufficient.

2. Step 2: Choose data structure to track multiple check-ins

   A stack per passenger id allows tracking multiple check-ins in order, enabling correct matching on checkOut.

3. Step 3: Why other options fail

   Overwriting check-ins loses data (A). Traversing full list each time (C) is inefficient. Disallowing multiple check-ins (D) is not a solution.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Stack per id supports multiple active trips correctly [OK]

Hint: Stack per id tracks multiple active check-ins [OK]

Common Mistakes:

• Overwriting check-in info loses data