Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Google SWE coding round, one question the whole time. The problem was a Mahjong hand validator and it looked deceptively clean on the surface but the combinatorics got messy fast.

Questions Asked (1)

Given an array of 14 integers (each between 1 and 9) representing a Mahjong hand, determine whether the hand is a winning hand. A winning hand consists of exactly one pair and four melds, where each meld is either three identical tiles or three consecutive values.

Algorithms & Data Structures

Author's notes

I started by sorting and trying to greedily strip out sequences and triplets, which works in some cases but blows up when you have ambiguous tile groups.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a recursive search: first identify the pair, then recursively check if the remaining tiles can be partitioned into four melds. Use a frequency array of size 10 (indices 1-9) to efficiently track tile counts and backtrack when a meld choice fails.

Pro tip: Before coding, clarify edge cases like multiple possible pairs or ambiguous meld choices; mentioning that you'll test with hands like 1,1,1,2,3,4,5,6,7,8,9,9,9,9 shows thoroughness.

1. Clarify rules and constraints

Confirm that the hand has exactly 14 tiles, values 1-9, and that a winning hand requires one pair and four melds (triplets or sequences). Ask if there are any special hands or if the input is always valid.

2. Choose data representation

Use a frequency array of size 10 (index 0 unused) to count occurrences of each tile. This allows O(1) checks for removing a triplet or sequence.

3. Identify the pair and recurse

Iterate over possible pairs (tiles with count >= 2). For each, decrement the pair, then recursively attempt to remove four melds from the remaining tiles.

4. Implement recursive meld removal

In the recursion, find the smallest tile with count > 0. Try removing a triplet (if count >= 3) or a sequence (if next two tiles have count > 0). Backtrack if neither leads to a solution.

5. Analyze complexity and optimize

Discuss time complexity: at most 9 possible pairs, and recursion depth 4, with branching factor at most 2. Mention that memoization or pruning can further optimize, but is not strictly needed for 14 tiles.

Key Points to Mention

Use a frequency array to efficiently track tile counts and check meld availability.
Backtracking is necessary because greedy choices (e.g., always taking triplets first) can fail.
The recursion depth is small (at most 4 melds), so exponential blowup is not a concern.
Edge cases: multiple pairs, tiles with count > 4 (invalid), and hands that are already sorted.
Time complexity: O(9 * 2^4) in the worst case, which is effectively constant.
Testing: include cases like all sequences, all triplets, mixed, and non-winning hands.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.