Question

Are the below statements true about skiplists?

In a sorted set of elements skip lists can implement the below operations

i.given a element find closest element to the given value in the sorted set in O(logn)

ii.find the number of elements in the set whose values fall a given range in O(logn)

(a) true

(b) false

This is a very interesting question from Skip List topic in section Types of Lists of Data Structures & Algorithms I

This question was addressed to me during a job interview.

Answer 1

Right option is (a) true

The explanation is: To achieve above operations augment with few additional stuff like partial counts.