Sunday, May 23, 2010

Count in a range in O(1)

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 ;-)

3 comments:

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

    We 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.

    ReplyDelete
  2. For preprocessing -
    Make 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]

    ReplyDelete