← Verkada Interview InsightsSoftware Engineer
Went with hash sets per row, column, and box and just iterated once through the grid.
Use a single pass over the board, maintaining hash sets for each row, column, and 3x3 sub-box to detect duplicates. For each non-empty cell, compute its sub-box index and check if the digit already exists in the corresponding sets; if it does, return false immediately. After scanning all cells, return true.
Pro tip: Clarify with the interviewer whether the function should validate only the current state or also check solvability, as this affects the approach. Also, mention that early termination on duplicate detection can save time, and discuss trade-offs between using sets versus bitmasks for space efficiency.
Confirm that the board is 9x9, empty cells are '.', and we only need to validate the current state, not solve the Sudoku. Ask if the input is guaranteed to be well-formed.
Decide on using hash sets (or boolean arrays/bitmasks) for rows, columns, and boxes. Explain that sets provide O(1) average lookup and easy duplicate detection.
Loop over each cell (i, j). If the cell is not '.', compute the box index as (i // 3) * 3 + (j // 3). Check if the digit is already in the row[i], col[j], or box[boxIndex] set; if so, return false. Otherwise, add the digit to all three sets.
After the loop, return true. State that time complexity is O(1) since the board size is fixed (81 cells), and space complexity is O(1) as well (at most 81 digits stored across sets).
Mention testing with an empty board (all '.'), a valid board, and boards with duplicates in rows, columns, and boxes. Also consider boards with invalid characters (if not guaranteed).
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.
Acknowledge that multithreading can parallelize the validation of rows, columns, and subgrids, but emphasize that for a standard 9x9 Sudoku the overhead likely outweighs the benefits. Discuss the trade-offs and when it might be worthwhile, such as for larger grids or as part of a larger system.
Pro tip: Mention that the real bottleneck is often memory access and synchronization, not CPU, so measure before optimizing. Also, note that a single-threaded solution is simpler and less error-prone, which is valuable in production code.
Confirm the size of the Sudoku (e.g., 9x9) and whether validation is a one-off or part of a high-throughput system. This determines if multithreading is even worth considering.
Break validation into independent tasks: checking each row, each column, and each 3x3 subgrid. These can be processed concurrently without data races if done carefully.
Estimate the cost of thread creation, synchronization, and merging results. For a 9x9 grid, the total work is tiny (81 cells), so overhead likely dominates.
If scaling to larger grids or many puzzles, suggest using a thread pool to validate chunks (e.g., each thread handles a set of rows/columns/subgrids) and combine results with a barrier or atomic counters.
State that for typical 9x9 Sudoku, a single-threaded approach is faster and simpler; multithreading only helps for very large grids or when validating many puzzles in parallel.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.