← Hebbia Interview Insights

Hebbia·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026Remote

Summary

HebbiaAI software engineer interview that built on a standard Tic-Tac-Toe problem by pushing into Ultimate Tic-Tac-Toe territory. The jump in complexity caught me pretty flat-footed and I spent more time than I'd like to admit just trying to get the data layout straight in my head.

Questions Asked (1)

Q1

Implement Ultimate Tic-Tac-Toe on a 9x9 grid structured as a 3x3 arrangement of 3x3 sub-boards. A move is represented as (sub_row, sub_col, cell_row, cell_col, player). Winning a sub-board claims it for the outer grid, and winning three claimed sub-boards in a row wins the game. Discuss data layout and incremental win detection at both levels.

System DesignAlgorithms & Data StructuresData Modeling
Author's notes

I froze a bit figuring out where to even start.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the rules and constraints, then propose a data layout that supports efficient access and updates, such as a 3D array or a flat array with index mapping. Explain how to perform incremental win detection at both sub-board and global levels using counters or bitmasks, and discuss trade-offs between different approaches.

Pro tip: Emphasize that incremental win detection is crucial for performance in real-time games, and mention how you would handle edge cases like a sub-board being full without a winner or a move sending the opponent to an already won sub-board.

1. Clarify Rules and Constraints

Confirm the rules: a move is (sub_row, sub_col, cell_row, cell_col, player); winning a sub-board claims it; winning three claimed sub-boards in a row wins. Discuss constraints like board size, number of moves, and performance requirements.

2. Design Data Layout

Propose a data structure to represent the 9x9 grid, such as a 3D array (3x3x3x3) or a flat array of 81 cells. Explain how to map (sub_row, sub_col, cell_row, cell_col) to an index, and how to track sub-board ownership and global win status.

3. Implement Incremental Win Detection

Describe how to detect wins incrementally after each move: for the sub-board, update row/column/diagonal counters or bitmasks for the player; if a win occurs, mark the sub-board as won and update global counters for the outer grid similarly.

4. Handle Edge Cases and Optimizations

Discuss edge cases: sub-board full without winner, move sent to already won sub-board (if allowed), and global win detection. Mention optimizations like early termination, bitwise operations, and avoiding full board scans.

5. Analyze Complexity and Trade-offs

Compare time and space complexity of incremental detection versus naive scanning. Explain why incremental is O(1) per move for win checks, and discuss memory overhead of counters versus bitmasks.

Key Points to Mention

  • Use a 3D array or flat array with index mapping for the 9x9 grid.
  • Track sub-board winners and global winners separately.
  • Incremental win detection using row/column/diagonal counters or bitmasks.
  • Update global win detection when a sub-board is won.
  • Handle edge cases: full sub-board without winner, moves to won sub-boards.
  • Time complexity: O(1) per move for win detection with incremental approach.

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