Losing head/tail while rewiring
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
Design a Skiplist without using any built-in libraries.
A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists.
For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way:
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n).
See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list
Implement the Skiplist class:
Skiplist() Initializes the object of the skiplist.bool search(int target) Returns true if the integer target exists in the Skiplist or false otherwise.void add(int num) Inserts the value num into the SkipList.bool erase(int num) Removes the value num from the Skiplist and returns true. If num does not exist in the Skiplist, do nothing and return false. If there exist multiple num values, removing any one of them is fine.Note that duplicates may exist in the Skiplist, your code needs to handle this situation.
Example 1:
Input ["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"] [[], [1], [2], [3], [0], [4], [1], [0], [1], [1]] Output [null, null, null, null, false, null, true, false, true, false] Explanation Skiplist skiplist = new Skiplist(); skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // return False skiplist.add(4); skiplist.search(1); // return True skiplist.erase(0); // return False, 0 is not in skiplist. skiplist.erase(1); // return True skiplist.search(1); // return False, 1 has already been erased.
Constraints:
0 <= num, target <= 2 * 1045 * 104 calls will be made to search, add, and erase.Problem summary: Design a Skiplist without using any built-in libraries. A skiplist is a data structure that takes O(log(n)) time to add, erase and search. Comparing with treap and red-black tree which has the same function and performance, the code length of Skiplist can be comparatively short and the idea behind Skiplists is just simple linked lists. For example, we have a Skiplist containing [30,40,50,60,70,90] and we want to add 80 and 45 into it. The Skiplist works this way: Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons You can see there are many layers in the Skiplist. Each layer is a sorted linked list. With the help of the top layers, add, erase and search can be faster than O(n). It can be proven that the average time complexity for each operation is O(log(n)) and space complexity is O(n). See more about Skiplist: https://en.wikipedia.org/wiki/Skip_list Implement the Skiplist class:
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Linked List · Design
["Skiplist","add","add","add","search","add","search","erase","erase","search"] [[],[1],[2],[3],[0],[4],[1],[0],[1],[1]]
design-hashset)design-hashmap)design-linked-list)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1206: Design Skiplist
class Skiplist {
private static final int MAX_LEVEL = 32;
private static final double P = 0.25;
private static final Random RANDOM = new Random();
private final Node head = new Node(-1, MAX_LEVEL);
private int level = 0;
public Skiplist() {
}
public boolean search(int target) {
Node curr = head;
for (int i = level - 1; i >= 0; --i) {
curr = findClosest(curr, i, target);
if (curr.next[i] != null && curr.next[i].val == target) {
return true;
}
}
return false;
}
public void add(int num) {
Node curr = head;
int lv = randomLevel();
Node node = new Node(num, lv);
level = Math.max(level, lv);
for (int i = level - 1; i >= 0; --i) {
curr = findClosest(curr, i, num);
if (i < lv) {
node.next[i] = curr.next[i];
curr.next[i] = node;
}
}
}
public boolean erase(int num) {
Node curr = head;
boolean ok = false;
for (int i = level - 1; i >= 0; --i) {
curr = findClosest(curr, i, num);
if (curr.next[i] != null && curr.next[i].val == num) {
curr.next[i] = curr.next[i].next[i];
ok = true;
}
}
while (level > 1 && head.next[level - 1] == null) {
--level;
}
return ok;
}
private Node findClosest(Node curr, int level, int target) {
while (curr.next[level] != null && curr.next[level].val < target) {
curr = curr.next[level];
}
return curr;
}
private static int randomLevel() {
int level = 1;
while (level < MAX_LEVEL && RANDOM.nextDouble() < P) {
++level;
}
return level;
}
static class Node {
int val;
Node[] next;
Node(int val, int level) {
this.val = val;
next = new Node[level];
}
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* Skiplist obj = new Skiplist();
* boolean param_1 = obj.search(target);
* obj.add(num);
* boolean param_3 = obj.erase(num);
*/
// Accepted solution for LeetCode #1206: Design Skiplist
func init() { rand.Seed(time.Now().UnixNano()) }
const (
maxLevel = 16
p = 0.5
)
type node struct {
val int
next []*node
}
func newNode(val, level int) *node {
return &node{
val: val,
next: make([]*node, level),
}
}
type Skiplist struct {
head *node
level int
}
func Constructor() Skiplist {
return Skiplist{
head: newNode(-1, maxLevel),
level: 1,
}
}
func (this *Skiplist) Search(target int) bool {
p := this.head
for i := this.level - 1; i >= 0; i-- {
p = findClosest(p, i, target)
if p.next[i] != nil && p.next[i].val == target {
return true
}
}
return false
}
func (this *Skiplist) Add(num int) {
level := randomLevel()
if level > this.level {
this.level = level
}
node := newNode(num, level)
p := this.head
for i := this.level - 1; i >= 0; i-- {
p = findClosest(p, i, num)
if i < level {
node.next[i] = p.next[i]
p.next[i] = node
}
}
}
func (this *Skiplist) Erase(num int) bool {
ok := false
p := this.head
for i := this.level - 1; i >= 0; i-- {
p = findClosest(p, i, num)
if p.next[i] != nil && p.next[i].val == num {
p.next[i] = p.next[i].next[i]
ok = true
}
}
for this.level > 1 && this.head.next[this.level-1] == nil {
this.level--
}
return ok
}
func findClosest(p *node, level, target int) *node {
for p.next[level] != nil && p.next[level].val < target {
p = p.next[level]
}
return p
}
func randomLevel() int {
level := 1
for level < maxLevel && rand.Float64() < p {
level++
}
return level
}
/**
* Your Skiplist object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Search(target);
* obj.Add(num);
* param_3 := obj.Erase(num);
*/
# Accepted solution for LeetCode #1206: Design Skiplist
class Node:
__slots__ = ['val', 'next']
def __init__(self, val: int, level: int):
self.val = val
self.next = [None] * level
class Skiplist:
max_level = 32
p = 0.25
def __init__(self):
self.head = Node(-1, self.max_level)
self.level = 0
def search(self, target: int) -> bool:
curr = self.head
for i in range(self.level - 1, -1, -1):
curr = self.find_closest(curr, i, target)
if curr.next[i] and curr.next[i].val == target:
return True
return False
def add(self, num: int) -> None:
curr = self.head
level = self.random_level()
node = Node(num, level)
self.level = max(self.level, level)
for i in range(self.level - 1, -1, -1):
curr = self.find_closest(curr, i, num)
if i < level:
node.next[i] = curr.next[i]
curr.next[i] = node
def erase(self, num: int) -> bool:
curr = self.head
ok = False
for i in range(self.level - 1, -1, -1):
curr = self.find_closest(curr, i, num)
if curr.next[i] and curr.next[i].val == num:
curr.next[i] = curr.next[i].next[i]
ok = True
while self.level > 1 and self.head.next[self.level - 1] is None:
self.level -= 1
return ok
def find_closest(self, curr: Node, level: int, target: int) -> Node:
while curr.next[level] and curr.next[level].val < target:
curr = curr.next[level]
return curr
def random_level(self) -> int:
level = 1
while level < self.max_level and random.random() < self.p:
level += 1
return level
# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)
# obj.add(num)
# param_3 = obj.erase(num)
// Accepted solution for LeetCode #1206: Design Skiplist
use std::collections::HashMap;
struct Skiplist {
data: HashMap<i32, usize>,
}
impl Skiplist {
fn new() -> Self {
let data = HashMap::new();
Skiplist { data }
}
fn search(&self, target: i32) -> bool {
self.data.contains_key(&target)
}
fn add(&mut self, num: i32) {
*self.data.entry(num).or_default() += 1;
}
fn erase(&mut self, num: i32) -> bool {
if !self.data.contains_key(&num) {
return false;
}
let count = self.data.get_mut(&num).unwrap();
*count -= 1;
if *count == 0 {
self.data.remove(&num);
}
true
}
}
#[test]
fn test() {
let mut obj = Skiplist::new();
obj.add(1);
obj.add(2);
obj.add(3);
assert_eq!(obj.search(0), false);
obj.add(4);
assert_eq!(obj.search(1), true);
assert_eq!(obj.erase(0), false);
assert_eq!(obj.erase(1), true);
assert_eq!(obj.search(1), false);
}
// Accepted solution for LeetCode #1206: Design Skiplist
class Node {
val: number;
next: (Node | null)[];
constructor(val: number, level: number) {
this.val = val;
this.next = Array(level).fill(null);
}
}
class Skiplist {
private static maxLevel: number = 32;
private static p: number = 0.25;
private head: Node;
private level: number;
constructor() {
this.head = new Node(-1, Skiplist.maxLevel);
this.level = 0;
}
search(target: number): boolean {
let curr = this.head;
for (let i = this.level - 1; i >= 0; i--) {
curr = this.findClosest(curr, i, target);
if (curr.next[i] && curr.next[i]!.val === target) {
return true;
}
}
return false;
}
add(num: number): void {
let curr = this.head;
const level = this.randomLevel();
const node = new Node(num, level);
this.level = Math.max(this.level, level);
for (let i = this.level - 1; i >= 0; i--) {
curr = this.findClosest(curr, i, num);
if (i < level) {
node.next[i] = curr.next[i];
curr.next[i] = node;
}
}
}
erase(num: number): boolean {
let curr = this.head;
let ok = false;
for (let i = this.level - 1; i >= 0; i--) {
curr = this.findClosest(curr, i, num);
if (curr.next[i] && curr.next[i]!.val === num) {
curr.next[i] = curr.next[i]!.next[i];
ok = true;
}
}
while (this.level > 1 && this.head.next[this.level - 1] === null) {
this.level--;
}
return ok;
}
private findClosest(curr: Node, level: number, target: number): Node {
while (curr.next[level] && curr.next[level]!.val < target) {
curr = curr.next[level]!;
}
return curr;
}
private randomLevel(): number {
let level = 1;
while (level < Skiplist.maxLevel && Math.random() < Skiplist.p) {
level++;
}
return level;
}
}
/**
* Your Skiplist object will be instantiated and called as such:
* var obj = new Skiplist()
* var param_1 = obj.search(target)
* obj.add(num)
* var param_3 = obj.erase(num)
*/
Use this to step through a reusable interview workflow for this problem.
Copy all n nodes into an array (O(n) time and space), then use array indexing for random access. Operations like reversal or middle-finding become trivial with indices, but the O(n) extra space defeats the purpose of using a linked list.
Most linked list operations traverse the list once (O(n)) and re-wire pointers in-place (O(1) extra space). The brute force often copies nodes to an array to enable random access, costing O(n) space. In-place pointer manipulation eliminates that.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pointer updates overwrite references before they are saved.
Usually fails on: List becomes disconnected mid-operation.
Fix: Store next pointers first and use a dummy head for safer joins.