~/problems / Simulation & OOP design / Object-oriented design and extensible simulations

OA: Lazy array with deferred maps

medium 2 levels ~45 min Databricks

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 new LazyArray that behaves like this one with fn applied to every element (after all the maps already in the chain). map must not call fn and 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 equals target, or -1 if there is none.

Laziness rules for index_of, which the tests check by counting calls:

  • Apply the chain's functions in order (the first map first), one element at a time from index 0 upward.
  • 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.

Level 2 unlocks when level 1 passes.

Topic: Object-oriented design and extensible simulations. Classes that survive new requirements: games, payments, subscriptions, refactors.

0:00
Ctrl ' run · Ctrl ↵ submit
esc