The interview question I just answered with Uber.

The answer provided to them had O(2N),
while this slightly revised has O(N).

Text of the challenge:

Sudoku is a game played on a 9x9 grid. The object of the game is to fill in
every square on the grid with a number, 1-9, so that:

  Every row contains the numbers 1-9
  Every column contains the numbers 1-9
  Each of the 9 3x3 sub-grids contains the numbers 1-9

In addition to the numbers 1-9, we will also use the number 0 to indicate an
empty space that has not been filled in yet. Duplicate 0 entries in rows,
columns, and 3x3 sub-grids are valid.

We are going to write a validator for a Sudoku Board. Imagine you are solving
a Sudoku (http://www.colinj.co.uk/Sudoku_help.htm) puzzle. You want to know
if the current board has any non-zero duplicates in its rows, columns, and 3x3
subgrids.

Represent the Sudoku board as a two-dimensional array of integers.

boolean isValidBoard(int[][] board) {
  // TODO: fill this in
  return false;
}