Find largest subset sharing a common digit
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Take-home Project
You are given a list `A` of **two-digit integers** (each from 10 to 99). Two integers are said to “share a digit” if they have at least one digit in common (e.g., `23` and `35` share digit `3`).
Determine the **maximum size of a subset** of `A` such that **all numbers in the subset share at least one common digit** (i.e., there exists a digit `d` in `{0,1,...,9}` that appears in every number in the chosen subset).
**Input:** Array/list `A` of length `m`, with each `A[i]` in `[10, 99]`.
**Output:** An integer = the maximum possible subset size.
**Example:**
- `A = [23, 35, 30, 19]`
- The digit `3` appears in `23, 35, 30` → answer is `3`.
Quick Answer: This question evaluates the ability to analyze arrays for the largest subset sharing a common digit, emphasizing digit-level feature extraction, frequency analysis, and set-based reasoning. Commonly asked in the Coding & Algorithms domain, it assesses practical algorithmic implementation and efficient aggregation/counting with basic data structures rather than purely conceptual reasoning.
Given two-digit integers, return the largest number of elements that all contain one common digit.
Constraints
- Numbers are two-digit integers in normal inputs
Examples
Input: ([11, 21, 31, 41, 16, 17, 18, 34, 57],)
Expected Output: 7
Input: ([23, 35, 30, 19],)
Expected Output: 3
Input: ([10, 22, 33],)
Expected Output: 1
Input: ([],)
Expected Output: 0
Hints
- Count how many numbers contain each digit, counting a number once per digit even if repeated.