Index intersection merge
A planner can answer a multi-column AND predicate by intersecting two single-column indexes (index intersection / bitmap AND). You are given two posting lists, each a sorted list of unique int row_ids that match one predicate. Return the sorted list of row_ids present in BOTH lists (the AND result). Do this with a single linear merge of the two sorted lists (no set construction is required, though correctness is what is checked). Lists may be large (up to 1e5 each) and may be empty.
Implement
index_intersect(a: list[int], b: list[int]) → list[int]Examples
in
[[1,3,5,7,9],[3,4,5,6,9]]out[3,5,9]What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 30 min
solution.py
InputExpectedGot
[[1,3,5,7,9],[3,4,5,6,9]][3,5,9]not run yetsample