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. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

2. You need to design a system that supports posting tweets and retrieving the 10 most recent tweets from a user's timeline, including tweets from users they follow. Which approach best balances efficient posting and retrieving the top recent tweets in real-time?

easy

A. Store all tweets in a global list and scan it entirely each time to find the top 10 recent tweets.

B. Maintain a linked list of tweets per user, a hashmap for followees, and use a max heap to merge the most recent tweets from followees efficiently.

C. Use a dynamic programming approach to precompute the top tweets for each user after every post.

D. Use a simple array per user and sort all tweets from followees every time the feed is requested.

Solution

1. Step 1: Understand the problem constraints

   The system must support fast posting and retrieving the top 10 recent tweets from a user's followees including themselves.

2. Step 2: Evaluate approaches

   Brute force scanning or sorting all tweets each time is inefficient. DP is not applicable here. Using linked lists per user and a max heap for merging recent tweets achieves O(1) posting and O(k log F) retrieval, where F is followees count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linked list + hashmap + heap is the optimal pattern for this problem [OK]

Hint: Linked list + heap merges recent tweets efficiently [OK]

Common Mistakes:

• Thinking sorting all tweets each time is efficient
• Trying DP for a streaming feed problem

3. You need to design a data structure that supports setting values at indices, taking snapshots of the entire array state, and retrieving values at any snapshot efficiently. Which approach best balances time and space complexity for frequent set and get operations?

easy

A. Store full copies of the array on every snapshot to allow O(1) get operations.

B. Maintain a hash map per index storing (snap_id, value) pairs and use binary search to retrieve values for get operations.

C. Use a single global hash map keyed by (index, snap_id) and perform linear search for get operations.

D. Use a segment tree to store snapshots and query values at any snapshot.

Solution

1. Step 1: Understand problem requirements

   The data structure must efficiently support set, snap, and get operations with many snapshots and updates.

2. Step 2: Evaluate approaches

   Storing full snapshots (B) uses too much space and is slow for many snaps. A global hash map with linear search (C) makes get operations slow. Segment trees (D) are complex and not optimal here. Using a hash map per index with binary search (A) allows O(1) amortized set and snap, and O(log m) get, balancing time and space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per index enables fast retrieval [OK]

Hint: Binary search per index enables fast retrieval [OK]

Common Mistakes:

• Thinking full snapshots are efficient for many snaps
• Using linear search for get causes slow queries

4. What is the time complexity of the get operation in the optimal SnapshotArray implementation that uses a hash map per index with binary search, assuming m snapshots and k set operations?

medium

A. O(1) because values are stored directly per index and snap_id

B. O(k) because get must scan all set operations for the index

C. O(m) because linear search is needed over all snapshots

D. O(log m) because binary search is performed on at most m entries per index

Solution

1. Step 1: Identify data structure for get

   Each index stores a sorted list of (snap_id, value) pairs, with length up to number of set operations k but bounded by m snapshots.

2. Step 2: Analyze get operation

   Get uses binary search on this list to find the value for the requested snap_id, which takes O(log m) time since at most one entry per snapshot per index.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search on sorted snapshot list yields O(log m) [OK]

Hint: Binary search on snapshots per index yields O(log m) get time [OK]

Common Mistakes:

• Assuming get is O(1) due to direct indexing
• Confusing linear search with binary search

5. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness