Given n integers in the range 0 to k, answers any query about how many of the n integers fall into a range [a b] in O(1) time. Make your own assumptions and build your own indexing data structures.

PS: I was used to ask this question during my interviews. Now no longer ;-)

Only static arrays (when retrieval is done by the index, i.e. A[5]) and perfect hash tables offer constant search time.

ReplyDeleteWe will call the given n-sized array as array A. We allocate an array of k elements. We call this array B. Then

for (i = 0; i < k; i++) {

B[i] = number of elements from A >= i

}

Therefore array B will store:

B[0] = number of elements from A >= 0

B[1] = number of elements from A >= 1

B[2] = number of elements from A >= 2

..

B[a] = number of elements from A >= a

B[b] = number of elements from A >= b

B[k-1] = number of elements from A >= k-1

Now the range query

"recover the number of elements >= a and <= b" is

answered by subtracting B[a]-B[b] with O(1) complexity.

complexity?

ReplyDeleteFor preprocessing -

ReplyDeleteMake an array c[k] in which c[i] holds the number of elements less than or equal to i. This will take O(n+k).

Now to answer the query we need to calculate c[b]-c[a-1]