← Upstart Interview Insights

Upstart·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Got a Sudoku validation problem for a Software Engineer screen at Upstart. Pretty classic constraints question, nothing too wild, but the 3x3 box indexing is where people tend to trip up.

Questions Asked (1)

Q1

Given a 9x9 Sudoku board partially filled with digits 1-9 and '.' for empty cells, write a function to determine if the board is valid. A valid board has no repeated digits in any row, column, or 3x3 sub-box. Empty cells are ignored and the board doesn't need to be solvable.

Algorithms & Data Structures
Author's notes

The row and column checks felt straightforward, just a set per row and per column.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a single pass over the board, checking each filled cell against sets for its row, column, and 3x3 sub-box. If any digit is already present in the corresponding set, return false; otherwise, add it and continue. Return true after processing all cells.

Pro tip: Clarify that the board only needs to be validated, not solved, and mention that you can optimize space by using bitmasks instead of sets if needed. This shows you understand the problem's constraints and can adapt to follow-up questions.

1. Clarify requirements and edge cases

Confirm that empty cells are ignored, the board may be unsolvable, and only validity is checked. Ask about input size (fixed 9x9) and whether modification is allowed.

2. Choose data structures

Decide on using sets (or boolean arrays/bitmasks) to track seen digits for each row, column, and sub-box. Explain the trade-offs between clarity and efficiency.

3. Iterate through the board

Loop over each cell; if it's not '.', compute its sub-box index (row/3, col/3) and check for duplicates in the corresponding row, column, and sub-box sets.

4. Validate and update

If a duplicate is found, return false immediately. Otherwise, add the digit to the sets for its row, column, and sub-box.

5. Return result and discuss complexity

After the loop, return true. State that time complexity is O(1) (since 81 cells) and space is O(1) (fixed 9x9), but generally O(n^2) for an n x n board.

Key Points to Mention

  • Use separate sets (or arrays) for rows, columns, and 3x3 sub-boxes to track seen digits.
  • Compute sub-box index as (row // 3) * 3 + (col // 3) or use a 3D array.
  • Skip empty cells ('.') and only process digits 1-9.
  • Early return false upon detecting a duplicate to avoid unnecessary work.
  • Time and space complexity are O(1) for fixed 9x9, but O(n^2) for general n x n.
  • Alternative approach: use bitmasks (integers) to represent seen digits for each row/column/box, reducing space and potentially speeding up checks.

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