Implement Univariate Linear Regression with Ordinary Least Squares
Company: Two Sigma
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Implement **univariate (simple) linear regression** fitted in batch with the **ordinary least squares (OLS)** closed-form solution. You must implement the formula yourself — do not use any machine-learning or statistics library fitting routine.
You are given `n` observations `(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)`. Find the slope `b` and intercept `a` of the line
$$\hat{y} = a + b x$$
that minimize the sum of squared residuals
$$\sum_{i=1}^{n} \left( y_i - (a + b x_i) \right)^2 .$$
The OLS closed-form solution is:
$$b = \frac{\sum_{i=1}^{n} (x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=1}^{n} (x_i - \bar{x})^2}, \qquad a = \bar{y} - b\,\bar{x}$$
where $\bar{x}$ and $\bar{y}$ are the means of the `x` and `y` values.
**Input**
- `x`: a list of `n` real numbers (the feature values).
- `y`: a list of `n` real numbers (the target values), where `y[i]` corresponds to `x[i]`.
**Output**
- A list of two numbers `[b, a]`: the fitted slope and intercept, in that order. Answers within an absolute or relative error of `1e-6` of the correct values are accepted.
**Constraints**
- `2 <= n <= 100000`
- `-10^6 <= x[i], y[i] <= 10^6`
- The `x` values are guaranteed to contain at least two distinct values (the denominator is never zero).
- Your solution should run in `O(n)` time using a constant number of passes over the data.
**Example 1**
```
x = [1, 2, 3]
y = [2, 4, 6]
```
Output: `[2.0, 0.0]`
The points lie exactly on the line `y = 2x`, so the slope is `2.0` and the intercept is `0.0`.
**Example 2**
```
x = [0, 1, 2, 3]
y = [1, 3, 2, 5]
```
Output: `[1.1, 1.1]`
Here $\bar{x} = 1.5$, $\bar{y} = 2.75$, $\sum (x_i - \bar{x})(y_i - \bar{y}) = 5.5$, and $\sum (x_i - \bar{x})^2 = 5.0$, giving slope `b = 1.1` and intercept `a = 2.75 - 1.1 * 1.5 = 1.1`.
**Example 3**
```
x = [5, 5, 10]
y = [1, 3, 2]
```
Output: `[0.0, 2.0]`
The best-fit line is horizontal: the covariance term is `0`, so `b = 0.0` and `a` equals the mean of `y`, which is `2.0`.
Quick Answer: This question evaluates understanding of univariate linear regression and the ordinary least squares (OLS) closed-form estimator, probing competencies in basic statistical estimation, interpretation of slope and intercept, numerical stability, and floating-point arithmetic.
Implement univariate (simple) linear regression fitted in batch with the ordinary least squares (OLS) closed-form solution. You must implement the formula yourself — do not use any machine-learning or statistics library fitting routine.
You are given `n` observations `(x_1, y_1), ..., (x_n, y_n)`. Find the slope `b` and intercept `a` of the line `y_hat = a + b*x` that minimize the sum of squared residuals `sum_i (y_i - (a + b*x_i))^2`.
The OLS closed-form solution is:
b = sum_i (x_i - x_mean)(y_i - y_mean) / sum_i (x_i - x_mean)^2
a = y_mean - b * x_mean
where `x_mean` and `y_mean` are the means of the `x` and `y` values.
Input:
- `x`: a list of `n` real numbers (feature values).
- `y`: a list of `n` real numbers (target values), where `y[i]` corresponds to `x[i]`.
Output:
- A list of two numbers `[b, a]`: the fitted slope and intercept, in that order. Answers within an absolute or relative error of `1e-6` of the correct values are accepted.
Constraints
- 2 <= n <= 100000
- -10^6 <= x[i], y[i] <= 10^6
- The x values contain at least two distinct values (denominator is never zero).
- Must run in O(n) time with a constant number of passes over the data.
- Answers within absolute or relative error 1e-6 are accepted.
Examples
Input: ([1, 2, 3], [2, 4, 6])
Expected Output: [2.0, 0.0]
Explanation: Points lie exactly on y = 2x, so slope = 2.0 and intercept = 0.0.
Input: ([0, 1, 2, 3], [1, 3, 2, 5])
Expected Output: [1.1, 1.1]
Explanation: x_mean=1.5, y_mean=2.75, covariance sum=5.5, variance sum=5.0, so b=1.1 and a=2.75-1.1*1.5=1.1.
Hints
- First compute the means x_mean = mean(x) and y_mean = mean(y) in one pass each.
- Accumulate the covariance numerator sum((x_i - x_mean)*(y_i - y_mean)) and the variance denominator sum((x_i - x_mean)^2) in a single loop.
- The slope is numerator / denominator; then the intercept is y_mean - slope * x_mean. Return [slope, intercept].