Katkat
Back

Find largest group of two-digit numbers sharing digits

GoogleSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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 (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.