Upstart·Data Scientist·Technical Phone Screen
- Given a 65-element vector of yearly discretionary income, formulate a spending plan that is nondecreasing over time, never borrows from future income, and minimizes the squared deviation from the income profile. Show that this reduces to isotonic L2 regression under a nondecreasing constraint, and explain why the no-borrowing condition is automatically satisfied when probability mass is only shifted forward.
- Implement an O(n) Pool-Adjacent-Violators Algorithm in Python or R that returns both the smoothed spending vector and the block structure of the solution.
- Using a fixed random seed and a normally distributed income vector (mean 1000, sd 100, clipped at 0), run your algorithm and report the total squared error, verify the output is nondecreasing, and confirm that cumulative spending never exceeds cumulative income at any time step.
- Compare your PAVA implementation against a naive iterative averaging approach (repeatedly smooth out decreasing runs) in terms of both correctness and runtime.
“This is where I spent most of my mental energy.”