Quick Overview

This question evaluates proficiency in matrix manipulation, handling of binomial random samples, column normalization, and algorithmic efficiency for processing large numerical arrays.

Normalize Columns in Binomial Matrix Efficiently

Company: Google

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Scenario Write code that creates a 100×100 matrix of Binomial(1, 0. 5) samples and normalizes each column so it sums to 1. ##### Question Provide an efficient algorithm (language of your choice) to perform the above task in O(n²) time. ##### Hints Vectorized NumPy operations beat nested loops.

Overview: This question evaluates proficiency in matrix manipulation, handling of binomial random samples, column normalization, and algorithmic efficiency for processing large numerical arrays.

Given an n x m binary matrix (entries are 0 or 1), return a new matrix of floats where each column is normalized to sum to 1. For each column j with sum s > 0, set output[i][j] = matrix[i][j] / s for all rows i. If a column sum is 0, leave that column as all zeros. Preserve the original shape and row/column order.

Constraints

  • 1 <= n, m <= 1000
  • matrix is rectangular with all rows of equal length
  • Each entry matrix[i][j] is 0 or 1
  • Return a new matrix of floats
  • Time complexity should be O(n*m) (O(n^2) for square matrices)
  • If a column sum is 0, the entire column remains zeros

Hints

  1. Compute all column sums in a single pass over the matrix.
  2. Then divide entries by their column sum to fill the output.
  3. If a column sum is zero, skip dividing that column to avoid division by zero.
  4. Avoid recomputing column sums per row or per element.

Loading coding console...

Show the approach

Approach

The algorithm performs two passes: first accumulate sums for each column, then divide each nonzero entry by its column sum to produce normalized values. Columns with sum zero are left as zeros to avoid division by zero. This avoids repeated summation and ensures linear work in the number of elements.

Time complexity:
O(n*m) (O(n^2) for n x n matrices)
Space complexity:
O(n*m) for the output matrix (O(1) extra if normalizing in place)