How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Determine winner in stack-merging game

Q: Determine winner in stack-merging game

This question evaluates understanding of combinatorial game theory, impartial game analysis, state-space encoding, and efficient state-space search techniques.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Game: Babylon stack merging (two-player, perfect play) You are given a two-player turn-based game. There are `n` stacks of tiles. Each stack has: - a **height** (positive integer) - a **top color** (one of `Y`, `W`, `G`, `B`) ### Initial state - There are `n` stacks, each of **height = 1**. - The `i`-th stack’s top color is `colors[i]`. ### Legal move On your turn, you must pick **two different stacks** `A` and `B` and merge **the entire stack `A` onto the top of stack `B`**, but only if **at least one** condition holds: 1. `height(A) == height(B)`, or 2. `topColor(A) == topColor(B)` After merging: - `height(B) = height(A) + height(B)` - `topColor(B) = topColor(A)` (because `A` is placed on top) - stack `A` is removed (total number of stacks decreases by 1) ### Winning condition - If it is your turn and there is **no legal merge**, you **lose**. - Equivalently, the player who makes the **last legal move** wins. ### Task Given the initial `colors` array, determine whether the **first player** has a winning strategy assuming optimal play from both players. Return `true` if the first player can force a win; otherwise return `false`. ### Constraints (you may assume) - `1 <= n <= 12` - `colors[i]` is in `{ 'Y','W','G','B' }` ### Example (illustrative) - Input: `colors = ["Y","Y"]` - There is one legal move (same top color). First player moves and wins → output `true`.

Quick Answer: This question evaluates understanding of combinatorial game theory, impartial game analysis, state-space encoding, and efficient state-space search techniques.

You are given a two-player game with several stacks of tiles. Initially, there are n stacks, each with height 1, and the i-th stack has top color colors[i]. On each turn, a player must choose two different stacks A and B and place the entire stack A on top of stack B. This move is legal only if the two stacks have the same height or the same top color. After merging, the new stack has height height(A) + height(B), its top color becomes the top color of A, and stack A disappears. If a player has no legal move on their turn, they lose. Given the initial colors array, determine whether the first player can force a win assuming both players play optimally.

Constraints

1 <= len(colors) <= 12
Each colors[i] is one of 'Y', 'W', 'G', 'B'
All stacks initially have height 1

Examples

Input: ['Y']

Expected Output: False

Explanation: With only one stack, there are no two different stacks to merge, so the first player loses immediately.

Input: ['Y', 'W']

Expected Output: True

Explanation: The two stacks have equal height, so one legal merge exists. After that, only one stack remains and the second player has no move.

Input: ['Y', 'W', 'G']

Expected Output: True

Explanation: The first player can merge 'Y' onto 'W', leaving stacks (2, 'Y') and (1, 'G'). These have different heights and different top colors, so the second player has no legal move.

Input: ['Y', 'Y', 'Y']

Expected Output: False

Explanation: Any first move leaves two stacks: (2, 'Y') and (1, 'Y'). The second player can merge them because the top colors match, making the last move.

Input: ['Y', 'Y', 'W']

Expected Output: True

Explanation: The first player can merge one 'Y' onto the other 'Y', leaving (2, 'Y') and (1, 'W'). Different heights and different top colors mean no move for the second player.

Input: ['Y', 'Y', 'Y', 'Y', 'Y']

Expected Output: False

Explanation: All stacks always share the same top color, so a merge is always possible until one stack remains. That means exactly 4 moves occur, so the second player makes the last move.

Input: ['Y', 'W', 'G', 'B']

Expected Output: True

Explanation: The first player can create a stack of height 2 with a color different from the two remaining single stacks, for example merge 'Y' onto 'W'. Then the second player is forced to merge the two height-1 stacks, creating two height-2 stacks, and the first player makes the final merge.

Hints

Only the current height and top color of each stack matter. The deeper contents of a stack never affect future moves.
Since the order of stacks does not matter, memoize game states using a canonical sorted representation of (height, color) pairs.

Quick Overview

This question evaluates understanding of combinatorial game theory, impartial game analysis, state-space encoding, and efficient state-space search techniques.