Coding & Algorithms · Interview Question
Given prefix sums, answer 'sum of subarray [i,j]' in O(1) per query. Preprocessing cost?
How to answer
Precompute prefix[k] = sum of first k elements in O(n) time/space. Then sum(i..j) = prefix[j+1] - prefix[i], one O(1) subtraction per query. This turns Q range queries from O(Q·n) into O(n + Q) — the core of cumulative-sum tricks used in PnL and rolling-window calcs.
Key idea: Off-by-one indexing (prefix[j] - prefix[i] instead of prefix[j+1] - prefix[i]), dropping or double-counting an endpoint.
More: Quant interview prep · Quant salary
Related Coding & Algorithms questions
- A fair six-sided die pays you its face value in dollars. What is the risk-neutral fair price to play this game once, and why?
- Draw a uniformly random element from a stream of unknown length in O(1) memory. How does reservoir sampling work?
- Expected and worst-case time complexity of quicksort, and why does the expected case dominate in practice?
- Find for each array element whether its complement (target - x) exists. Naive is O(n²). Get it to O(n)?