Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Google SWE interview with a deceptively simple-looking array problem that made me second-guess myself more than it should have.

Questions Asked (1)

Given an array of two-digit integers, find the largest subset where every number shares at least one common digit (0-9). Return the size of that subset.

Algorithms & Data Structures

Author's notes

My first instinct was to overcomplicate it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

For each digit 0-9, count how many numbers contain that digit, then return the maximum count. This works because any valid subset must share at least one common digit, so the largest subset is simply the set of all numbers containing the most frequent digit.

Pro tip: Clarify that numbers are two-digit (10-99) and that a number like 11 has the same digit twice but still counts once for digit 1. Also mention that if the array is empty, return 0.

1. Clarify constraints and edge cases

Confirm that numbers are two-digit integers (10-99), and ask about empty arrays, duplicates, and whether a number like 11 should be treated as containing digit 1 once or twice.

2. Identify the key insight

Realize that any subset sharing a common digit must be a subset of all numbers containing that digit. Therefore, the largest such subset is exactly the set of all numbers containing the most frequent digit.

3. Design the algorithm

Initialize an array of size 10 to zero. For each number, extract its tens and ones digits, and increment the count for each unique digit in that number. Finally, return the maximum count.

4. Analyze complexity and optimize

The algorithm runs in O(n) time and O(1) space, which is optimal. Discuss potential micro-optimizations like early termination if a digit reaches n.

5. Test with examples

Walk through a small example, such as [12, 23, 34, 45], to verify the counts and ensure the logic handles cases where numbers share multiple digits.

Key Points to Mention

The problem reduces to finding the most frequent digit across all numbers.
Each number can contribute to at most two digit counts (tens and ones), but if both digits are the same, it should only count once for that digit.
Time complexity is O(n) and space complexity is O(1) using a fixed-size array of 10 counters.
Edge cases: empty array returns 0; numbers with repeated digits (e.g., 11) are handled correctly.
The approach is optimal because any valid subset must be contained within the set of numbers sharing a particular digit.
Consider using a boolean array or set per number to avoid double-counting the same digit.

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