← Google Interview Insights

Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Google SWE coding round, one question the whole time. Pretty graph-flavored problem dressed up as a number puzzle. Felt okay about my solution but I kept second-guessing the union-find approach when a simple BFS would've done fine.

Questions Asked (1)

Q1

Given an integer array where each element is a two-digit number, define two numbers as connected if they share at least one digit (tens or ones). Connectivity is transitive. Find the size of the largest connected component in the array.

Algorithms & Data Structures
Author's notes

I went straight for union-find and it worked, but I wasted probably five minutes convincing myself it was the right tool when BFS over adjacency would've been cleaner to explain out loud.

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. Use Union-Find (Disjoint Set Union) to efficiently merge connected components, then find the largest component size. Alternatively, build a graph of digits (0-9) and numbers, then use BFS/DFS to find connected components.

Pro tip: Clarify edge cases upfront: empty array, single element, numbers with repeated digits (e.g., 11), and numbers sharing both digits. Also discuss time/space complexity trade-offs between Union-Find and graph traversal approaches.

1. Understand the problem and clarify constraints

Confirm that connectivity is transitive and that each number is a two-digit integer (10-99). Ask about input size, possible duplicates, and whether digits can be zero (e.g., 10, 20).

2. Choose an approach: Union-Find or graph traversal

Union-Find is efficient for dynamic connectivity; graph traversal (BFS/DFS) is intuitive. Consider building a bipartite graph between numbers and digits to reduce edges.

3. Implement the chosen algorithm

For Union-Find: initialize parent array, union numbers sharing digits, then count component sizes. For BFS/DFS: build adjacency list (or digit-to-number mapping) and traverse.

4. Handle edge cases and optimize

Account for empty input, single element, and numbers with identical digits. Optimize by using digit buckets (0-9) to avoid O(n^2) comparisons.

5. Analyze complexity and test

State time and space complexity (e.g., O(n α(n)) for Union-Find, O(n) for BFS with digit buckets). Walk through a small example to verify correctness.

Key Points to Mention

  • Union-Find (Disjoint Set Union) with path compression and union by rank for near-constant time operations.
  • Graph representation: either direct edges between numbers or bipartite graph with digit nodes (0-9).
  • Time complexity: O(n α(n)) for Union-Find, O(n) for BFS/DFS with digit buckets; space complexity O(n).
  • Edge cases: empty array, single element, numbers with repeated digits (e.g., 11), numbers sharing both digits.
  • Optimization: using digit buckets to avoid O(n^2) pairwise comparisons.
  • Alternative approach: BFS/DFS on a graph where nodes are numbers and edges connect those sharing a digit.

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