HebbiaAI·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026Remote

Summary

HebbiaAI software engineering interview that went straight into a meaty coding problem. It was a follow-up to standard Tic-Tac-Toe but with a lot more moving parts, and the design discussion around data layout took up more time than I expected.

Questions Asked (1)

Implement Ultimate Tic-Tac-Toe on a 9x9 grid structured as a 3x3 arrangement of 3x3 sub-boards. A move is represented as a tuple of sub-board coordinates, cell coordinates, and the player. A player claims a sub-board by getting three in a row within it, and the overall winner is whoever claims three sub-boards in a row on the outer grid. Discuss your data layout and how you'd detect wins incrementally at both levels.

Algorithms & Data StructuresSystem DesignData Modeling

Author's notes

I started with the inner board logic since it's basically just regular TTT, but the nesting tripped me up more than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by defining a clear data model: represent the board as a 3x3 array of sub-boards, each a 3x3 array of cells, and track the active sub-board constraint. Then explain incremental win detection: for each move, check only the affected row, column, and diagonal in the sub-board, and if a sub-board is won, check the corresponding lines in the outer grid. Emphasize efficiency and correctness, and discuss handling of edge cases like forced moves and draws.

Pro tip: Mention that you can precompute win lines (8 per board) and use bitboards for O(1) win checks, but keep the explanation accessible. Also, note that the active sub-board constraint can be enforced by tracking the last move's cell coordinates.

1. Define the data layout

Choose a representation: a 3x3 array of sub-boards, each a 3x3 array of cells (or a flat 9x9 array with index mapping). Track the active sub-board and the overall winner.

2. Handle move mechanics

Given a move (sub-board coords, cell coords, player), validate it against the active sub-board constraint and cell emptiness. Update the cell and determine the next active sub-board (the cell's coordinates).

3. Detect sub-board wins incrementally

After placing a mark, check only the row, column, and diagonals passing through that cell within the sub-board. If a win is found, mark the sub-board as claimed by the player.

4. Detect overall wins incrementally

When a sub-board is claimed, check the corresponding row, column, and diagonals in the outer grid. If three claimed sub-boards align, declare the overall winner.

5. Discuss edge cases and optimizations

Address draws, forced moves when the target sub-board is already won, and potential optimizations like bitboards or precomputed win lines.

Key Points to Mention

Data layout: 3x3 array of sub-boards, each with 3x3 cells; track active sub-board and overall winner.
Incremental win detection: check only lines through the last move at both sub-board and outer levels.
Active sub-board constraint: next move must be in the sub-board corresponding to the cell just played, unless that sub-board is already won.
Efficiency: avoid full-board scans; use precomputed win lines or bitboards for O(1) checks.
Edge cases: draws, forced moves, and handling when a sub-board is won but the game continues.
Complexity: O(1) per move for win detection, O(1) space for board state.

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