← Verkada Interview InsightsSoftware Engineer

Verkada·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Verkada software engineer interview that was mostly a single coding problem with a design twist tacked on at the end. The main question was straightforward enough but the follow-up about parallelism is where things got interesting and where I felt a little out of my depth.

Questions Asked (2)

Q1

Given a 9x9 Sudoku board where some cells are empty (marked as '.'), write a function to determine if the current board state is valid. A valid board has no duplicate digits in any row, column, or 3x3 sub-box. Empty cells are ignored.

Algorithms & Data Structures
Author's notes

Went with hash sets per row, column, and box and just iterated once through the grid.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

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.

1. Clarify requirements and constraints

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.

2. Choose data structures

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.

3. Iterate through the board

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.

4. Return result and analyze complexity

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).

5. Test with edge cases

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).

Key Points to Mention

  • Use of hash sets or boolean arrays for O(1) duplicate checks.
  • Box index calculation: (row // 3) * 3 + (col // 3).
  • Single-pass approach with early termination.
  • Time and space complexity are O(1) due to fixed board size.
  • Handling of empty cells by skipping them.
  • Clarifying that the function only validates the current state, not solvability.

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

Q2

Follow-up: how would you use multithreading to speed up the Sudoku validation, and does it actually help here?

Technical Trade-offsSystem Design
Author's notes

This is where I stumbled a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

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.

1. Clarify the problem and constraints

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.

2. Identify parallelizable units

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.

3. Analyze overhead vs. benefit

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.

4. Propose a multithreaded design (if applicable)

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.

5. Conclude with a recommendation

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.

Key Points to Mention

  • Amdahl's Law: the speedup is limited by the serial portion (e.g., merging results).
  • Thread overhead: creation, context switching, and synchronization can exceed the work itself for small tasks.
  • Data partitioning: rows, columns, and subgrids are independent, but subgrids overlap with rows/columns, requiring careful indexing.
  • False sharing: adjacent memory locations accessed by different threads can degrade performance.
  • Alternative: use SIMD or bitwise operations for a single-threaded speedup.
  • When it helps: larger grids (e.g., 16x16 or 25x25) or batch validation of many puzzles.

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