Design Skiplist

Hard
2095.

Design Skiplist

HardLinked ListDesignGoogleMicrosoft

Design Skiplist is a hard coding problem on linked list and design, asked in Google and Microsoft interviews.

Implement a skiplist without using any built-in ordered library. A skiplist keeps its values in sorted linked lists stacked in levels: the bottom level holds every value, and each value is also copied up into the next level with probability 1/2. A search starts at the top level and drops down a level whenever the next value would overshoot, so search, add and erase all take O(log n) expected time.

The same value may be stored more than once. Write the class Skiplist:

  • Skiplist() creates an empty skiplist.
  • boolean search(int target) returns whether target is stored.
  • void add(int num) stores num (another copy if it is already there).
  • boolean erase(int num) removes one copy of num and returns true, or returns false (and changes nothing) if num is not stored.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["Skiplist","add","add","add","search","erase","search","erase","search","erase","search"] [[],[7],[7],[3],[7],[7],[7],[7],[7],[7],[3]]
Output
[null,null,null,null,true,true,true,true,false,false,true]
Explanation
7 is stored twice. The first erase removes one copy, so 7 is still found; the second removes the other. A third erase finds nothing to remove. 3 was never touched.

Example 2

Input
["Skiplist","search","add","add","search","erase","search"] [[],[0],[0],[20000],[20000],[0],[0]]
Output
[null,false,null,null,true,true,false]
Explanation
0 and 20000 are the smallest and largest values allowed.

Constraints

  • 0 <= num, target <= 2 * 10^4
  • At most 5 * 10^4 calls are made in total to search, add and erase
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 */
var Skiplist = function() {
    
};

/**
 * @param {number} target
 * @return {boolean}
 */
Skiplist.prototype.search = function(target) {
    
};

/**
 * @param {number} num
 * @return {void}
 */
Skiplist.prototype.add = function(num) {
    
};

/**
 * @param {number} num
 * @return {boolean}
 */
Skiplist.prototype.erase = function(num) {
    
};

Sign in to run your own test cases

Sign in

Design Skiplist — Solution in Python, Java & C++

Design Skiplist solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on linked list and design.

Design Skiplist is a hard coding problem on linked list and design, asked in Google and Microsoft interviews.

  • Difficulty: Hard
  • Topics: Linked List, Design
  • Asked at: Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Implement a skiplist without using any built-in ordered library. A skiplist keeps its values in sorted linked lists stacked in levels: the bottom level holds every value, and each value is also copied up into the next level with probability 1/2. A search starts at the top level and drops down a level whenever the next value would overshoot, so search, add and erase all take O(log n) expected time.

The same value may be stored more than once. Write the class Skiplist:

  • Skiplist() creates an empty skiplist.
  • boolean search(int target) returns whether target is stored.
  • void add(int num) stores num (another copy if it is already there).
  • boolean erase(int num) removes one copy of num and returns true, or returns false (and changes nothing) if num is not stored.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["Skiplist","add","add","add","search","erase","search","erase","search","erase","search"]
[[],[7],[7],[3],[7],[7],[7],[7],[7],[7],[3]]
Output: [null,null,null,null,true,true,true,true,false,false,true]
Explanation: 7 is stored twice. The first erase removes one copy, so 7 is still found; the second removes the other. A third erase finds nothing to remove. 3 was never touched.

Example 2

Input: ["Skiplist","search","add","add","search","erase","search"]
[[],[0],[0],[20000],[20000],[0],[0]]
Output: [null,false,null,null,true,true,false]
Explanation: 0 and 20000 are the smallest and largest values allowed.

Constraints

  • 0 <= num, target <= 2 * 10^4
  • At most 5 * 10^4 calls are made in total to search, add and erase

Hints for Design Skiplist

  1. Hint 1

    Start from a sorted linked list: search is O(n) because you can only step one node at a time. Add express lanes — higher levels that skip over many nodes.

  2. Hint 2

    Give each new node a random height: level 1 always, and each further level with probability 1/2 (up to a cap such as 16). A head node with the full height starts every level.

  3. Hint 3

    All three operations begin the same way: from the top level down, move right while the next value is smaller than the key, and remember the last node visited on each level. Those are the nodes whose next pointers an insertion or deletion rewires.

