Query an Indexed In-Memory Numeric Table
Company: Retell
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Query an Indexed In-Memory Numeric Table
### Problem
Implement `queryIndexedRows(rows, queries) -> answers` for one immutable in-memory table containing only integer values.
Each query contains one or more inclusive range filters. A filter is `[column, low, high]` and accepts a row when `low <= row[column] <= high`. Filters in the same query are combined with logical AND. For each query, return the zero-based indices of all accepted rows in ascending order.
Build reusable column indexes once before answering the queries. A solution that scans every table row independently for every query does not meet the requirement.
### Function Contract
- `rows` is a JSON array of equal-length JSON integer arrays.
- `queries` is a JSON array; each query is an array of filters, and each filter is a three-integer array `[column, low, high]`.
- Return a JSON array of integer arrays, one answer per query in encounter order.
- Repeated values, duplicate rows, and repeated filters are allowed. Rows remain distinct by index.
- Do not mutate `rows` or `queries`.
The four language signatures use only homogeneous integer containers:
- Python: `def queryIndexedRows(rows: list[list[int]], queries: list[list[list[int]]]) -> list[list[int]]`
- JavaScript: `function queryIndexedRows(rows, queries)` returns an array of integer arrays.
- Java: `List<List<Integer>> queryIndexedRows(List<List<Integer>> rows, List<List<List<Integer>>> queries)`
- C++: `vector<vector<int>> queryIndexedRows(const vector<vector<int>>& rows, const vector<vector<vector<int>>>& queries)`
### Constraints
- `1 <= rows.length <= 20,000`.
- `1 <= rows[0].length <= 20`, and every row has that same length.
- `1 <= queries.length <= 2,000`.
- `1 <= queries[i].length <= rows[0].length`.
- `0 <= column < rows[0].length` and `-1,000,000,000 <= low <= high <= 1,000,000,000`.
- Every table value is between `-1,000,000,000` and `1,000,000,000`.
- Let `B` be the byte length of `[rows, queries]` serialized as compact UTF-8 JSON, with no whitespace and every punctuation, sign, and digit byte counted. Inputs satisfy `B <= 96,000`.
- Let `R` be the compact UTF-8 JSON byte length of the returned nested integer array under the same rule. Inputs guarantee `R <= 96,000`. Thus the fully serialized input plus result is at most `192,000` bytes.
- Target preprocessing time `O(c * n log n)` and index space `O(c * n)`, where `n` is the row count and `c` is the column count.
- For a filter, use binary search in its column index to identify the inclusive value range. Combine candidate row IDs without scanning all `n` rows for each query. Account for the candidate IDs inspected, intersected, sorted, and emitted in the query cost.
### Examples
```text
rows = [
[10, 5, 100],
[20, 5, 90],
[15, 8, 100],
[10, 7, 80]
]
queries = [
[[0, 10, 15]],
[[0, 10, 20], [1, 5, 5]],
[[2, 95, 105], [0, 11, 30]]
]
answers = [[0, 2, 3], [0, 1], [2]]
```
```text
rows = [[4, 4], [4, 4], [9, 1]]
queries = [
[[0, 4, 4], [1, 4, 4]],
[[0, 5, 8]]
]
answers = [[0, 1], []]
```
```hint Intersect the smallest candidate ranges first
Each column index can expose a bounded slice by binary search. Starting with the shortest slice can reduce the intermediate membership work for an AND query.
```
### Discussion Requirements
1. Describe the per-column index and how lower and upper bounds find an inclusive range.
2. Explain how duplicate values and duplicate rows retain distinct row indices.
3. Compare hash-set intersection with sorted-list intersection for multiple filters.
4. Explain why the final answer order may require sorting even when a value index is sorted by value.
5. Describe unit tests for exact boundaries, no matches, repeated filters, negative values, and all rows matching.
Quick Answer: Build reusable column indexes for an immutable numeric table, then answer range-filter queries that combine conditions with logical AND. The task tests binary-search boundaries, candidate intersection, duplicate row identity, deterministic output ordering, and honest preprocessing and query costs.
Implement `queryIndexedRows(rows, queries)` for one immutable in-memory table whose cells are all integers.
`rows` is a rectangular table: `rows[i][j]` is the value in row `i`, column `j`, and every row has the same length. A row is identified by its zero-based index, so two rows holding identical values are still two different rows.
A **filter** is a three-integer array `[column, low, high]`. It accepts row `i` when `low <= rows[i][column] <= high` -- both endpoints inclusive.
A **query** is a non-empty array of filters combined with logical AND: a row is accepted by the query only when *every* filter in that query accepts it. The same column may appear in more than one filter of a query, and an identical filter may be listed more than once; repeating a filter never changes that query's answer.
### Output
Return one answer per query, in the same order the queries were given.
- Each answer is the list of zero-based indices of the rows that query accepts, **in ascending index order**.
- A query that accepts no row contributes an **empty list** in its slot -- never a missing slot, never a sentinel value.
- Answers are never merged, deduplicated, or reordered across queries.
Do not mutate `rows` or `queries`.
### Intended approach
Build reusable per-column indexes **once**, before answering any query, then answer each query from those indexes. Re-scanning all `n` table rows for every query is exactly what this problem asks you to avoid: for a filter, binary-search that column's index for the inclusive value range, and combine candidate row ids without touching every row. Grading only inspects returned values, so the index requirement is a design requirement rather than something a test can observe directly -- but the largest test is sized so a per-query full scan is meaningfully more work than an indexed lookup.
### Signatures
- Python: `def queryIndexedRows(rows, queries)` with `rows: list[list[int]]`, `queries: list[list[list[int]]]`, returning `list[list[int]]`
- JavaScript: `function queryIndexedRows(rows, queries)` returning an array of integer arrays
- Java: `public java.util.List<java.util.List<Integer>> queryIndexedRows(java.util.List<java.util.List<Integer>> rows, java.util.List<java.util.List<java.util.List<Integer>>> queries)`
- C++: `std::vector<std::vector<int>> queryIndexedRows(const std::vector<std::vector<int>>& rows, const std::vector<std::vector<std::vector<int>>>& queries)`
`queries` is always one argument and is never split into parallel arrays.
### Constraints
- `1 <= rows.length <= 20,000`.
- `1 <= rows[0].length <= 20`, and every row has exactly that length.
- `1 <= queries.length <= 2,000`.
- `1 <= queries[i].length <= rows[0].length` -- every query carries at least one filter and never more filters than the table has columns. Only the filter *count* is capped; the same column may legally be reused across those filters.
- Each filter is exactly three integers `[column, low, high]` with `0 <= column < rows[0].length` and `-1,000,000,000 <= low <= high <= 1,000,000,000`. `low <= high` is guaranteed, so no inverted range occurs.
- `-1,000,000,000 <= rows[i][j] <= 1,000,000,000`.
- Repeated values, duplicate rows, and repeated filters are all allowed; rows stay distinct by index.
- Let `B` be the byte length of `[rows, queries]` serialized as compact UTF-8 JSON, with no whitespace and every punctuation, sign, and digit byte counted. Inputs satisfy `B <= 96,000`.
- Let `R` be the compact UTF-8 JSON byte length of the returned nested integer array under the same rule. Inputs guarantee `R <= 96,000`. The fully serialized input plus result is therefore at most `192,000` bytes.
- Target preprocessing time `O(c * n log n)` and index space `O(c * n)`, where `n` is the row count and `c` is the column count. Account for the candidate ids inspected, intersected, sorted, and emitted in the per-query cost.
### Numeric range
Every table value and every filter bound satisfies `|value| <= 10^9 < 2^31 - 1`, and every returned number is a row index below `20,000`. Both fit in a signed 32-bit integer, so `int` is sufficient in Java and C++ and no 64-bit or big-integer handling is required. Compare values directly rather than subtracting them: a difference such as `-1,000,000,000 - 1,000,000,000` does not fit in signed 32 bits.
### Examples
**Example 1**
```text
rows = [
[10, 5, 100],
[20, 5, 90],
[15, 8, 100],
[10, 7, 80]
]
queries = [
[[0, 10, 15]],
[[0, 10, 20], [1, 5, 5]],
[[2, 95, 105], [0, 11, 30]]
]
answers = [[0, 2, 3], [0, 1], [2]]
```
Query 0 keeps every row whose column 0 lies in `[10, 15]`: rows 0, 2 and 3. Query 1 ANDs column 0 in `[10, 20]` with column 1 exactly `5`, which only rows 0 and 1 satisfy. Query 2 needs column 2 in `[95, 105]` (rows 0 and 2) and column 0 in `[11, 30]` (rows 1 and 2), leaving row 2 alone.
**Example 2**
```text
rows = [[4, 4], [4, 4], [9, 1]]
queries = [
[[0, 4, 4], [1, 4, 4]],
[[0, 5, 8]]
]
answers = [[0, 1], []]
```
Rows 0 and 1 are identical yet remain two separate answers, because a row is identified by its index. The second query matches nothing, so its slot holds an empty list rather than disappearing.
Constraints
- 1 <= rows.length <= 20,000
- 1 <= rows[0].length <= 20, and every row has exactly that length
- 1 <= queries.length <= 2,000
- 1 <= queries[i].length <= rows[0].length (at least one filter per query, never more filters than the table has columns; only the filter count is capped, so the same column may be reused across those filters)
- Each filter is exactly three integers [column, low, high] with 0 <= column < rows[0].length and -1,000,000,000 <= low <= high <= 1,000,000,000 (low <= high is guaranteed)
- -1,000,000,000 <= rows[i][j] <= 1,000,000,000
- Repeated values, duplicate rows, and repeated filters are all allowed; rows stay distinct by index
- Let B be the byte length of [rows, queries] serialized as compact UTF-8 JSON, with no whitespace and every punctuation, sign, and digit byte counted. Inputs satisfy B <= 96,000
- Let R be the compact UTF-8 JSON byte length of the returned nested integer array under the same rule. Inputs guarantee R <= 96,000, so input plus result is at most 192,000 bytes
- Target preprocessing time O(c * n log n) and index space O(c * n), where n is the row count and c is the column count; account for the candidate ids inspected, intersected, sorted, and emitted in the per-query cost
- All values fit in a signed 32-bit integer (|value| <= 10^9 < 2^31 - 1) and every returned number is a row index below 20,000, so no 64-bit or big-integer handling is required
Examples
Input: ([[10,5,100],[20,5,90],[15,8,100],[10,7,80]],[[[0,10,15]],[[0,10,20],[1,5,5]],[[2,95,105],[0,11,30]]])
Expected Output: [[0,2,3],[0,1],[2]]
Input: ([[4,4],[4,4],[9,1]],[[[0,4,4],[1,4,4]],[[0,5,8]]])
Expected Output: [[0,1],[]]
Hints
- One sorted array per column -- the row ids ordered by that column's value, alongside the values themselves -- can be built once and reused by every query. For an inclusive [low, high] range, where does a lower bound land and where does an upper bound land?
- Within one query, the filters select candidate ranges of very different widths. If you start from the narrowest one, how many rows are left to check the other filters against, and how does that compare to the table size?
- A per-column index is ordered by value, not by row id. What does that imply about the order candidates come out in, versus the order the answer is required to be in?