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

Sollicitatievraag bij Google

Gevolgde bedrijven

Vacatures