Design Skiplist

📋

Problem

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.

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)

Edge cases: search in an empty Skiplist → falseerase a number not present → falseadd duplicate numbers and erase one occurrence → true

</>

IDE

class Skiplist: def __init__(self): pass def search(self, target: int) -> bool: pass def add(self, num: int) -> None: pass def erase(self, num: int) -> bool: passpublic class Skiplist { public Skiplist() {} public boolean search(int target) { return false; } public void add(int num) {} public boolean erase(int num) { return false; } }class Skiplist { public: Skiplist() {} bool search(int target) { return false; } void add(int num) {} bool erase(int num) { return false; } };class Skiplist { constructor() {} search(target) { return false; } add(num) {} erase(num) { return false; } }

class Skiplist:
    def __init__(self):
        # Write your solution here
        pass
    def search(self, target: int) -> bool:
        pass
    def add(self, num: int) -> None:
        pass
    def erase(self, num: int) -> bool:
        pass

public class Skiplist {
    public Skiplist() {
        // Write your solution here
    }
    public boolean search(int target) {
        return false;
    }
    public void add(int num) {
        // Write your solution here
    }
    public boolean erase(int num) {
        return false;
    }
}

class Skiplist {
public:
    Skiplist() {
        // Write your solution here
    }
    bool search(int target) {
        return false;
    }
    void add(int num) {
        // Write your solution here
    }
    bool erase(int num) {
        return false;
    }
};

class Skiplist {
    constructor() {
        // Write your solution here
    }
    search(target) {
        return false;
    }
    add(num) {
        // Write your solution here
    }
    erase(num) {
        return false;
    }
}

Common Bugs to Avoid

Wrong: [true, false, true, false]Erase method always returns true regardless of element presence.✅ Add a check before erase to confirm element exists; return false if not found. Detected by t1_01.

Wrong: [true, true, false, false]Search method returns false for existing elements due to incorrect traversal or comparison.✅ Ensure search traverses nodes correctly and compares target with node values properly. Detected by t1_02.

Wrong: [true, true, true, false]Add method inserts nodes at the end instead of sorted position, breaking search and erase.✅ Traverse to correct sorted position before inserting new node. Detected by t3_01.

Wrong: [false, false]Search and erase do not handle empty Skiplist correctly, possibly causing errors or wrong returns.✅ Check for empty head.next before traversal and return false if empty. Detected by t2_01.

Wrong: TLE or timeoutImplementation uses single-level linked list causing O(n) per operation, leading to timeout on large inputs.✅ Implement multi-level Skiplist with probabilistic promotion to achieve O(log n) average time. Detected by t4_01.

✓

Test Cases

Try testing your Skiplist on empty and minimal inputs to catch base case bugs.

Consider corner cases like duplicates and unordered insertions that break naive implementations.

Focus on optimizing your Skiplist to use multiple levels and probabilistic promotion to avoid timeouts.

t1_01basic

Input{"operations":["add","add","add","search","add","search","erase","erase","search"],"arguments":[[1],[2],[3],[0],[4],[1],[0],[1],[1]]}

Expected[false,true,false,false]

⏱ Performance - must finish in 2000ms

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.

💡 Simulate each operation step-by-step to understand the Skiplist behavior.

💡 Remember that search returns true only if the element exists; erase returns true only if the element was present and removed.

💡 Check that erase returns false when trying to remove a non-existent element and that search reflects the current state after each operation.

Why it failed: Incorrect output indicates failure to maintain correct element presence after add/erase operations. Fix by ensuring erase only removes existing elements and search checks current nodes properly. This is the canonical basic case test.

✓ Correctly handles add, search, and erase operations maintaining Skiplist integrity.

t1_02basic

Input{"operations":["add","add","search","erase","search","add","search"],"arguments":[[5],[10],[5],[5],[5],[7],[7]]}

Expected[true,true,false,true]

⏱ Performance - must finish in 2000ms

Add 5 and 10. Search 5 returns true. Erase 5 returns true. Search 5 now returns false. Add 7 and search 7 returns true.

💡 Focus on the effect of erase on the presence of elements.

💡 Check that search returns false after an element is erased.

💡 Ensure add inserts elements correctly and search finds them.

Why it failed: Failing this test usually means erase does not remove the element or search does not reflect updated state. Fix by updating pointers correctly on erase and verifying search traversal.

✓ Correctly updates Skiplist after add and erase, and search returns accurate presence.

t2_01edge

Input{"operations":["search","erase"],"arguments":[[10],[10]]}

Expected[false,false]

⏱ Performance - must finish in 2000ms

Searching and erasing in an empty Skiplist should return false.

💡 Test behavior on empty data structure.

💡 Check that search and erase handle empty head correctly.

💡 Ensure no null pointer exceptions and return false when no elements exist.

Why it failed: Returning true or error on empty Skiplist means missing base case checks for empty list. Fix by checking if head.next is None before traversal.

✓ Correctly returns false for search and erase on empty Skiplist.

t2_02edge

Input{"operations":["add","search","erase","search"],"arguments":[[-20000],[-20000],[-20000],[-20000]]}

Expected[true,true,true,false]

⏱ Performance - must finish in 2000ms

Add minimum allowed value -20000, search returns true, erase returns true, search after erase returns false.

💡 Test boundary values for num and target.

💡 Check that Skiplist handles negative and minimum values correctly.

💡 Ensure erase removes the element and search reflects the updated state.

