Google·Data Scientist·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google data science interview with a coding question around matrix generation and normalization. Pretty focused on whether you actually know NumPy or if you'd just write a slow nested loop and call it a day.

Questions Asked (1)

Write code to generate a 100x100 matrix of Binomial(1, 0.5) samples, then normalize each column so its values sum to 1. What's an efficient way to do this in O(n²) time?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was a nested loop and I almost went with it before catching myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying that generating 10,000 Bernoulli samples is inherently O(n²) since each of the n² entries must be generated. Then focus on the normalization step: compute column sums in O(n²) by iterating over all elements, and divide each element by its column sum in another O(n²) pass. Emphasize that this two-pass approach is optimal because you must touch every element at least once.

Pro tip: Mention that you can combine the two passes into one by first computing column sums, then normalizing in-place, but be prepared to discuss the trade-off between memory and cache efficiency. Also, note that using vectorized operations (e.g., NumPy) is practically faster but still O(n²) in complexity.

1. Clarify the problem and constraints

Confirm that the matrix is 100x100, each entry is a Bernoulli(0.5) sample (0 or 1), and normalization means each column sums to 1. Discuss that since entries are 0/1, column sums are counts of ones, and normalization divides each entry by the column sum.

2. Outline the naive approach

Describe generating the matrix with nested loops (O(n²)) and then normalizing by computing column sums and dividing each element. This is straightforward but may involve multiple passes.

3. Optimize to O(n²) time

Explain that the optimal approach is to compute column sums in one pass over the matrix (O(n²)), then divide each element by its column sum in a second pass (O(n²)). This is O(n²) overall and optimal because every element must be read and written.

4. Discuss implementation details and trade-offs

Mention in-place normalization to save memory, handling columns with sum zero (though unlikely with p=0.5 and n=100), and using vectorized operations for practical speed. Note that the algorithm is O(n²) regardless of vectorization.

5. Provide code or pseudocode

Write clear pseudocode or actual code (e.g., in Python with NumPy) demonstrating the two-pass approach, ensuring it runs in O(n²) time and O(n²) space (or O(n) extra space for column sums).

Key Points to Mention

Time complexity: O(n²) is optimal because you must generate and process n² elements.
Space complexity: O(n²) for the matrix, O(n) extra for column sums if not in-place.
Two-pass approach: first compute column sums, then normalize.
Edge cases: columns with sum zero (probability ~ (0.5)^100, negligible but worth mentioning).
Vectorization: using NumPy or similar can speed up constant factors but doesn't change asymptotic complexity.
In-place normalization: possible to avoid extra matrix allocation, but may affect cache performance.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.