Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Google SWE coding round with a grouping problem that looks deceptively simple until you start thinking about transitive relationships between numbers.

Questions Asked (1)

Given an array of two-digit numbers (up to 100 elements), find the maximum size of a group where every number in the group shares at least one digit with at least one other number in the group.

Algorithms & Data Structures

Author's notes

My first instinct was to just check pairwise digit overlap and greedily build groups, which completely fell apart once I thought about transitivity.

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 at least one digit. The task reduces to finding the largest connected component in this graph. Use union-find or BFS/DFS to compute component sizes efficiently.

Pro tip: Clarify that the group must be connected (each number shares a digit with at least one other in the group), not just that every number shares a digit with some common number. This distinction is crucial and often missed.

1. Clarify the problem

Confirm that the group must be connected: every number shares at least one digit with at least one other number in the group. This means the group forms a connected component in the digit-sharing graph.

2. Model as a graph

Create nodes for each number. Add an edge between two numbers if they share at least one digit (0-9). The problem then asks for the size of the largest connected component.

3. Choose an algorithm

Use Union-Find (Disjoint Set Union) or BFS/DFS to find connected components. Union-Find is efficient for up to 100 elements and easy to implement.

4. Optimize edge creation

Instead of checking all pairs (O(n^2)), group numbers by each digit they contain. For each digit, union all numbers that have that digit. This reduces time complexity.

5. Compute and return the maximum size

After processing all digits, find the size of each connected component and return the maximum. Handle edge cases like empty array or single element.

Key Points to Mention

Graph representation: nodes as numbers, edges for shared digits.
Connected components: the group must be connected, not just share a common digit.
Union-Find (Disjoint Set Union) for efficient component tracking.
Optimization: group by digits to avoid O(n^2) pairwise comparisons.
Time complexity: O(n * d) where d is number of digits per number (at most 2), effectively O(n).
Edge cases: empty array, single element, numbers with no shared digits.

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