How to solve Design Skiplist

A skiplist is a sorted linked list with probabilistic express lanes. Walking from the top lane down, every operation finds, on each level, the last node before the key — the "update path" — in O(log n) expected steps; inserting or deleting a node is then only a matter of splicing it into or out of those lanes.

Approach

  1. Keep a head node with L = 16 forward pointers (enough for far more than 5 · 10^4 values).
  2. path(key): start at the head on level L - 1; on each level move right while the next node's value is < key, record the current node as path[level], then go down a level.
  3. search(target): the node after path[0] on level 0 is the first value >= target; report whether it equals target.
  4. add(num): pick a height h (1, plus one more level with probability 1/2 each time, at most L). For levels 0..h-1, set node.next[lv] = path[lv].next[lv] and path[lv].next[lv] = node.
  5. erase(num): let node be the node after path[0] on level 0; if it is missing or holds another value, return false. Otherwise, on each of its levels, set path[lv].next[lv] = node.next[lv], and return true.

Why it works

Every level is a sorted sub-list of the level below, so moving right while values are smaller never skips a value >= key, and dropping a level only refines the position; path[0] is therefore the last node of the whole list below key. Because heights double the gap between express stops on average, each level is crossed in O(1) expected steps, giving O(log n) expected work. With duplicates, the node after path[0] is the first copy, and on each of its levels it is also the first node >= num, so path[lv].next[lv] is exactly that node.

Complexity

  • Time — O(log n) expected per operation
  • Space — O(n) expected (about two pointers per value)

Pitfalls

  • Use strict < while walking right; with <=, a search would step past the copies it is looking for.
  • erase removes one copy only and must report false without touching the list when the value is absent.
  • The coin flips only affect speed: the stored values, and so every answer, are the same whatever the random heights are.

Reference solution

Python

import random

class SkipNode:
    __slots__ = ("value", "nxt")

    def __init__(self, value, height):
        self.value = value
        self.nxt = [None] * height

class Skiplist:
    LEVELS = 16

    def __init__(self):
        self.head = SkipNode(-1, self.LEVELS)

    def _path(self, key):  # on every level, the last node with value < key
        path = [None] * self.LEVELS
        cur = self.head
        for lv in range(self.LEVELS - 1, -1, -1):
            while cur.nxt[lv] is not None and cur.nxt[lv].value < key:
                cur = cur.nxt[lv]
            path[lv] = cur
        return path

    def search(self, target: int) -> bool:
        node = self._path(target)[0].nxt[0]
        return node is not None and node.value == target

    def add(self, num: int) -> None:
        path = self._path(num)
        height = 1
        while height < self.LEVELS and random.random() < 0.5:
            height += 1
        node = SkipNode(num, height)
        for lv in range(height):
            node.nxt[lv] = path[lv].nxt[lv]
            path[lv].nxt[lv] = node

    def erase(self, num: int) -> bool:
        path = self._path(num)
        node = path[0].nxt[0]
        if node is None or node.value != num:
            return False
        for lv in range(len(node.nxt)):
            if path[lv].nxt[lv] is node:
                path[lv].nxt[lv] = node.nxt[lv]
        return True

Java

class Skiplist {
    private static final int LEVELS = 16;

    private static class Node {
        int value;
        Node[] nxt;
        Node(int value, int height) { this.value = value; nxt = new Node[height]; }
    }

    private final Node head = new Node(-1, LEVELS);
    private final Random rnd = new Random();

    public Skiplist() {
    }

    private Node[] path(int key) { // on every level, the last node with value < key
        Node[] path = new Node[LEVELS];
        Node cur = head;
        for (int lv = LEVELS - 1; lv >= 0; lv--) {
            while (cur.nxt[lv] != null && cur.nxt[lv].value < key) cur = cur.nxt[lv];
            path[lv] = cur;
        }
        return path;
    }

