This occurred in April for a PhD 2025 New Grad SWE role. The recruiter reached out, and I applied.

The interview was very chill, lasting about 45 minutes. It started with a brief introduction and then moved directly into questions.

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. For example, for the array 01100000001, the positions of 1 bits are {1, 2, 10}.

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

Time Complexity (T.C): It should not be linear. Space Complexity (S.C): It should be constant.

You should not use recursion or extra functions.