← Databricks Interview Insights

Databricks·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Databricks coding screen, one question the whole time. Pretty focused session, they wanted to see if you could get past the naive O(n) check and actually think about the math behind it.

Questions Asked (1)

Q1

Design a Tic-Tac-Toe class for an n x n board. Implement a move method that places a mark for a given player and returns the winning player's number if that move wins, or 0 otherwise. The solution should run in O(1) per move.

Algorithms & Data StructuresSystem Design
Author's notes

My first instinct was to scan the whole row and column after every move, which is obviously too slow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use an O(1) per move approach by maintaining row, column, and diagonal counters for each player. When a move is made, update the corresponding counters and check if any counter reaches n, indicating a win.

Pro tip: Clarify that the O(1) requirement applies per move, not per game, and mention that the board state can be stored implicitly via counters, reducing space complexity to O(n).

1. Clarify requirements and constraints

Confirm board size n, number of players (2), and that a move returns the winning player or 0. Discuss edge cases like invalid moves or moves after game ends.

2. Design data structures

Maintain arrays for row sums, column sums, and two diagonal sums for each player. Use a 2D board to track moves for validation, or use a hash set for O(1) move validation.

3. Implement move method

For a given player and position (row, col), update the corresponding row, column, and diagonal counters. Check if any counter equals n; if so, return the player.

4. Analyze complexity

Explain that each move takes O(1) time because only a constant number of counters are updated and checked. Space complexity is O(n) for the counters and board.

5. Test with examples

Walk through a small example (e.g., n=3) to demonstrate correctness, including a winning move and a non-winning move.

Key Points to Mention

  • O(1) time per move achieved by incremental updates of counters.
  • Space complexity O(n) for counters, plus O(n^2) if storing the board explicitly.
  • Handling of diagonal wins: only update diagonals when row == col or row + col == n-1.
  • Validation of moves: ensure the cell is empty and the game is not already won.
  • Return value: 0 if no win, otherwise the player number.
  • Scalability: the approach works for any n, and multiple games can be played independently.

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