Meta·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Meta SWE interview with a pretty math-heavy combinatorics problem disguised as an array question. No fluff, just one deep problem that required a proof and a constructive example.

Questions Asked (1)

Given an integer array of length n (n >= 1) with arbitrary integer values, what is the maximum number of distinct frequency counts that can appear among the array's distinct values? Derive a tight closed-form expression in terms of n, prove it's optimal, and give a concrete example that hits the bound.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This wrecked me for the first few minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as partitioning the n elements into groups of equal frequency, where each group corresponds to a distinct frequency value. To maximize the number of distinct frequencies, use the smallest possible frequencies 1, 2, 3, ... and find the largest k such that the sum 1+2+...+k ≤ n. Then derive the closed-form k = floor((sqrt(8n+1)-1)/2) and prove optimality by showing any additional frequency would require more than n elements.

Pro tip: Emphasize that the bound is tight and constructive: the example with frequencies 1, 2, ..., k and one leftover group (if any) achieves it. This shows you understand both the upper bound and its attainability, which interviewers value.

1. Understand the problem

Clarify that we need the maximum number of distinct frequency counts among the distinct values in the array. Each distinct value has a frequency (a positive integer), and the sum of all frequencies equals n.

2. Formulate as an optimization

To maximize the number of distinct frequencies, we should use the smallest possible distinct positive integers: 1, 2, 3, ..., k. The sum of these must be ≤ n, so we need the largest k with k(k+1)/2 ≤ n.

3. Derive closed-form expression

Solve the quadratic inequality k^2 + k - 2n ≤ 0 to get k = floor((sqrt(8n+1)-1)/2). This is the maximum number of distinct frequencies.

4. Prove optimality

Show that any set of k+1 distinct positive frequencies has sum at least 1+2+...+(k+1) = (k+1)(k+2)/2 > n, which is impossible. Thus k is an upper bound, and it is achievable by construction.

5. Provide a concrete example

For a given n, construct an array with frequencies 1, 2, ..., k and one additional group with frequency n - k(k+1)/2 (if >0). For instance, n=10 gives k=4 (since 1+2+3+4=10), so an array with frequencies 1,2,3,4 works.

Key Points to Mention

The sum of frequencies equals n, so the problem reduces to partitioning n into distinct positive integers.
To maximize the count, use the smallest distinct integers: 1, 2, 3, ..., k.
The closed-form solution is k = floor((sqrt(8n+1)-1)/2), derived from the triangular number inequality.
Optimality proof: any k+1 distinct frequencies sum to at least (k+1)(k+2)/2 > n, which is impossible.
Constructive example: frequencies 1,2,...,k and possibly one extra group with the remaining count.
Edge cases: n=1 gives k=1; n=2 gives k=1 (since 1+2=3>2); n=3 gives k=2 (1+2=3).

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