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 Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Chime.

What role is this question designed for?

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

Simulate toppling board game outcome

Company: Chime

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Implement a function that, given the board size N (3–9 inclusive) and a list of move strings, returns one of: "in progress", "player 1 is the winner", or "player 2 is the winner". The board is N×N. Players alternate turns and the active player changes on each Place move: all Topple moves between two Place moves belong to the player who executed the preceding Place. Move formats: ( 1) Place: "pXY" places one piece at row X, col Y. You may place only on an empty cell or a cell already owned by the current player. Placing on an empty cell claims it for the current player; otherwise increase the stack height. ( 2) Topple: "tXYD" topples all pieces from (X,Y) in direction D ∈ {u,r,d,l}. You may topple only from a cell you own with stack height ≥2. Pick up all pieces from (X,Y) and drop them one-by-one into adjacent cells starting from the next cell along D; pieces that go off-board are lost. Captures: if a dropped piece lands on a cell owned by the opponent, that piece is captured by the opponent and added to that cell’s stack (ownership of a cell is the owner of the stack on that cell). Game end: as soon as one player has zero pieces anywhere on the board, return the other player as the winner. Assume all moves are valid and well formed. Examples: ["p10", "p12", "p10", "t10r"] → "player 1 is the winner"; ["p00", "p22", "p02", "p22", "t22u", "t02l"] → "player 2 is the winner".

Quick Answer: This question evaluates a candidate's ability to implement a discrete board-game simulation, including state management, turn-based ownership semantics, stack-based piece handling, capture mechanics, and game termination detection.

Implement a function `solution(n, moves)` that simulates a two-player stacking game on an `n x n` board and returns one of: - `"in progress"` - `"player 1 is the winner"` - `"player 2 is the winner"` Rules: 1. The board starts empty. 2. Rows and columns are zero-indexed. 3. The first `Place` move is made by player 1, the second `Place` move by player 2, the third by player 1, and so on. 4. `Topple` moves do not switch turns. Every `Topple` belongs to the same player as the most recent `Place` move. 5. Each cell stores an owner and a stack height. Move formats: - `"pXY"` — Place one piece at row `X`, column `Y`. - You may place only on an empty cell or a cell already owned by the current player. - If the cell is empty, it becomes owned by the current player with height 1. - Otherwise, increase that stack height by 1. - `"tXYD"` — Topple the entire stack from row `X`, column `Y` in direction `D`, where `D` is one of `u`, `r`, `d`, `l`. - You may topple only from a cell owned by the current player with stack height at least 2. - Pick up all pieces from `(X, Y)`, making that cell empty. - Drop the pieces one by one into consecutive cells starting from the next cell in direction `D`. - If a piece would land off the board, it is lost. - If a dropped piece lands on: - an empty cell: that cell becomes owned by the current player - the current player's cell: add the piece to that stack - the opponent's cell: the current player captures that entire stack, so ownership flips to the current player and the dropped piece is added to the stack Winning rule: - Start checking for elimination only after both players have made at least one `Place` move. - After each move, if one player has zero pieces anywhere on the board, the other player wins immediately. - If no one has won after all moves, return `"in progress"`. Assume all moves are valid and well formed.

Constraints

3 <= n <= 9
0 <= len(moves) <= 100000
Each move is either `pXY` or `tXYD`
X and Y are digits in the range [0, n - 1]
D is one of `u`, `r`, `d`, `l`
All moves are valid and well formed

Examples

Input: (3, ["p10", "p12", "p10", "t10r"])

Expected Output: "player 1 is the winner"

Explanation: Player 1 builds a stack of 2 at (1,0), then topples right. One piece lands on (1,1), and the next lands on player 2's cell (1,2), capturing it. Player 2 is left with zero pieces.

Input: (3, ["p00", "p22", "p02", "p22", "t22u", "t02l"])

Expected Output: "player 2 is the winner"

Explanation: After `p22`, both `t22u` and `t02l` belong to player 2 because no new Place move occurs. Player 2 first captures (0,2), then topples it left to capture (0,0), eliminating player 1.

Input: (4, ["p00", "p11", "p00", "t00d"])

Expected Output: "in progress"

Explanation: Player 1 topples two pieces downward from (0,0) to (1,0) and (2,0), but player 2 still has a piece at (1,1). Both players still have pieces.

Input: (3, [])

Expected Output: "in progress"

Explanation: No moves have been played, so the game is still in progress.

Input: (3, ["p01", "p22", "p01", "t01u"])

Expected Output: "player 2 is the winner"

Explanation: Player 1 topples a stack of 2 upward from the top row, so both pieces fall off the board and are lost. Since both players had already placed at least once, player 1 is eliminated and player 2 wins.

Solution

def solution(n, moves):
    owners = [[0] * n for _ in range(n)]
    heights = [[0] * n for _ in range(n)]

    # totals[player] = total number of pieces currently owned by that player
    totals = [0, 0, 0]
    placed_once = [False, False, False]

    # The current player is the player who made the most recent Place move.
    current_player = 0
    place_count = 0

    directions = {
        'u': (-1, 0),
        'r': (0, 1),
        'd': (1, 0),
        'l': (0, -1),
    }

    def check_winner():
        if placed_once[1] and placed_once[2]:
            if totals[1] == 0:
                return "player 2 is the winner"
            if totals[2] == 0:
                return "player 1 is the winner"
        return None

    for move in moves:
        if move[0] == 'p':
            current_player = 1 if place_count % 2 == 0 else 2
            place_count += 1
            placed_once[current_player] = True

            x = int(move[1])
            y = int(move[2])

            if owners[x][y] == 0:
                owners[x][y] = current_player
                heights[x][y] = 1
            else:
                heights[x][y] += 1

            totals[current_player] += 1

        else:  # Topple
            x = int(move[1])
            y = int(move[2])
            d = move[3]
            dx, dy = directions[d]

            stack_size = heights[x][y]

            # Remove the source stack from the current player.
            owners[x][y] = 0
            heights[x][y] = 0
            totals[current_player] -= stack_size

            # Only cells until the board edge can receive pieces.
            step = 1
            while step <= stack_size:
                nx = x + dx * step
                ny = y + dy * step

                if not (0 <= nx < n and 0 <= ny < n):
                    break

                if owners[nx][ny] == 0:
                    owners[nx][ny] = current_player
                    heights[nx][ny] = 1
                    totals[current_player] += 1
                elif owners[nx][ny] == current_player:
                    heights[nx][ny] += 1
                    totals[current_player] += 1
                else:
                    other = owners[nx][ny]
                    captured_height = heights[nx][ny]

                    totals[other] -= captured_height
                    owners[nx][ny] = current_player
                    heights[nx][ny] = captured_height + 1
                    totals[current_player] += captured_height + 1

                step += 1

        result = check_winner()
        if result is not None:
            return result

    return "in progress"

Time complexity: O(len(moves) * n). Space complexity: O(n^2).

Hints

Store each board cell as two pieces of information: owner and stack height. Also keep total piece counts for each player so you can detect a winner in O(1) after every move.
During a topple, only the cells from the source to the board edge can receive pieces. Since `n <= 9`, at most `n - 1` dropped pieces stay on the board; the rest are immediately lost.

Quick Overview

This question evaluates a candidate's ability to implement a discrete board-game simulation, including state management, turn-based ownership semantics, stack-based piece handling, capture mechanics, and game termination detection.