Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Google SWE coding round, one question the whole time. Number theory flavored but really just brute force optimization once you see it. Not the hardest thing I've done but the constraint range made me nervous.

Questions Asked (1)

Given an integer n, find all integers s less than n such that s can be expressed as the sum of two squares in exactly two distinct unordered ways, where (a, b) and (b, a) count as the same. For example, 50 qualifies because 1² + 7² = 50 and 5² + 5² = 50. The constraint is 1 <= n < 2³¹ - 1.

Algorithms & Data Structures

Author's notes

The example they give makes it look easy but then you realize n can be up to 2 billion and suddenly your O(n²) loop is a problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem and constraints, then propose an efficient algorithm using number theory: a number can be expressed as a sum of two squares in exactly two ways iff its prime factorization has exactly two primes ≡ 1 mod 4 (counting multiplicity) and no primes ≡ 3 mod 4 with odd exponent. Iterate through s up to n, factorize each s, and count representations using the formula r2(s)/8, but adjust for squares and zeros. Optimize by precomputing primes or using a sieve if n is large.

Pro tip: Mention that the number of representations as a sum of two squares is given by r2(s) = 4(d1(s) - d3(s)), where d1 and d3 are the counts of divisors ≡ 1 and 3 mod 4. This shows deep number theory knowledge and can simplify counting.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: find all s < n that have exactly two distinct unordered representations as a sum of two squares. Note the constraint n < 2^31 - 1, so O(n) or O(n log n) algorithms are acceptable, but O(n^2) is not.

2. Derive the number-theoretic condition

Use the sum of two squares theorem: s is representable iff every prime ≡ 3 mod 4 appears with even exponent. The number of representations is r2(s)/8 (for positive a,b) with adjustments for zeros and equal squares. Exactly two representations means r2(s) = 16 (if no zeros or equal squares) or other cases.

3. Design an efficient algorithm

For each s from 1 to n-1, factorize s and count representations using the formula. Alternatively, generate all sums of two squares up to n and count frequencies. Choose based on n's size; for n up to 2^31, a sieve or precomputed primes can speed up factorization.

4. Handle edge cases and optimize

Consider s=0? The problem says integers s less than n, but likely s>0. Handle cases where a=b (like 50=5^2+5^2) and where one square is zero (if allowed). Optimize by noting that s must be composite with specific prime factors.

5. Analyze complexity and test

State time and space complexity. For factorization approach, O(n sqrt(n)) is too slow; use precomputed primes up to sqrt(n) for O(n log log n) sieve. Test with small n and the given example (50).

Key Points to Mention

Sum of two squares theorem: prime factorization condition (primes ≡ 3 mod 4 must have even exponent).
Formula for number of representations: r2(s) = 4(d1(s) - d3(s)), where d1 and d3 count divisors ≡ 1 and 3 mod 4.
Exactly two unordered representations means r2(s) = 16 (if no zeros/equal squares) or other cases; need to adjust for a=b and a=0.
Efficient factorization using precomputed primes up to sqrt(n) or a sieve.
Alternative approach: generate all sums of two squares up to n and count frequencies using a hash map or array.
Time complexity: O(n log log n) with sieve, or O(n sqrt(n)) naive; space complexity O(n) for sieve or hash map.

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