Citadel: Update No-Intercept Regression Slopes Across Batches

Update No-Intercept Regression Slopes Across Batches

Company: Citadel

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Data arrives in `M` batches. Each `x_batches[b]` and `y_batches[b]` is a matrix with the same number `N` of columns and the same number of rows within batch `b`. Column `j` of `x` is paired with column `j` of `y`. For each cumulative prefix of batches, fit every paired no-intercept regression $$ y_j=\beta_j x_j $$ using all rows seen so far. Implement: ```text cumulative_slopes( x_batches: List[Matrix[float]], y_batches: List[Matrix[float]] ) -> List[List[float]] ``` Output `M` rows of `N` slopes, where output row `b` uses batches `0` through `b` and $$ \beta_j=\frac{\sum x_{ij}y_{ij}}{\sum x_{ij}^2}. $$ ### Constraints - `1 <= M <= 1_000` - `1 <= N <= 500` - The total number of input rows across batches is at most `200_000`. - Every matrix is rectangular and paired batch shapes match. - Every input value is finite and has absolute value at most `10^6`. - Each `x` value is either zero or has absolute value at least `10^-6`. - For every cumulative prefix and column, the denominator is positive. - Floating-point answers within `1e-9` absolute or relative error are accepted. ### Clarifications - Do not include an intercept or center the data. - A cumulative result uses all prior batches, not only the current batch. - Batch row counts may differ. - These bounds keep each product at most `10^12`, each cumulative numerator and denominator at most `2 * 10^17` in magnitude, and every positive denominator at least `10^-12`, preventing overflow or a non-finite slope in double precision. ```hint Keep sufficient statistics Each slope needs only a running sum of `x*y` and a running sum of `x*x` for its column. ``` ### Examples ```text Input: x_batches = [[[1], [2]], [[3]]] y_batches = [[[2], [4]], [[3]]] Output: [[2.0], [19.0 / 14.0]] ``` ### Evaluation Focus - Correct column pairing and cumulative updates. - Reuse of sufficient statistics rather than refitting over all history. - (O(RN)) total time for `R` input rows and (O(N)) working state beyond the output. - Stable floating-point accumulation and shape validation. ### Extension Which additional running statistics are needed to support an intercept?

Overview: Compute cumulative no-intercept regression slopes as paired data arrives in batches. Reuse running cross-products and sums of squares instead of refitting all historical rows.

Data arrives in M batches. Each x_batches[b] and y_batches[b] is a matrix with the same number N of columns and the same number of rows within batch b. Column j of x is paired with column j of y.

For each cumulative prefix of batches, fit every paired no-intercept regression

y_j=\beta_j x_j

using all rows seen so far. Implement:

cumulative_slopes(
    x_batches: List[Matrix[float]],
    y_batches: List[Matrix[float]]
) -> List[List[float]]

Output M rows of N slopes, where output row b uses batches 0 through b and

\beta_j=\frac{\sum x_{ij}y_{ij}}{\sum x_{ij}^2}.

Constraints

1 <= M <= 1_000
1 <= N <= 500
The total number of input rows across batches is at most 200_000 .
Every matrix is rectangular and paired batch shapes match.
Every input value is finite and has absolute value at most 10^6 .
Each x value is either zero or has absolute value at least 10^-6 .
For every cumulative prefix and column, the denominator is positive.
Floating-point answers within 1e-9 absolute or relative error are accepted.

Clarifications

Do not include an intercept or center the data.
A cumulative result uses all prior batches, not only the current batch.
Batch row counts may differ.
These bounds keep each product at most 10^12 , each cumulative numerator and denominator at most 2 * 10^17 in magnitude, and every positive denominator at least 10^-12 , preventing overflow or a non-finite slope in double precision.

Examples

Input:
x_batches = [[[1], [2]], [[3]]]
y_batches = [[[2], [4]], [[3]]]

Output:
[[2.0], [19.0 / 14.0]]

Evaluation Focus

Correct column pairing and cumulative updates.
Reuse of sufficient statistics rather than refitting over all history.
(O(RN)) total time for R input rows and (O(N)) working state beyond the output.
Stable floating-point accumulation and shape validation.

Extension

Which additional running statistics are needed to support an intercept?