Find largest group of two-digit numbers sharing digits
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
You are given an integer array `A` of length `n` (`1 <= n <= 100`). Each element is a two-digit number (e.g., from 10 to 99). Two numbers are considered **connected** if they share **at least one digit** in common.
Examples of “share a digit”:
- `55` and `58` share digit `5`
- `25` and `45` share digit `5`
- `12` and `23` share digit `2`
- `55` and `66` share no digit
A **group** is any set of numbers that can be connected through this relation transitively (i.e., if `a` shares a digit with `b`, and `b` shares a digit with `c`, then `a`, `b`, `c` can be in the same group even if `a` and `c` don’t share a digit directly).
Task: Return the **maximum possible size** of a group (i.e., the size of the largest connected component under the “shares a digit” relation).
Output: an integer, the largest group size.
Clarifications:
- If `A` contains duplicate values, treat them as separate elements (they each contribute 1 to the group size).
- Sharing can be via either the tens digit or the ones digit.
Quick Answer: This question evaluates a candidate's ability to model pairwise relationships and compute connected components in small graphs, testing skills in graph connectivity and grouping based on shared attributes in arrays of two-digit numbers.
You are given an integer array `A` of length `n` (`1 <= n <= 100`). Each element is a two-digit number (10 to 99). Two numbers are **connected** if they share **at least one digit** in common (the shared digit may be the tens digit or the ones digit of either number).
Examples of "share a digit":
- `55` and `58` share digit `5`
- `25` and `45` share digit `5`
- `12` and `23` share digit `2`
- `55` and `66` share no digit
A **group** is any set of numbers connected through this relation **transitively**: if `a` shares a digit with `b`, and `b` shares a digit with `c`, then `a`, `b`, `c` belong to the same group even if `a` and `c` do not share a digit directly.
Return the **maximum possible group size** — i.e., the size of the largest connected component under the "shares a digit" relation.
Notes:
- Duplicate values are treated as separate elements; each contributes 1 to its group's size.
- Output is a single integer.
Constraints
- 1 <= n <= 100
- Each A[i] is a two-digit number (10 <= A[i] <= 99)
- Duplicate values are allowed and counted as separate elements
- Connection is transitive (group = connected component)
Examples
Input: ([55, 58, 25, 45],)
Expected Output: 4
Explanation: 55-58 share 5, 25-45 share 5, and 55-25/55-45 share 5, so all four numbers are in one component of size 4.
Input: ([55, 66, 77],)
Expected Output: 1
Explanation: 55, 66, 77 share no digit with each other, so every number is its own component; the largest size is 1.
Hints
- Model each number as a node; add an edge between any two numbers that share a digit. The answer is the size of the largest connected component.
- A two-digit number has only its tens and ones digit, so 'shares a digit' is just a non-empty intersection of two 2-element digit sets — an O(1) check.
- Union-Find (Disjoint Set Union) makes the component sizes easy: union every connected pair, then count how many indices map to each root and take the max. A BFS/DFS over an adjacency list works too.
- Watch the duplicate clarification: identical values still count as distinct elements, so they each add 1 to the component — union by index, not by value.