Answer Repeated Range Aggregate Queries on a Static BST
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
## Problem
A fixed binary search tree has been converted once by an in-order traversal into
the JSON-portable array `sortedValues`, which is sorted in nondecreasing order
and repeats duplicate node values. Given `queries`, where each query is
`[low, high]`, return one `[sum, count]` pair per query for all values in that
inclusive range. Return `[0, 0]` for an empty range result. Preprocess the fixed
array so repeated queries do not scan all values.
### Constraints & Assumptions
- `0 <= len(sortedValues) <= 200,000`, and duplicate values appear once per BST node.
- There are at most 200,000 queries.
- Values and range bounds are 32-bit signed integers.
- Use signed 64-bit prefix sums in Java and C++; the stated bounds keep every sum within `+/-2^53`, so Python integers and JavaScript numbers are exact as well.
### Clarifications
- Range endpoints are inclusive and `low <= high`.
- Duplicates contribute separately to both sum and count.
- The public function receives `sortedValues` and `queries`; it does not receive or construct a custom tree-node type.
- Return results in the same order as the queries, and let the caller compute an average as `sum / count` when count is nonzero.
### Examples
```text
sortedValues = [1, 3, 3, 5, 8]
queries = [[3, 5], [6, 7]]
output = [[11, 3], [0, 0]]
```
### Hints
```hint Exploit the fixed input
Convert the tree's ordered values into a representation that supports prefix aggregates.
```
```hint Locate query boundaries
Two binary searches can isolate the inclusive slice for each query.
```
Overview: Preprocess a sorted array derived from a static BST to answer many inclusive range queries. Use binary-search boundaries and wide prefix sums to return both the sum and count for each range without rescanning the tree.
Read the full Meta Software Engineer interview experience this question came from
A fixed binary search tree has already been converted by in-order traversal into sortedValues, a nondecreasing array that contains one entry per node, including duplicates. For each inclusive [low, high] query, return [sum, count] for all array values in that range, or [0, 0] when none match. Preserve query order and preprocess the fixed array so repeated queries do not scan every value.
Constraints
- 0 <= len(sortedValues) <= 200000.
- sortedValues is nondecreasing and repeats duplicate values once per BST node.
- There are at most 200000 queries.
- Each query is [low, high] with low <= high and inclusive endpoints.
- Values and range bounds are signed 32-bit integers.
- Every sum remains within +/-2^53 and requires signed 64-bit prefix sums in Java and C++.
Examples
Input: ([1, 3, 3, 5, 8], [[3, 5], [6, 7]])
Expected Output: [[11, 3], [0, 0]]
Explanation: This is the source example; duplicate threes contribute separately and the second range is empty.
Input: ([], [[-1, 1], [0, 0]])
Expected Output: [[0, 0], [0, 0]]
Explanation: Every query over an empty value array has zero sum and count.
Hints
- Precompute prefix sums over the fixed sorted array.
- Use lower and upper bounds to isolate each inclusive query slice.