Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Google SWE coding round, one question about digit-sharing in a list of 2-digit numbers. Pretty algorithmic, not super hard on the surface but easy to overthink.

Questions Asked (1)

Given a list of 2-digit numbers, return the maximum count of elements that share at least one digit in common with each other. For example, [55, 15, 20] returns 2 because 55 and 15 both contain 5.

Algorithms & Data Structures

Author's notes

My first instinct was to overcomplicate it with some graph-based grouping approach.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose an efficient algorithm. A good approach is to model the problem as a graph where each number is a node, and edges connect numbers sharing a digit; the answer is the size of the largest connected component. Alternatively, use union-find or BFS/DFS to find the largest group of numbers that are connected through shared digits.

Pro tip: Discuss trade-offs between different approaches (e.g., graph traversal vs. union-find) and mention time/space complexity. Also, consider if the list can be large and if there are memory constraints, as this shows you think about scalability.

1. Clarify the problem

Ask clarifying questions: Are the numbers always 2-digit? Can there be duplicates? What should be returned if no two numbers share a digit? Confirm that the count is for a subset where every pair shares at least one digit (i.e., a clique) or if it's a connected component (where numbers may not all share the same digit but are linked through others). The example suggests connected component, but it's ambiguous.

2. Identify the core challenge

Recognize that this is a graph connectivity problem: each number is a node, and an edge exists if two numbers share a digit. The goal is to find the largest connected component. Alternatively, if the problem requires a clique (all numbers share a common digit), then it's about finding the most frequent digit among all numbers.

3. Choose an algorithm

For connected components, use union-find (disjoint set) or BFS/DFS. For efficiency, note that each number has only two digits, so you can group numbers by their digits and then union groups that share a digit. If it's a clique, simply count the frequency of each digit and return the maximum count.

4. Implement and test

Write code for the chosen approach, handling edge cases like empty list, single element, and numbers with repeated digits (e.g., 55). Test with the given example and additional cases to ensure correctness.

5. Analyze complexity

State the time and space complexity. For union-find with path compression, it's nearly O(n α(n)) time and O(n) space. If using digit frequency, it's O(n) time and O(1) space (since only 10 digits).

Key Points to Mention

Graph modeling: nodes as numbers, edges for shared digits.
Union-Find (Disjoint Set Union) for efficient connected component detection.
Alternative: digit frequency counting if the problem requires a common digit among all elements.
Edge cases: empty list, single number, duplicates, numbers like 55 (both digits same).
Time and space complexity analysis.
Clarify ambiguity: connected component vs. clique.

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