← Create New Paste

Valid Sudoku in a Coding Interview: A Clean Walkthrough

4 views
"Determine if a 9x9 Sudoku board is valid" looks like a puzzle question, but interviewers use it to test something practical: can you translate a set of rules into a data structure, keep the code tidy, and explain your choices while you type? Here is how to handle it from the first clarifying question to the final complexity discussion. 1. Clarify before you code Ask three things. Does the board need to be solvable, or only consistent with the rules so far? (Almost always: only consistent.) How are empty cells represented, usually "." or 0? Is the input always 9x9? Saying these out loud shows the interviewer you read requirements carefully, which matters more than the algorithm itself. 2. State the rules as constraints A filled board is valid when no digit repeats in any row, any column, or any of the nine 3x3 boxes. That is three families of constraints, 27 groups in total. Once you phrase it like that, the solution almost writes itself: track which digits you have already seen in each group. 3. The single-pass solution Create 9 sets for rows, 9 for columns and 9 for boxes. Walk every cell once. Skip empty cells. For a digit d at (r, c), compute the box index as (r // 3) * 3 + (c // 3). If d is already in rows[r], cols[c] or boxes[b], return false. Otherwise add it to all three. If you finish the loop, return true. In Python the core loop is about eight lines. Name the box formula out loud and test it on a corner: cell (4, 7) belongs to box (1 * 3) + 2 = 5, the middle-right box. Interviewers love seeing you sanity-check an index calculation instead of trusting it. 4. Complexity, honestly stated Because the board is fixed at 81 cells, time and space are technically O(1). It is better to also say "O(n^2) for an n x n generalisation" so the interviewer sees you understand the scaling. 5. Common follow-ups - Bitmasks instead of sets: store each group as a 9-bit integer and check with (mask >> d) & 1. It is faster and uses less memory, and is a nice way to show range. - One set of encoded strings: add keys like "5 in row 2", "5 in col 7", "5 in box 1" into a single set. Short and readable, though slower. - Sudoku Solver: the natural next question. It uses the same three constraint structures plus backtracking, so building the validator cleanly first pays off. - Variable board sizes: replace 3 with sqrt(n) and validate that n is a perfect square. 6. Mistakes that cost points Forgetting to skip empty cells, computing the box index as r // 3 + c // 3 (which collides), and checking the whole board three separate times when one pass is enough. Also avoid going silent while debugging; narrate what you are checking. 7. Practise the delivery, not just the code Most candidates who know this problem still stumble when someone is watching. Rehearse explaining the box formula and complexity in under a minute. If you want support during the real thing, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, so you can stay structured when nerves hit. Validity checks like this appear in many forms, from spreadsheets to form validation to game state. Treat Valid Sudoku as practice for turning rules into constraints, and you will recognise the pattern quickly next time.
Created Nov 16, 2026 23:09 Expires Nov 16, 2027 23:09