Two Sigma Data Scientist Interview Experience — Piecewise Interpolation, Temperature Prediction, and Streaming Linear Regression on the OA

This Two Sigma research OA is also an old question that's been floating around on the forum.

Question 1: You're given a bunch of discrete points that connect into a polyline. Now you're given an x, and you need to compute the corresponding y. If x falls between two points, do linear interpolation; if it falls outside the range, extend the line segments on either end to compute it. The question mainly tests how to handle this efficiently — generally you'd sort first, then use binary search to find which two points x falls between.

Question 2: You're given historical temperature data for NYC and a bunch of small towns, and you need to analyze things like which town has the biggest fluctuations, which one is most similar to NYC, and so on. After that, you use the towns' data to predict NYC's temperature, using MSE to evaluate performance. There's also a bit of a feature selection flavor to it — each time you pick the one town that reduces the error the most and add it in, continuing until you've selected a specified number.

Question 3: Write linear regression without an intercept by hand. The first part is the ordinary case — compute the slope directly from the whole batch of data. The second part is streaming data: data keeps coming in, and you can't recompute everything from scratch each time — instead you need to maintain some running/cumulative quantities so you can update the result online.