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. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child lists can themselves have children, and so on. Which approach best guarantees an in-place flattening of this multilevel list into a single-level doubly linked list without using extra space?

easy

A. Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.

B. Use a recursive depth-first traversal that returns the tail of each flattened child list to connect nodes.

C. Apply a greedy approach that always appends child lists at the end of the main list after full traversal.

D. Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flattening a multilevel doubly linked list in-place without extra space.

2. Step 2: Identify the approach that guarantees in-place flattening without extra space

   Using a recursive depth-first traversal that returns the tail of each flattened child list allows splicing child lists correctly and efficiently without extra data structures.

3. Step 3: Evaluate other options

   Iterative splicing (Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.) can cause repeated tail searches leading to O(n^2) time and is less straightforward. Greedy appending (Apply a greedy approach that always appends child lists at the end of the main list after full traversal.) fails to maintain order. Dynamic programming (Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.) is not applicable.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Recursive DFS approach is standard and efficient for in-place flattening [OK]

Hint: Recursive DFS returns tail to connect lists efficiently [OK]

Common Mistakes:

• Assuming iterative splicing is always best despite complexity
• Appending child lists only at the end
• Using DP which is not applicable here

2. Examine the following buggy code snippet from the AllOne data structure. Which line contains the subtle bug that causes keys to remain in multiple buckets after incrementing, leading to incorrect max/min results?

def inc(self, key: str) -> None:
    if key not in self.key_to_bucket:
        if 1 not in self.count_to_bucket:
            new_bucket = Bucket(1)
            self._insert_bucket_after(new_bucket, self.head)
        self.count_to_bucket[1].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[1]
    else:
        curr_bucket = self.key_to_bucket[key]
        next_count = curr_bucket.count + 1
        if next_count not in self.count_to_bucket:
            new_bucket = Bucket(next_count)
            self._insert_bucket_after(new_bucket, curr_bucket)
        self.count_to_bucket[next_count].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[next_count]
        # BUG: Missing removal of key from old bucket
        # curr_bucket.keys.remove(key)
        if len(curr_bucket.keys) == 0:
            self._remove_bucket(curr_bucket)

medium

A. Line removing key from old bucket's keys set (commented out)

B. Line updating key_to_bucket mapping

C. Line removing empty bucket if keys set is empty

D. Line adding key to new bucket's keys set

Solution

1. Step 1: Identify key movement between buckets

   When incrementing, key must be removed from old bucket's keys set.

2. Step 2: Locate missing removal

   The commented out line that removes the key from old bucket is missing, causing key to appear in multiple buckets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without removal, max/min queries become incorrect due to duplicate keys [OK]

Hint: Key must be removed from old bucket after increment [OK]

Common Mistakes:

• Forgetting to remove key from old bucket after increment/decrement

3. What is the time complexity of performing n operations (push, pop, increment) on the optimal CustomStack implementation that uses a lazy increment array?

medium

A. O(n * k), where k is the increment size

B. O(n + k), where k is the maximum increment size

C. O(n log n), due to increment propagation

D. O(n), total for all operations combined

Solution

1. Step 1: Analyze push and pop operations

   Each push and pop is O(1) amortized, as they add or remove one element.

2. Step 2: Analyze increment operation

   Increment only updates inc array at one index, O(1) per call. Propagation happens lazily during pop, each element's increment propagated once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All n operations combined run in O(n) total time [OK]

Hint: Lazy increments make all operations O(1) amortized, total O(n) [OK]

Common Mistakes:

• Assuming increment is O(k) per call
• Confusing total time with per-operation time

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

5. Suppose you want to extend the LRU Cache to support a "reuse" operation that marks an existing key as recently used without retrieving its value. Which modification to the optimal LRU Cache implementation is correct to support this efficiently?

hard

A. On reuse, remove the key from the cache and re-insert it with the same value.

B. Do nothing; reuse is equivalent to get, so no code change is needed.

C. Use a queue instead of a doubly linked list to track usage order for easier reuse.

D. Add a new method that calls _remove and _add on the node corresponding to the key.

Solution

1. Step 1: Understand reuse operation

   Reuse means marking a key as recently used without returning its value, so usage order must be updated.

2. Step 2: Efficiently update usage order

   Calling _remove and _add on the node moves it to the front in O(1) time, correctly updating usage.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Reuse requires usage update without value retrieval, done by repositioning node [OK]

Hint: Reuse updates usage order like get but without returning value [OK]

Common Mistakes:

• Re-inserting wastes time
• Queue can't reorder efficiently
• Assuming reuse needs no code change