Exercise: Skiplists

Solve a task to modify the find() method in a skiplist.

We'll cover the following

Task

The find(x) method in a Skiplist sometimes performs redundant comparisons; these occur when x is compared to the same value more than once. They can occur when, for some node, u, u.next[r] = u.next[r − 1]. Modify the find(x) method so that these redundant comparisons can be avoided.

Sample input

The sample input will be as follows:

The first 25 values in a skiplist will be using this formula: i % 100 + 900
The next 50 values in a skiplist will be using this formula: i % 50
The next 25 values in a skiplist will be using this formula: i % 20

Expected output

The expected output will be as follows:

Adding 1000 elements
Searching
Found: 10, null, null

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy