Practice/Meta/Leetcode 1206. Design Skiplist

Leetcode 1206. Design Skiplist

CodingOptional

Problem

Design and implement a Skip List data structure that supports efficient insertion, deletion, and search operations. A skip list is a probabilistic data structure that allows O(log n) average time complexity for these operations by maintaining multiple levels of linked lists.

In a skip list:

• The bottom level (level 0) contains all elements in sorted order
• Higher levels contain a subset of elements from lower levels, acting as "express lanes"
• Each element has a random tower height determined probabilistically
• Operations traverse from the highest level downward, skipping over elements when possible

Your implementation should support the following operations:

• search(target): Returns true if the target value exists in the skip list, false otherwise
• add(num): Inserts a value into the skip list (duplicates are allowed)
• remove(num): Removes one occurrence of a value from the skip list if it exists, returns true if removed, false otherwise

Requirements

1. Implement a SkipList class with methods for search, add, and remove
2. Support duplicate values (multiple copies of the same number can be stored)
3. Maintain sorted order of elements at all levels
4. Use probabilistic level generation (typically 50% chance to promote to next level)
5. Handle edge cases like removing from an empty list or searching for non-existent values

Constraints

• 0 ≤ num, target ≤ 20000
• At most 50000 total operations will be performed
• The skip list should support at least 16 levels for optimal performance
• Average time complexity should be O(log n) for all operations
• Space complexity is O(n) where n is the number of elements

Examples

Example 1:

` Operations: skiplist = SkipList() skiplist.add(1) skiplist.add(2) skiplist.add(3) skiplist.search(1) // returns true skiplist.search(4) // returns false

Explanation: The skip list contains {1, 2, 3}. Searching for 1 finds it, but 4 is not present. `

Example 2:

` Operations: skiplist = SkipList() skiplist.add(5) skiplist.add(5) skiplist.remove(5) // returns true skiplist.search(5) // returns true

Explanation: After adding 5 twice, one remove operation leaves one copy of 5 remaining. `

Example 3:

` Operations: skiplist = SkipList() skiplist.remove(10) // returns false skiplist.add(10) skiplist.add(15) skiplist.add(20) skiplist.search(15) // returns true skiplist.remove(20) // returns true skiplist.search(20) // returns false

Explanation: Removing from empty list returns false. After additions, elements can be found and removed. `