Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google coding round, one problem the whole time. The question looked deceptively simple but the transitive grouping part is where things get interesting and where I almost went down the wrong path.

Questions Asked (1)

Given a list of two-digit integers, group numbers together if they share any digit. Grouping is transitive, so if A shares a digit with B and B shares a digit with C, all three are in the same group. Return the size of the largest group.

Algorithms & Data Structures

Author's notes

My first instinct was to do pairwise comparisons between all numbers and BFS from there.

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, then find the largest connected component using Union-Find (DSU) or BFS/DFS. Since numbers are two-digit, you can optimize by grouping via digit buckets (0-9) and unioning numbers that share a digit.

Pro tip: Mention that with only 10 possible digits, you can use a Union-Find structure with 10 digit nodes and union each number's two digits, then count the size of each digit group. This reduces the problem to O(n α(10)) time and avoids building a full graph.

1. Clarify and Restate

Confirm the input format (list of two-digit integers) and that grouping is transitive. Restate the goal: return the size of the largest group of numbers connected by shared digits.

2. Choose Data Structure

Decide between Union-Find (DSU) or graph traversal (BFS/DFS). Union-Find is efficient for dynamic connectivity and easy to implement with path compression and union by rank.

3. Build Connections

For each number, extract its two digits and union them. Alternatively, create a mapping from each digit to a list of numbers and union numbers that share a digit.

4. Compute Group Sizes

After processing all numbers, count the size of each group by finding the root of each number's digits and tallying. Track the maximum size.

5. Analyze Complexity

State time complexity: O(n α(10)) ≈ O(n) with Union-Find, and space O(10) for digit nodes plus O(n) for mapping numbers to digits if needed.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for near-constant time operations.
Graph representation: nodes as numbers or digits, edges between numbers sharing a digit.
Transitivity handled naturally by Union-Find or connected components.
Optimization: only 10 possible digits, so use digit nodes to reduce graph size.
Edge cases: empty list, single number, numbers with same digits (e.g., 11, 22), numbers sharing no digits.
Time and space complexity analysis: O(n α(10)) time, O(10 + n) space.

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