Meta·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jul 2026

Summary

Meta SWE interview with a tricky algorithmic problem that pushed me to think beyond linear time. The question felt deceptively simple at first glance but the sub-O(n) constraint is what made it actually hard.

Questions Asked (1)

You're given a sorted array with lots of duplicates but very few distinct values. Count the number of unique values using fewer than O(n) operations. How would you approach this, and what's the complexity?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the naive scan and immediately caught myself because they literally said sub-linear.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search to find the first occurrence of each new distinct value, leveraging the sorted order to skip duplicates. Start from the beginning, find the next distinct value by searching for the first element greater than the current value, and repeat until the end. The number of binary searches equals the number of distinct values, so the complexity is O(k log n) where k is the number of distinct values, which is much less than O(n) when k is small.

Pro tip: Clarify that 'fewer than O(n) operations' means sublinear in n, and that the solution's complexity depends on k, the number of distinct values. If k is small, O(k log n) is excellent; if k could be large, mention that O(n) might be optimal, but the problem guarantees few distinct values.

1. Understand the problem and constraints

Restate the problem: sorted array with many duplicates, few distinct values. The goal is to count unique values in fewer than O(n) operations. Clarify that 'fewer than O(n)' means sublinear in the array length n.

2. Choose binary search as the core technique

Since the array is sorted, binary search can efficiently find boundaries. To count distinct values, we can find the first occurrence of each distinct value by searching for the next value greater than the current one.

3. Design the algorithm

Initialize count = 0 and index = 0. While index < n: increment count, set current = arr[index], then binary search for the first index where arr[index] > current. Set index to that position. Repeat until index reaches n.

4. Analyze complexity

Each binary search takes O(log n) time, and we perform one per distinct value, so total time is O(k log n), where k is the number of distinct values. Since k is small, this is much less than O(n). Space complexity is O(1).

5. Discuss edge cases and alternatives

Consider edge cases: empty array, all elements same, all elements distinct. Mention that if k is not small, O(n) might be optimal, but the problem guarantees few distinct values. Also note that a linear scan would be O(n), which is not acceptable.

Key Points to Mention

Binary search to find the first occurrence of the next distinct value.
Time complexity O(k log n) where k is the number of distinct values, which is sublinear when k is small.
Space complexity O(1) as we only use a few variables.
The algorithm leverages the sorted property to skip duplicates efficiently.
Edge cases: empty array, single distinct value, all distinct values.
Comparison with linear scan O(n) and why it's not optimal for this problem.

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