Verkada Inc.·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Verkada coding screen, one question about validating a Sudoku board. Pretty standard algorithmic problem but the edge cases tripped me up more than I expected.

Questions Asked (1)

Given a 9x9 Sudoku board that may be partially filled, determine whether it is valid. Each row, column, and 3x3 sub-box must contain the digits 1-9 with no repeats. Empty cells are marked with a dot and don't need to be validated.

Algorithms & Data Structures

Author's notes

I went straight for sets and tracked each row, column, and box in a single pass.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a single pass through the board, maintaining hash sets for each row, column, and 3x3 sub-box to detect duplicates. For each filled cell, check if the digit already exists in the corresponding row, column, or box; if so, return false. Otherwise, add the digit to all three sets and continue. Return true if no duplicates are found.

Pro tip: Clarify with the interviewer whether the board is guaranteed to be 9x9 and whether empty cells are always represented by '.', as this affects input validation. Also, mention that you can optimize space by using bitmasks instead of sets, which is a common follow-up.

1. Understand the problem and constraints

Confirm that the board is 9x9, empty cells are '.', and only filled cells need validation. Ask if the board is guaranteed to be valid in terms of size and characters.

2. Choose data structures

Decide to use hash sets for rows, columns, and boxes, or bitmasks for space efficiency. Explain the trade-offs.

3. Iterate through the board

Loop over each cell. If the cell is not '.', compute the box index (row/3)*3 + col/3. Check if the digit exists in the corresponding row, column, or box set.

4. Validate and update

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

5. Return result and discuss complexity

After the loop, return true. Mention that time complexity is O(1) since the board size is fixed (81 cells), and space complexity is O(1) as well.

Key Points to Mention

Single-pass approach with O(1) time and space due to fixed board size.
Use of hash sets or bitmasks to track seen digits.
Box index calculation: (row/3)*3 + col/3.
Handling of empty cells ('.') by skipping validation.
Early termination upon finding a duplicate.
Potential follow-up: optimizing space with bitmasks or using arrays of size 9.

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