Why it failed: Failing to handle boundary values or returning wrong search results indicates missing or incorrect comparisons. Fix by ensuring comparisons use <= and >= correctly.

✓ Handles minimum boundary values correctly with proper add, search, and erase.

t2_03edge

Input{"operations":["add","add","add","erase","search"],"arguments":[[100],[100],[100],[100],[100]]}

Expected[true,true,true,true,false]

⏱ Performance - must finish in 2000ms

Add duplicate 100 three times, erase once returns true, search returns true (two remain), erase twice more returns true, search returns false after all erased.

💡 Test handling of duplicate elements and partial erase.

💡 Check that erase removes only one occurrence at a time.

💡 Ensure search returns true if at least one occurrence exists.

Why it failed: If erase removes all duplicates at once or search returns false prematurely, fix by removing only one node per erase call and searching all nodes.

✓ Correctly handles duplicates with single occurrence erase and accurate search.

t3_01corner

Input{"operations":["add","add","add","search","erase","search"],"arguments":[[1],[3],[2],[2],[2],[2]]}

Expected[true,true,true,true,true,false]

⏱ Performance - must finish in 2000ms

Add 1,3,2 in unsorted order. Search 2 returns true. Erase 2 returns true. Search 2 returns false after erase.

💡 Test if implementation incorrectly assumes sorted insertion order.

💡 Check that add inserts nodes in correct sorted position.

💡 Fix by traversing to correct insertion point before adding.

Why it failed: Failing this test means add inserts at wrong position breaking order, causing search and erase to fail. Fix by inserting nodes in sorted order.

✓ Correctly inserts nodes in sorted order regardless of add call order.

t3_02corner

Input{"operations":["add","add","add","add","search","erase","search"],"arguments":[[5],[5],[5],[5],[5],[5],[5]]}

Expected[true,true,true,true,true,true,false]

⏱ Performance - must finish in 2000ms

Add 5 four times, search 5 returns true, erase 5 removes one occurrence returns true, search 5 still true (3 remain), erase 3 more times removes all, search 5 returns false.

💡 Test correct handling of multiple duplicates and multiple erases.

💡 Check that erase removes only one node per call.

💡 Fix by updating pointers carefully to remove single nodes.

Why it failed: If erase removes all duplicates at once or search returns false prematurely, fix by removing only one node per erase and searching all nodes.

✓ Correctly handles multiple duplicates with single occurrence erase.

t3_03corner

Input{"operations":["add","add","add","search","erase","search"],"arguments":[[1],[2],[3],[4],[4],[4]]}

Expected[true,true,true,false,false,false]

⏱ Performance - must finish in 2000ms

Add 1,2,3. Search 4 returns false. Erase 4 returns false. Search 4 returns false.

💡 Test searching and erasing elements never added.

💡 Check that erase returns false if element not found.

💡 Fix by verifying node existence before erase and returning false if absent.

Why it failed: Returning true on erase of non-existent element or incorrect search results means missing existence checks. Fix by checking node presence before erase.

✓ Correctly returns false for search and erase of non-existent elements.

t4_01performance

Input{"operations":["add","add","add","add","add","add","add","add","add","add","search","search","search","search","search","search","search","search","search","search","erase","erase","erase","erase","erase","erase","erase","erase","erase","erase"],"arguments":[[10000],[9999],[9998],[9997],[9996],[9995],[9994],[9993],[9992],[9991],[10000],[9999],[9998],[9997],[9996],[9995],[9994],[9993],[9992],[9991],[10000],[9999],[9998],[9997],[9996],[9995],[9994],[9993],[9992],[9991]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=30 operations with large values near upper bound. O(log n) average complexity expected to complete within 2 seconds.

💡 Focus on implementing efficient multi-level Skiplist with probabilistic promotion.

💡 Avoid linear scans; use levels to skip nodes and achieve O(log n) average time.

💡 Use randomization to decide node levels and maintain pointers for fast traversal.

Why it failed: TLE indicates use of linear scan or brute force linked list approach. Fix by implementing multi-level Skiplist with probabilistic node promotion to achieve O(log n) average complexity.

✓ Efficient Skiplist implementation confirmed with average O(log n) operations.

Practice

1. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] >= left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

Solution

1. Step 1: Trace bisect indices on empty starts list

   Initially, self.starts = []. Calling bisect_left([], 2) returns 0, and bisect_right([], 6) returns 0.

2. Step 2: Update intervals and starts

   Since i == 0, the first if condition is skipped. Also, j == 0, so second if is skipped. No intervals to delete. Insert left=2 at self.starts[0:0], so self.starts = [2]. Interval stored as {2:6}.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starts list after first addRange is [2] [OK]

Hint: Bisect on empty list returns 0, so starts list gets single element [OK]

Common Mistakes:

• Assuming right endpoint is also inserted in starts list

2. 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

3. 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

4. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Solution

1. Step 1: Analyze set() method

   The set method always appends (snap_id, val) without checking if the last entry has the same snap_id, causing duplicate entries for the same snap_id.

2. Step 2: Consequence on get()

   Duplicate entries for the same snap_id break binary search assumptions and can cause get to return incorrect values.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct code replaces last entry if snap_id matches [OK]

Hint: Check if last snap_id matches before appending in set() [OK]

Common Mistakes:

• Appending blindly causes duplicates
• Misunderstanding initialization defaults

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)