Meta 真实面试题：如何用前缀和快速回答「子数组里有多少个 1」？

题目正文（原文）

// 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

这题是典型的「区间和多次查询」问题，标准解是先预处理一维前缀和数组 prefix[i] 为前 i 个元素中 1 的个数，然后每次查询在 O(1) 时间用 prefix[end] – prefix[start-1] 求出答案。考察点是空间换时间、预处理思想和 API 设计

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Meta、Google、Amazon 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Stripe 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。