    public boolean search(int target) {
        Node node = path(target)[0].nxt[0];
        return node != null && node.value == target;
    }

    public void add(int num) {
        Node[] path = path(num);
        int height = 1;
        while (height < LEVELS && rnd.nextBoolean()) height++;
        Node node = new Node(num, height);
        for (int lv = 0; lv < height; lv++) {
            node.nxt[lv] = path[lv].nxt[lv];
            path[lv].nxt[lv] = node;
        }
    }

    public boolean erase(int num) {
        Node[] path = path(num);
        Node node = path[0].nxt[0];
        if (node == null || node.value != num) return false;
        for (int lv = 0; lv < node.nxt.length; lv++) {
            if (path[lv].nxt[lv] == node) path[lv].nxt[lv] = node.nxt[lv];
        }
        return true;
    }
}

C++

class Skiplist {
    static const int LEVELS = 16;
    struct Node {
        int value;
        vector<Node*> nxt;
        Node(int v, int h) : value(v), nxt(h, nullptr) {}
    };
    Node* head = new Node(-1, LEVELS);

    void path(int key, Node** out) { // on every level, the last node with value < key
        Node* cur = head;
        for (int lv = LEVELS - 1; lv >= 0; lv--) {
            while (cur->nxt[lv] && cur->nxt[lv]->value < key) cur = cur->nxt[lv];
            out[lv] = cur;
        }
    }
public:
    Skiplist() {}

    bool search(int target) {
        Node* p[LEVELS];
        path(target, p);
        Node* node = p[0]->nxt[0];
        return node && node->value == target;
    }

    void add(int num) {
        Node* p[LEVELS];
        path(num, p);
        int height = 1;
        while (height < LEVELS && (rand() & 1)) height++;
        Node* node = new Node(num, height);
        for (int lv = 0; lv < height; lv++) {
            node->nxt[lv] = p[lv]->nxt[lv];
            p[lv]->nxt[lv] = node;
        }
    }

    bool erase(int num) {
        Node* p[LEVELS];
        path(num, p);
        Node* node = p[0]->nxt[0];
        if (!node || node->value != num) return false;
        for (int lv = 0; lv < (int)node->nxt.size(); lv++) {
            if (p[lv]->nxt[lv] == node) p[lv]->nxt[lv] = node->nxt[lv];
        }
        delete node;
        return true;
    }
};

JavaScript

var SK_LEVELS = 16;

function SkipNode(value, height) {
    this.value = value;
    this.nxt = new Array(height);
    for (var i = 0; i < height; i++) this.nxt[i] = null;
}

var Skiplist = function() {
    this.head = new SkipNode(-1, SK_LEVELS);
};

Skiplist.prototype.path = function(key) { // on every level, the last node with value < key
    var path = new Array(SK_LEVELS), cur = this.head;
    for (var lv = SK_LEVELS - 1; lv >= 0; lv--) {
        while (cur.nxt[lv] !== null && cur.nxt[lv].value < key) cur = cur.nxt[lv];
        path[lv] = cur;
    }
    return path;
};

Skiplist.prototype.search = function(target) {
    var node = this.path(target)[0].nxt[0];
    return node !== null && node.value === target;
};

Skiplist.prototype.add = function(num) {
    var path = this.path(num), height = 1;
    while (height < SK_LEVELS && Math.random() < 0.5) height++;
    var node = new SkipNode(num, height);
    for (var lv = 0; lv < height; lv++) {
        node.nxt[lv] = path[lv].nxt[lv];
        path[lv].nxt[lv] = node;
    }
};

Skiplist.prototype.erase = function(num) {
    var path = this.path(num), node = path[0].nxt[0];
    if (node === null || node.value !== num) return false;
    for (var lv = 0; lv < node.nxt.length; lv++) {
        if (path[lv].nxt[lv] === node) path[lv].nxt[lv] = node.nxt[lv];
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.