Dot grid game winner: Frontier Interview's solution

Question: Dot grid game winner

Companies: Google

Difficulty: Medium

Problem statement

Two players play a dots-and-boxes style game on a 9 x 9 grid of dots. The grid has 8 x 8 = 64 unit squares ("boxes"). Rows and columns are numbered 0 to 8.

You are given moves, a list of the sticks placed in order. moves[i] = [r1, c1, r2, c2] places a stick between dot (r1, c1) and dot (r2, c2). The two dots are always horizontally or vertically adjacent, and they may appear in either order.

Players strictly alternate. Player 1 makes moves 1, 3, 5, ... and player 2 makes moves 2, 4, 6, ..., whether or not a move closes a box. Whoever places the fourth side of a box scores that box. A single stick can close two boxes at once, and both count for its player.

Implement find_winner(moves: list[list[int]]) -> int. Return 1 or 2 for the player who owns more boxes after all moves, or 0 for a tie.

Constraints

0 <= len(moves) <= 144 (the total number of sticks on a 9 x 9 dot grid)
0 <= r1, c1, r2, c2 <= 8
No stick is placed twice. (A natural follow-up asks you to validate this yourself.)

Example 1

moves = [[0,0,0,1], [0,0,1,0], [1,0,1,1], [0,1,1,1]]
output: 2

The first four sticks are the four sides of the top-left box. The 4th move is player 2's, so player 2 scores 1 and player 1 scores 0.

Example 2

moves = [[0,1,0,0], [5,5,5,6], [1,0,0,0], [6,6,6,7], [1,1,1,0], [7,7,7,8], [1,1,0,1]]
output: 1

Player 1's sticks (moves 1, 3, 5, 7) are the four sides of the top-left box, written with the endpoints reversed. Player 1 places the last side on move 7. Player 2's sticks close nothing.

Expected: O(1) work per move.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is Dots and Boxes scoring. A 9 x 9 grid of dots has 8 x 8 = 64 unit boxes. A box belongs to the player who places its fourth side. You replay the moves, credit each box to the right player, and compare the totals.

Brute force. After every move, scan all 64 boxes and count the closed ones. The increase since the previous move is what the mover scored. That costs O(B) per move, where B is the number of boxes. For B = 64 it is fine, but it does not scale, and it misses the key observation.

The useful fact. A stick touches at most two boxes:

a horizontal stick (r, c)-(r, c+1) is the bottom of box (r-1, c) and the top of box (r, c);
a vertical stick (r, c)-(r+1, c) is the right side of box (r, c-1) and the left side of box (r, c).

Name a box by its top-left dot. A box can only close on the move that places one of its four sides. So after each move you check just those two candidate boxes (skipping any off the board). Each move is O(1).

Representation. Keep two boolean grids. h[r][c] is the stick (r, c)-(r, c+1) and v[r][c] is the stick (r, c)-(r+1, c). Box (r, c) is closed when h[r][c], h[r+1][c], v[r][c] and v[r][c+1] are all set. Sort the two endpoints first so the move [0,1,0,0] and the move [0,0,0,1] mean the same stick.

Whose move it is. In the base version players strictly alternate: move i (0-indexed) belongs to player i % 2 + 1, even after closing a box. The classic Dots and Boxes rule (closing a box earns another move) is a common part 2. The code handles both with a flag.

Invariants.

Each stick is placed at most once. A repeat is rejected, so no box is counted twice.
A box is counted exactly once: on the move that sets its last missing side, both candidate checks happen after that side is set, and no later move can touch a box whose four sides are all set.
One stick can close two boxes at once (a shared middle side). Both go to the mover.

Code

from typing import List


