Level 1 Deferred maps
A query engine often builds a chain of column transformations long before anyone asks for a result, and it's wasteful to transform a million rows when the first match is at row 3. Build an integer array whose map calls are recorded and only run when a lookup needs them.
Implement class LazyArray:
LazyArray(values: list[int]): wrap the numbers. Take your own snapshot: later changes to the caller's list must not affect the array.map(fn) -> LazyArray: return a newLazyArraythat behaves like this one withfnapplied to every element (after all the maps already in the chain).mapmust not callfnand must not copy the values: it should be O(1). The array it was called on is unchanged, so one array can be the start of several different chains.index_of(target: int) -> int: the smallest index whose fully transformed value equalstarget, or-1if there is none.
Laziness rules for index_of, which the tests check by counting calls:
- Apply the chain's functions in order (the first
mapfirst), one element at a time from index0upward. - Stop as soon as you find a match. No function may run on any element after the matching index.
- The functions are pure (same input, same output), but they may be expensive.
a = LazyArray([10, 20, 30, 40])
b = a.map(lambda x: x // 10) # nothing computed yet
c = b.map(lambda x: x * x) # still nothing
c.index_of(9) # 2 (functions ran on indexes 0, 1, 2 only)
c.index_of(5) # -1
b.index_of(4) # 3
a.index_of(20) # 1 (a is unchanged by the maps)
a.map(lambda x: -x).index_of(-10) # 0
Constraints: up to 10^5 values, chains of up to 1000 maps.
Show hint
each LazyArray stores a reference to its parent and its own function (the root stores the values). To evaluate element i, walk up to the root collecting functions, then apply them top-down; do this per element inside index_of so you can stop early.