// Given a large array of arbitrarily-placed 1's and 0's, write a service that answers the query
// "how many 1's in a given sub-array?". You should assume that the array is large, doesn't change,
// and is given to you ahead of time. The query will be called many times, so it needs to be fast.
Array: [0 0 1 0 1 0]
Query API: int getOnes(start, end)
Input: 0, 2 Output: 1
Input: 2, 4 Output: 2
This problem is a classic range query task. The optimal solution precomputes a 1D prefix-sum array where prefix[i] stores the number of ones up to index , then each query runs in O(1) time using prefix[end] - prefix[start-1]. It tests preprocessing, time–space trade-offs, and clean API design.
The VOprep team has long accompanied candidates through various major company OAs and VOs, including Meta, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for these companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.
END
