Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google SWE interview with a digit-subset problem that looks deceptively simple until you actually try to code it up under pressure. One question, algorithmic, and I left feeling like I probably overcomplicated my approach.

Questions Asked (1)

You're given a list of two-digit numbers. Find the largest subset where every number in the subset contains at least one digit in common. Return the size of that subset.

Algorithms & Data Structures

Author's notes

My first instinct was some kind of graph problem and I wasted probably three minutes going down that path before backing up.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each number is a node and edges connect numbers sharing a digit. The largest subset where every number shares a digit with every other is a clique, but the problem actually asks for a subset where all numbers share at least one common digit (since 'every number contains at least one digit in common' implies a single digit common to all). So the answer is the maximum frequency of any digit across all numbers. Alternatively, if the interpretation is pairwise, it's a clique problem, but the common interpretation is the simpler one.

Pro tip: Clarify the interpretation with the interviewer: does 'every number contains at least one digit in common' mean all numbers share a single common digit, or that every pair shares at least one digit? The former is trivial (max digit frequency), the latter is NP-hard (max clique). Google interviewers often expect you to recognize this distinction and discuss the complexity.

1. Clarify the problem statement

Ask the interviewer to confirm whether the subset requires a single digit common to all numbers, or pairwise common digits. This determines the approach and complexity.

2. Consider the simple interpretation

If a single common digit is required, iterate through all numbers, count the frequency of each digit (0-9), and return the maximum count. This is O(n) time and O(1) space.

3. Consider the pairwise interpretation

If every pair must share a digit, build a graph with numbers as nodes and edges between numbers sharing a digit. The problem reduces to finding the maximum clique, which is NP-hard. Discuss possible approaches like backtracking or approximation.

4. Discuss trade-offs and edge cases

Mention that the simple interpretation is likely intended for an interview due to its efficiency. Handle edge cases like empty list, numbers with repeated digits, and digits 0-9.

5. Write and test the solution

Implement the chosen approach, walk through examples, and verify with test cases. If time permits, discuss optimizations or alternative data structures.

Key Points to Mention

Graph representation: nodes as numbers, edges if they share a digit.
Maximum clique problem and its NP-hardness for the pairwise interpretation.
Digit frequency counting for the single common digit interpretation.
Time and space complexity analysis: O(n) vs exponential.
Edge cases: empty input, numbers with same digits, leading zeros.
Communication with interviewer to clarify ambiguous requirements.

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