class DotGrid:
    """Board of n x n dots. Edges are stored by orientation:
    h[r][c] is the stick (r, c)-(r, c+1); v[r][c] is the stick (r, c)-(r+1, c).
    The box with top-left dot (r, c) is closed when h[r][c], h[r+1][c],
    v[r][c] and v[r][c+1] are all placed."""

    def __init__(self, n: int = 9) -> None:
        self.n = n
        self.h = [[False] * (n - 1) for _ in range(n)]
        self.v = [[False] * n for _ in range(n - 1)]

    def _closed(self, r: int, c: int) -> bool:
        if not (0 <= r < self.n - 1 and 0 <= c < self.n - 1):
            return False
        return (self.h[r][c] and self.h[r + 1][c]
                and self.v[r][c] and self.v[r][c + 1])

    def place(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """Place one stick and return how many boxes it closed (0, 1 or 2)."""
        (r1, c1), (r2, c2) = sorted([(r1, c1), (r2, c2)])
        for r, c in ((r1, c1), (r2, c2)):
            if not (0 <= r < self.n and 0 <= c < self.n):
                raise ValueError("dot off the board")
        if r1 == r2 and c2 == c1 + 1:          # horizontal stick
            if self.h[r1][c1]:
                raise ValueError("stick already placed")
            self.h[r1][c1] = True
            # Only the box above and the box below can close.
            return self._closed(r1 - 1, c1) + self._closed(r1, c1)
        if c1 == c2 and r2 == r1 + 1:          # vertical stick
            if self.v[r1][c1]:
                raise ValueError("stick already placed")
            self.v[r1][c1] = True
            # Only the box to the left and the box to the right can close.
            return self._closed(r1, c1 - 1) + self._closed(r1, c1)
        raise ValueError("dots are not adjacent")


def find_winner(moves: List[List[int]], n: int = 9,
                extra_turn: bool = False) -> int:
    """Return 1 or 2 for the player with more boxes, 0 for a tie.

    extra_turn=False: players strictly alternate (move i belongs to player
    i % 2 + 1). extra_turn=True: the classic rule, where a player who closes
    a box moves again."""
    board = DotGrid(n)
    score = [0, 0]
    player = 0
    for i, (r1, c1, r2, c2) in enumerate(moves):
        if not extra_turn:
            player = i % 2
        gained = board.place(r1, c1, r2, c2)
        score[player] += gained
        if extra_turn and gained == 0:
            player ^= 1
    if score[0] == score[1]:
        return 0
    return 1 if score[0] > score[1] else 2

Complexity

DotGrid(n): O(n²) time and space for the two edge grids. For the fixed 9 x 9 board that is constant.
place: O(1). It does one lookup and one write, then checks at most two boxes of four sides each.
find_winner: O(m) time for m moves, plus the O(n²) board. The brute-force rescan would be O(m · n²).

Test cases

[[0,0,0,1],[0,0,1,0],[1,0,1,1],[0,1,1,1]] gives 2. The 4th stick closes box (0,0), and moves 2 and 4 are player 2's.
[[0,1,0,0],[5,5,5,6],[1,0,0,0],[6,6,6,7],[1,1,1,0],[7,7,7,8],[1,1,0,1]] gives 1. Endpoints are given in reverse order, and player 1 closes box (0,0) on move 7.
[] gives 0 (tie at 0-0).
On a 3 x 3 dot board, place the outer sides of boxes (0,0) and (0,1) first, then the shared middle stick [0,1,1,1] last. That last stick closes two boxes at once, and both go to its mover.
Strict alternation, where player 2 closes one box and player 1 closes the next: 0 (tie). With the extra-turn rule the same move list gives 2, because player 2 keeps the turn and closes both.
Invalid input: diagonal [0,0,1,1], non-adjacent [0,0,0,2], off-board [0,8,0,9], or the same stick twice raise ValueError. Ask the interviewer whether the input is guaranteed valid. If it is, the checks can go.
A full game of all 144 sticks (72 horizontal + 72 vertical on 9 x 9): the scores always add up to 64.

Follow-ups

Classic rule: closing a box gives another move. Who moves next now depends on the result of each move. You keep a player variable and flip it only when gained == 0 (the extra_turn flag). The scoring logic does not change.
Streaming / live game API. Expose move(r1, c1, r2, c2) -> int that returns the boxes gained, and winner() or scores() methods. Keep the scores and the current player inside the class. Each call stays O(1). Validate moves on input and reject anything after the board is full (count placed sticks against 2·n·(n-1)).
Rectangular or very large sparse boards. Use rows x cols dots. For huge boards, store placed sticks in a hash set of normalized (r1, c1, r2, c2) tuples instead of dense grids. The box check becomes four set lookups. Memory is O(m) instead of O(n²).
Report who owns each box, or detect the move when the game was decided. Record owner[r][c] when a box closes. The game is decided once one player's score is more than the boxes still open (total - s1 - s2). That check is O(1) after each move, so you can stop early.
Best play: can the player to move force a win? This is a game-tree search: minimax with memoization over the set of placed sticks (a bitmask), plus alpha-beta pruning. It is exponential. It only works for tiny boards (2 x 2 or 3 x 3 boxes). For real boards you discuss chain and long-chain heuristics. Good candidates name the blow-up instead of pretending it is tractable.

Interviewer expectations

Mid-level (L4)

Picks a clear edge representation and gets the index mapping right for both orientations.
Credits boxes to the mover with correct parity, including a stick that closes two boxes.
Handles endpoints given in either order and off-board neighbor boxes. Runs through a small example by hand.

Senior (L5)

Starts from the O(1) "only two candidate boxes" observation instead of rescanning the board, and explains why a box can't be double-counted.
Asks about input validity (duplicates, non-adjacent dots, board size) and turn rules before coding. Keeps validation separate from scoring.
Extends to the extra-turn rule and a stateful move() API without rewriting the core.

Staff (L6+)

Treats the board as a reusable component: rectangular sizes, a sparse store for large boards, early termination when the result is decided, per-box ownership for replay or UI.
Discusses the optimal-play follow-up honestly: minimax over edge bitmasks, its state-space size, and where it stops being feasible.
Considers concurrency or multiplayer service concerns if asked (serialize moves per game, idempotent move IDs), without over-engineering the base answer.