Google Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
A simpler solution would be to have an auxiliary array Test[1..9] whose elements are all initialized to 1 before the scanning of a row or a column or a 3x3 block.
When traversing each of the 9 rows/columns/3x3 blocks, clear the value of Test[k] against the number k encountered in the sudoku solution and at the end of the iteration check that whole Test[] array is cleared.
Here's my solution using XORs
public static bool VerifySudoku(int[,] sudokuMatrix)
{
if (sudokuMatrix.GetLength(0) != sudokuMatrix.GetLength(1))
throw new Exception("Number of rows in the sudoku matrix does not match the number of columns.");
if (sudokuMatrix.GetLength(0) != 9)
throw new Exception("For now let's just play with a 9x9 sudoku matrix.");
int nine1s = 0x1FF;//0000 0000 0000 0000 0000 0001 1111 1111
int[] colValidator = new int[9];//{0x1FF, 0x1FF, 0x1FF, 0x1FF, 0x1FF, 0x1FF, 0x1FF, 0x1FF, 0x1FF}
int[,] blockValidator = new int[3, 3];//{{0x1FF, 0x1FF, 0x1FF}, {0x1FF, 0x1FF, 0x1FF}, {0x1FF, 0x1FF, 0x1FF}}
for (int i = 0; i < 9; i++)
{
colValidator[i] = nine1s;
if (i < 3)
{
for (int j = 0; j < 3; j++)
{
blockValidator[i, j] = nine1s;
}
}
}
for (int row = 0; row < 9; row++)
{
int rowValidator = nine1s;
for (int col = 0; col < 9; col++)
{
int shifted1 = 1 << sudokuMatrix[row, col];
int blockRow = row / 3;
int blockCol = col / 3;
colValidator[col] ^= shifted1;
rowValidator ^= shifted1;
blockValidator[blockRow, blockCol] ^= shifted1;
}
if (rowValidator != 0)
return false; // the row did not have all digits 1-9
}
//similar row, these are validations for col and blocks
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (colValidator[i * 3 + j] != 0
|| blockValidator[i, j] != 0)
return false;
}
}
return true;
}
Since we know the there are only 9 numbers, we do not need to use hash table. An array is enough.
public boolean isValidSudoku(char[][] board) {
if(board == null)
return false;
for(int i = 0; i < 9; i++){
boolean[] flag = new boolean[9];
for(int j = 0; j < 9; j++){
int val = board[i][j] - 49;
if(board[i][j] == '.'){
continue;
} else if (flag[val] == true){
return false;
}else{
flag[val] = true;
}
}
}
for(int i = 0; i < 9; i++){
boolean[] flag = new boolean[9];
for(int j = 0; j < 9; j++){
int val = board[j][i] - 49;
if(board[j][i] == '.'){
continue;
} else if (flag[val] == true){
return false;
}else{
flag[val] = true;
}
}
}
for(int i = 0; i <= 6; i += 3){
for(int j = 0; j <=6; j += 3){
boolean[] flag = new boolean[9];
for(int m = i; m < i+3; m++){
for(int n = j; n < j+3; n++){
int val = board[m][n] - 49;
if(board[m][n] == '.'){
continue;
}else if(flag[val] == true){
return false;
}else{
flag[val] = true;
}
}
}
}
}
return true;
}
public bool SudoKuVerfier(int[,] ip)
{
int i = 0;
int j = 0;
int m = 0;
int rowlen = ip.GetLength(0);
int collen = ip.GetLength(1);
List<int> lst = new List<int>();
while (i < rowlen && j < collen)
{
if (i > 0)
{
m = i - 1;
while (m >= 0)
{
if (!lst.Contains(ip[m, j]))
{
lst.Add(ip[m, j]);
}
else
{
return false;
}
m--;
}
m = i;
while (m < rowlen)
{
if (!lst.Contains(ip[m, j]))
{
lst.Add(ip[m, j]);
}
else
{ return false; }
m++;
}
m = 0;
lst.Clear();
}
if (j > 0)
{
m = j - 1;
while (m >= 0)
{
if (!lst.Contains(ip[i, m]))
{
lst.Add(ip[i, m]);
}
else { return false; }
m--;
}
m = j;
while (m < collen)
{
if (!lst.Contains(ip[i, m]))
{
lst.Add(ip[i, m]);
}
else { return false; }
m++;
}
m = 0;
lst.Clear();
}
i++;
j++;
}
return true;
}
Create one long string initialized with null characters. The first 81 characters represent 9 rows. The next 81 characters represent 9 columns and the last 81 characters represent the 9 3X3 cubes. As we read in each digit we populate the three locations in the string. The expectation is that at the end of input the string will be filled with X. If it isn't completely filled then the solution is not valid.
#include "stdafx.h"
#include <string>
#include <iostream>
const int nMaskSize = 9 * 9 * 3 + 1;
int _tmain(int argc, _TCHAR* argv[])
{
char arrMask [nMaskSize];
memset(arrMask, 0, nMaskSize);
for (int r = 0; r < 9; r++)
{
for (int c = 0; c < 9; c++)
{
char cInput = 0;
while ((cInput < '1') || (cInput > '9'))
std::cin >> cInput;
int nInVal = cInput - '0';
arrMask[r * 9 + nInVal - 1] = 'X';
arrMask[81 + c * 9 + nInVal - 1] = 'X';
arrMask[162 + ((int)(r / 3)) * 27 + ((int)(c / 3)) * 9 + nInVal - 1] = 'X';
}
}
if (strlen(arrMask) == (nMaskSize - 1))
std::cout << "Solution is valid";
else
std::cout << "Solution is not valid";
return 0;
}
I think this solution will be much easier and simpler.
As the formula to find the sum of consecutive n numbers is [(n(n + 1) )/ 2]
the sum of numbers from 1 to 9 is 45.
So in my approach I add each of the n rows and check if the sum is less than 45 or not if there is a row whose sum is less that 45 than the algorithm stops and I output the row number as the error row if all the rows add upto 45 then I add each of the columns separately if the sum is less than 45 you stop and return with the column number (or false as exit status) else if all the columns also add upto 45 then exit as null (or true as success).
In addition to this, we can further enhance the solution as follows so that any malicious user can't enter fake numbers to add them to 45 and pass the check.
1.) If we find a row or a column whose sum is less than 45 or more than 45 then we can iterate through the elements of the array and find out the missing/duplicated element.
2.) if all the rows and columns add upto 45, then we can use this approach:
Hashtable<Integer,Integer> count = new Hashtable <Integer,Integer>();
iterate through all the elements and add them to the hashtable if the element doesn't exist then add as
count.put(element,1);
if the element exists then add as
count.put(element,count.get(element)+1));
Once all the elements are inside the hashtable then iterate through all the hash keys and check if the count == 9 or not, if not then STOP and output as FAILURE else SUCCESS, also if any element is higher than 9 or less than 1 than again you STOP and return FAILURE. The hashtable keySet MUST HAVE all the numbers between 1 to 9 and hence no solution like 555 555 555 is acceptable.
Running time analysis:
To sum up all the rows will take constant time O(c1)
To sum up all the columns will again take constant time O(c2)
now if we were to go further even then
iterating through all the elements inside the sudoku will take constant time O(c3) and hashtable operation is O(1) time (assuming no one over thinks the problems to implement a superior hash function :P ).
so the total is: O(c1) + O(c2) + O(c3) + (constant time to access hash table entries) = linear time.
Use a test array to determine if dataset is correct, or results together
#include <iostream>
using namespace std;
bool isSetComplete(int set, int data[9][9])
{
bool test[3][9] = { false };
int count[3] = { 0 };
int blockx = (set % 3) * 3;
int blocky = (set / 3) * 3;
for (int x = 0; x < 9; x++)
{
int val = data[set][x] - 1; // Test Row
if (!test[0][val])
{
test[0][val] = true;
count[0]++;
}
val = data[x][set] - 1; // Test Col
if (!test[1][val])
{
test[1][val] = true;
count[1]++;
}
int curx = blockx + (x % 3);
int cury = blocky + (x / 3);
val = data[curx][cury] - 1; // Test Block
if (!test[2][val])
{
test[2][val] = true;
count[2]++;
}
}
return (count[0] == 9 && count[1] == 9 && count[2] == 9);
}
int main()
{
int dataset[9][9] = { {2,4,8,3,9,5,7,1,6}, {5,7,1,6,2,8,3,4,9}, {9,3,6,7,4,1,5,8,2},
{6,8,2,5,3,9,1,7,4}, {3,5,9,1,7,4,6,2,8}, {7,1,4,8,6,2,9,5,3},
{8,6,3,4,1,7,2,9,5}, {1,9,5,2,8,6,4,3,7}, {4,2,7,9,5,3,8,6,1} };
bool isFail = false;
for (int x = 0; x < 9; x++)
{
isFail |= !isSetComplete(x, dataset);
}
if (isFail)
cout << "Failure" << endl;
else
cout << "Success" << endl;
return 0;
}
I have a simpler solution, create 2 x 9 strings
one per row and one per column
e.g. for the given suduko
first row will become "248395716"
first column string will be "259637814"
Once we have these strings, we need to prove that these strings are anagrams of "123456789"
For that simply sort these strings and compare them against "123456789", if all of them matches we have a valid solution.
I believe that we don't need to verify the box constraints, row and column should take care of it indirectly.
My solution is to check sum of all rows, all columns, all 3*3 block to match 45. If one of them did not match , then the solution is wrong.
Checking only the sum might be wrong because you might miss cases where there is 2 and 2 instead of 1 and 3.
For example: 2,2,2,4,5,6,7,8,9. in this case you will get the sum correctly but you should report that it was wrong.
I got little stuck at the interview and I couldn't get the right answer. After I hang out the phone, my mind just relaxed and cleared out and the solution just came to my mind and I could code it in 10-15min .... Too late I think.
Recomendation: Take a deep breath, relax and DO NOT GET NERVOUS!!! Interviews are not that hard ( when you prepare )
cheers,
- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014Axel