Design Skip List Lite

Implement a simplified skip list with search, insert, and delete operations.

skip-list linked-list search insert delete

Design a simplified skip list data structure that supports three operations: `insert`, `search`, and `delete`. All operations work on integer values (duplicates are not allowed).

Implement a class `SkipListLite` with the following methods:
- `__init__(self)` – initializes an empty skip list.
- `insert(self, num: int) -> None` – inserts `num` into the skip list. If `num` already exists, do nothing.
- `search(self, num: int) -> bool` – returns `True` if `num` is present, `False` otherwise.
- `delete(self, num: int) -> bool` – removes `num` from the skip list and returns `True` if `num` was present, `False` otherwise.

The internal structure must use a randomized level assignment to approximate O(log n) performance. Use a constant `MAX_LEVEL = 4` for the maximum number of levels. Use the `random` module to decide promotion: when inserting, start at level 0; while `random.random() < 0.5` and `level < MAX_LEVEL - 1`, increment the level. The level is assigned per inserted node.

You must implement the standard skip list search/insert/delete algorithms using forward pointers at each level. Do not use built-in sorted containers or sort methods.

Provide your implementation in the `SkipListLite` class. The grader will instantiate your class and call methods in sequence.

Constraints

Number of operations ≤ 10^4. Values are integers within [-10^9, 10^9]. The skip list should have at most 4 levels. Expected average time per operation is O(log n), worst-case O(n) due to randomization. Memory usage O(n * max_level).

Example

>>> sl = SkipListLite()
>>> sl.insert(5)
>>> sl.search(5)
True
>>> sl.insert(3)
>>> sl.insert(7)
>>> sl.search(7)
True
>>> sl.delete(3)
True
>>> sl.search(3)
False
>>> sl.delete(3)
False

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a sentinel 'head' node with forward pointers for each level.

For search, start from the highest level and move downward, advancing as long as the next node's value is less than the target.

During insert, collect the update nodes at each level that need to point to the new node.

For delete, you must reassign forward pointers and remove the node; if the node is not found, return False.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.