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]