Code RoomIndex page fetches
EasyPrep Room Coding #4775

Index page fetches

CodingDatabases & SQLStorage & CDNEntry–Mid~16 min

A reporting engine answers each query through an unclustered secondary index. The index hands back one pointer per matching row, in index key order, and a pointer names the heap page that row lives on. The engine holds exactly one heap page at a time, so walking the pointers in index order fetches a page whenever the next pointer names a page other than the one it is already holding, and a page left behind can be fetched again later. A bitmap scan instead gathers all the pointers first, sorts them, and fetches each distinct page exactly once. Each entry of queries is one query's pointer list, in index order. Return a list holding, for each query in input order, how many page fetches the bitmap scan saves. A query that matched nothing saves 0. Return an empty list when no queries are given.

Implement
bitmap_scan_savings(queries: list[list[int]]) → list[int]
Examples
in[[[4,4,7,7,4],[9],[2,5,2,5]]]out[1,0,2]
in[[[11,11,11,12,12,13]]]out[0]
in[[[3,8,3,8,3,8,3]]]out[5]
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 16 min
InputExpectedGot
[[[4,4,7,7,4],[9],[2,5,2,5]]][1,0,2]not run yetsample
[[[11,11,11,12,12,13]]][0]not run yetsample
[[[3,8,3,8,3,8,3]]][5]not run yetsample