Quick Overview

This Coding & Algorithms question evaluates algorithmic reasoning about combinatorial search and multiset partitioning, testing the candidate's ability to represent and manipulate tile counts and validate pattern-based groupings.

Determine if a 14-tile hand is winning

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an integer array `tiles` of length 14 representing a Mahjong-like hand. Each integer is a tile value from 1 to 9 (single suit). You may reorder the tiles. A hand is **winning** if it can be partitioned into: - **1 pair**: two identical tiles, and - **4 melds** (each meld uses 3 tiles), where each meld is either: - a **triplet**: three identical tiles (e.g., 7,7,7), or - a **sequence**: three consecutive values (e.g., 2,3,4). Each tile can be used at most once. Return `true` if the hand is winning, otherwise return `false`. Assumptions/constraints: - `tiles.length == 14` - `1 <= tiles[i] <= 9` - Each value can appear multiple times (as in a real tile set).

Overview: This Coding & Algorithms question evaluates algorithmic reasoning about combinatorial search and multiset partitioning, testing the candidate's ability to represent and manipulate tile counts and validate pattern-based groupings.

Read the full Google Software Engineer interview experience this question came from

You are given an integer array `tiles` of length 14 representing a Mahjong-like hand from a single suit. Each value is between 1 and 9, and you may reorder the tiles. A hand is **winning** if all 14 tiles can be partitioned into exactly: - **1 pair**: two identical tiles - **4 melds**: each meld uses 3 tiles and is either: - a **triplet**: three identical tiles - a **sequence**: three consecutive values Each tile must be used exactly once. Return `True` if the hand is winning, otherwise return `False`.

Constraints

  • `tiles.length == 14`
  • `1 <= tiles[i] <= 9`
  • Tiles may contain duplicates

Examples

Input: ([1,1,1,2,3,4,2,3,4,5,6,7,9,9],)

Expected Output: True

Explanation: A valid partition is pair `9,9`, triplet `1,1,1`, sequence `2,3,4`, sequence `2,3,4`, and sequence `5,6,7`.

Input: ([2,2,2,3,3,3,4,4,4,5,5,5,9,9],)

Expected Output: True

Explanation: Use pair `9,9` and four triplets: `2,2,2`, `3,3,3`, `4,4,4`, `5,5,5`.

Hints

  1. Count how many times each value from 1 to 9 appears instead of working directly with the raw array.
  2. Try every possible pair first. After removing a pair, recursively remove the smallest remaining tile as part of either a triplet or a sequence.

Community answers

Answer by memo

def solution(tiles): if len(tiles) != 14: return False count = [0] * 10 # count[v] = how many tiles of value v (1..9) for t in tiles: count[t] += 1 def can_form_melds(): # find the smallest value that still has tiles remaining i = next((v for v in range(1, 10) if count[v] > 0), None) if i is None: return True # no tiles left -> all successfully used as melds # try a triplet of i, i, i if count[i] >= 3: count[i] -= 3 if can_form_melds(): count[i] += 3 return True count[i] += 3 # try a sequence i, i+1, i+2 if i <= 7 and count[i] > 0 and count[i + 1] > 0 and count[i + 2] > 0: count[i] -= 1 count[i + 1] -= 1 count[i + 2] -= 1 if can_form_melds(): count[i] += 1 count[i + 1] += 1 count[i + 2] += 1 return True count[i] += 1 count[i + 1] += 1 count[i + 2] += 1 return False # neither option worked # try every possible pair value for p in range(1, 10): if count[p] >= 2: count[p] -= 2 if can_form_melds(): count[p] += 2 return True count[p] += 2 return False

Loading coding console...