Google Interview Question for Senior Software Development Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 2 vote

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 )

public static boolean validateSudoku(int A[][]){
	        @SuppressWarnings("unchecked")
		Hashtable<Integer,Boolean> rows[] =(Hashtable<Integer,Boolean>[]) new Hashtable<?,?>[9];
                @SuppressWarnings("unchecked")
		Hashtable<Integer,Boolean> columns[] =(Hashtable<Integer,Boolean>[]) new Hashtable<?,?>[9];
                @SuppressWarnings("unchecked")
		Hashtable<Integer,Boolean> blocks[][] =(Hashtable<Integer,Boolean>[][]) new Hashtable<?,?>[3][3];
		for(int r = 0; r < A.length; r++ ){
			for(int c = 0; c < A[r].length; c++){
				int key = A[r][c];

				if(rows[r] != null && rows[r].containsKey(key)){
					return false;
				}else{
					rows[r] = new Hashtable<Integer,Boolean>();
					rows[r].put(key,true);
				}
				if(columns[c] != null && columns[c].containsKey(key)){
					return false;
				}else{
					columns[c] = new Hashtable<Integer,Boolean>();
					columns[c].put(key,true);
				}
				int rk = r / 3;
				int ck = c / 3;
				if(blocks[rk][ck] != null && blocks[rk][ck].containsKey(key)){
					return false;
				}else{
					blocks[rk][ck] = new Hashtable<Integer,Boolean>();
					blocks[rk][ck].put(key,true);
				}
			}
		}
		return true;
	}

cheers,
Axel

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is the missing part.

if ( keey > 9)  return false;

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

key*

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That was a breeze man... how could you miss it?

- Murali Mohan February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Murali Mohan February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Time complexity of my solution is O(n^2) and space complexity is O(1)

- Murali Mohan February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
        }

- bp February 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution with the bits. I think you can also have some sort of sum accumulating ^, for example sum ^=number; Then for i : 1->9 do again sum ^=number and if it is not 0, then some number was missing.

- mbriskar May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Oups/ I forgot to validate values from 0 to 9. not big deal to fix that.
Sorry about that.

Additional to that, I could have fix the size of each hashtable to 10, to save some memory as well.

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- qgbian February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- vivek828 February 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Maurice J. Petrie February 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Sidhu February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- drs April 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Aritra February 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes. but what about the blocks 3x3 ??

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> February 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

.. and, sorting them is slower than adding to / checking for in a hashset.

- JeffD March 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Vinay February 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Amiad February 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there is a repeated case, for other columns or 3*3 block sum won't match.

- Vinay February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sum approach will fail for this case..so only by checking sum is not sufficient

555 555 555
555 555 555
555 555 555

- aviundefined February 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My approach was to add each value to a row and column to a set for each row and column. If the set has 9 elements for each row and column then it is correctly formed. Otherwise there is duplication which will return fewer items for a particular row or column and it won't validate.

- possen February 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My approach was to add each value to a row and column to a set for each row and column. If the set has 9 elements for each row and column then it is correctly formed. Otherwise there is duplication which will return fewer items for a particular row or column and it won't validate.

- possen February 10, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More