Quick Overview

This question evaluates a candidate's ability to reason about digit-based frequency analysis and efficient counting on arrays, testing competencies in combinatorics and algorithmic optimization for grouping elements by shared features.

Find largest digit-sharing subset

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Take-home Project

You are given an array of N integers. Each integer has exactly two decimal digits (i.e., each element is between 10 and 99 inclusive). You want to choose some of the array elements to form a **group**. A group is **valid** if there exists at least one digit (0–9) that appears in **every** number in the group. - For example, numbers 52, 25, and 55 can form a valid group because they all contain digit 5. - Numbers 11, 52, and 34 cannot form a valid group, because there is no single digit that appears in all three numbers. Your task: - Determine the **maximum possible size** of a valid group that can be chosen from the array. - If no two numbers share a digit, the answer can be 1 (any single element is trivially a valid group, since the shared digit condition holds vacuously for one element). **Input:** - An integer N (number of elements in the array). - N integers, each between 10 and 99 inclusive. **Output:** - A single integer: the maximum size of a valid group. You should design an efficient algorithm that works for large N.

Quick Answer: This question evaluates a candidate's ability to reason about digit-based frequency analysis and efficient counting on arrays, testing competencies in combinatorics and algorithmic optimization for grouping elements by shared features.

You are given an array of N two-digit integers (each between 10 and 99 inclusive). Choose some elements to form a group. A group is valid if there exists at least one decimal digit (0-9) that appears in EVERY number in the group. For example, 52, 25, and 55 form a valid group (all contain digit 5), while 11, 52, and 34 cannot (no single digit appears in all three). Return the maximum possible size of a valid group. A single element is always trivially a valid group, so for a non-empty array the answer is at least 1. Hint: A group is valid if and only if every member shares one common digit d. So the answer is simply the maximum, over all digits d in 0-9, of the count of numbers that contain d. Tally, for each digit, how many array elements contain it, then take the largest tally (clamped to at least 1 for a non-empty array).

Constraints

  • 1 <= N (the array may also be empty, for which the answer is 0)
  • Each element is an integer between 10 and 99 inclusive (exactly two decimal digits)
  • Duplicate values are allowed and counted independently
  • The algorithm must be efficient for large N (linear time)

Examples

Input: ([52, 25, 55],)

Expected Output: 3

Explanation: All three numbers contain the digit 5, so the entire array forms one valid group of size 3.

Input: ([11, 52, 34],)

Expected Output: 1

Explanation: No single digit appears in more than one of these numbers, so the best valid group is a single element.

Hints

  1. A group is valid iff all its members share one common digit. So you never need to consider arbitrary subsets — just fix the shared digit.
  2. For each digit d in 0..9, count how many array elements contain d. The largest such count is the answer.
  3. Extract a number's two digits with tens = x // 10 and ones = x % 10 (or use the string representation). Use a set per number so a number like 55 is not double-counted for digit 5.
  4. For a non-empty array the answer is at least 1, since any single element is trivially a valid group.

Loading coding console...