The question was:

Given a sparse bit array A of size M stored in a database. The database provides an API query(L,R) which returns 1 if there is at least one bit equal to one in A[L..R] and 0 otherwise.

You want to find all the 1 bits in a reasonable number of queries. E.g. for array 01100000001, positions of 1 bits are {1, 2, 10}.

Return the array of all the positions of 1's.

T.C - It should not be linear.
S.C - It should be constant.

You should not use recursion or extra function. (this part was the followup to the recursive and queue approach)

Question

The question was:

Given a sparse bit array A of size M stored in a database. The database provides an API query(L,R) which returns 1 if there is at least one bit equal to one in A[L..R] and 0 otherwise.

You want to find all the 1 bits in a reasonable number of queries. E.g. for array 01100000001, positions of 1 bits are {1, 2, 10}.

Return the array of all the positions of 1's.

T.C -> It should not be linear.
S.C -> It should be constant.

You should not use recursion or extra function. (this part was the followup to the recursive and queue approach)

Google

Google Interview Question

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?