Google Interview Question for SDE-2s


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a non brute force solution

public static void Print()
{
	var board = new int[4, 4];
	var solutions = GetSolutions(board, 0, 0);
	Console.WriteLine(solutions.Count);
}

public static List<int[,]> GetSolutions(int[,] board, int x, int y)
{
	var res = new List<int[,]>();
	if (y > 3)
	{
		res.Add(board);
		return res;
	}
	var options = GetOptions(board, x, y);
	int newX = x == 3 ? 0 : x+1;
	int newY = x == 3 ? y+1 : y;
	foreach (var number in options)
	{
		var newBoard = board.Clone() as int[,];
		newBoard[x, y] = number;
		res.AddRange(GetSolutions(newBoard, newX, newY));
	}
	return res;
}

private static List<int> GetOptions(int[,] board, int x, int y)
{
	var options = new List<int>() { 1, 2, 3, 4 };
	for (int i = 0; i < x; i++)
	{
		var val = board[i, y];
		if (options.Contains(val))
		{
			options.Remove(val);
		}
	}

	for (int i = 0; i < y; i++)
	{
		var val = board[x, i];
		if (options.Contains(val))
		{
			options.Remove(val);
		}
	}
	var xx = x / 2;
	var yy = y / 2;
	for (int i = xx*2; i < xx*2+2; i++)
	{
		for (int j = yy*2; j < yy*2+2; j++)
		{
			var val = board[i, j];
			if (options.Contains(val))
			{
				options.Remove(val);
			}
		}
	}
	return options;
}

- Asaf January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a shitty brute-force solution with hardcoded numbers (python 2)

ideone.com/9QUxd3

{{

import math

def is_compatible(p1, p2, vertical=True, cache={}):
if (p1, p2, vertical) in cache:
return cache[(p1, p2, vertical)]
perm1 = index_to_permutation(p1, 4)
perm2 = index_to_permutation(p2, 4)
box1 = [perm1[:2], perm1[2:]]
box2 = [perm2[:2], perm2[2:]]
if vertical:
box = box1 + box2
else:
box = [b1 + b2 for (b1, b2) in zip(box1, box2)]
rows = len(box)
cols = len(box[0])
compatible = True
for r in xrange(rows):
if len(list(set(box[r]))) != cols:
compatible = False
break
else:
for c in xrange(cols):
if len(list(set(box[i][c] for i in xrange(rows)))) != rows:
compatible = False
break
cache[(p1, p2, vertical)] = compatible
return compatible


def index_to_permutation(p, size):
numbers = range(size)
result = []
for i in xrange(size):
if i < size - 1:
order = int(math.factorial(size - i - 1))
index = p / order
p -= index * order
else:
index = 0
result.append(numbers[index])
del numbers[index]
return result

def print_solution(a, b, c, d):
box = [[a, b], [c, d]]
matrix = [[0] * 4 for i in xrange(4)]
for i in xrange(2):
for j in xrange(2):
sub_box = index_to_permutation(box[i][j], 4)
for ii in xrange(2):
for jj in xrange(2):
matrix[i * 2 + ii][j * 2 + jj] = sub_box[ii * 2 + jj]
for row in matrix:
print row
print '#' * 80

def main():
solutions = []
for a11 in xrange(24):
for a12 in xrange(24):
if not is_compatible(a11, a12, False):
continue
for a21 in xrange(24):
if not is_compatible(a11, a21, True):
continue
for a22 in xrange(24):
if not is_compatible(a22, a12, True):
continue
if not is_compatible(a22, a21, False):
continue
solutions.append([a11, a12, a21, a22])

for solution in solutions:
print_solution(*solution)

print "Total %d solutions" % len(solutions)

if __name__ == '__main__':
main()

}}

- john January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

import math

def is_compatible(p1, p2, vertical=True, cache={}):
    if (p1, p2, vertical) in cache:
        return cache[(p1, p2, vertical)]
    perm1 = index_to_permutation(p1, 4)
    perm2 = index_to_permutation(p2, 4)
    box1 = [perm1[:2], perm1[2:]]
    box2 = [perm2[:2], perm2[2:]]
    if vertical:
        box = box1 + box2
    else:
        box = [b1 + b2 for (b1, b2) in zip(box1, box2)]
    rows = len(box)
    cols = len(box[0])
    compatible = True
    for r in xrange(rows):
        if len(list(set(box[r]))) != cols:
            compatible = False
            break
    else:
        for c in xrange(cols):
            if len(list(set(box[i][c] for i in xrange(rows)))) != rows:
                compatible = False
                break
    cache[(p1, p2, vertical)] = compatible
    return compatible


def index_to_permutation(p, size):
    numbers = range(size)
    result = []
    for i in xrange(size):
        if i < size - 1:
            order = int(math.factorial(size - i - 1))
            index = p / order
            p -= index * order
        else:
            index = 0
        result.append(numbers[index])
        del numbers[index]
    return result

def print_solution(a, b, c, d):
    box = [[a, b], [c, d]]
    matrix = [[0] * 4 for i in xrange(4)]
    for i in xrange(2):
        for j in xrange(2):
            sub_box = index_to_permutation(box[i][j], 4)
            for ii in xrange(2):
                for jj in xrange(2):
                    matrix[i * 2 + ii][j * 2 + jj] = sub_box[ii * 2 + jj]
    for row in matrix:
        print row
    print '#' * 80

def main():
    solutions = []
    for a11 in xrange(24):
        for a12 in xrange(24):
            if not is_compatible(a11, a12, False):
                continue
            for a21 in xrange(24):
                if not is_compatible(a11, a21, True):
                    continue
                for a22 in xrange(24):
                    if not is_compatible(a22, a12, True):
                        continue
                    if not is_compatible(a22, a21, False):
                        continue
                    solutions.append([a11, a12, a21, a22])

    for solution in solutions:
        print_solution(*solution)

    print "Total %d solutions" % len(solutions)

if __name__ == '__main__':
    main()

- aww January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

so we represent each square as a permutation (of which there are 1 * 2 * 3 * 4 = 24) the uppert left square may have each permutation from 1-st to 24-th, the left bottom square must be compatible with upper left square, the same for right top square. And finally the bottom right square is taken to be compatible with left bottom and right top squares.

- Anonymous January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can't figure out anything else but to do a simple "brute force" with some minor optimizations. Undebugged solution in python 2:

import itertools

def isValid(l):
	check = lambda x: len(set(x)) == 4 and min(x) == 1 and max(x) == 4
	assert(all(check(x) for x in l))
	assert(all(check(x) for x in zip(*l)))
	squares = [[] for x in range(4)]
	for idx1, row in enumerate(l):
		for idx2, col in enumerate(row):
			squares[2*(idx1//2) + idx2].append(col)
	assert(all(check(x) for x in squares))

def getValidSolutionCount():
	validPermutations = list(itertools.permutations((1,2,3,4)))
	tot = 0
	for p in itertools.product([validPermutations]*4):
		try:
			isValid(p)
			tot += 1
		except:
			pass
	return tot

- Anonymous January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The obvious solution is the brute force one having (4^16)*48 steps (48 steps to check it). It can be reduced by using permutations of 1234 on each row. The total number of steps will be (4!*4!*4!*4!)*32 (32 steps to check it, since we don't need to check each row now).
This can be easily implemented in a dfs manner.

public void dfs(int r, int c, int[][] map, boolean[] values) {
		if (r == 4 && c == 0) {

			check(map);
			return;
		}

		for (int i = 0; i < 4; i++) {
			if (!values[i]) {
				map[r][c] = i + 1;
				values[i] = true;
				if (c == 3) {
					dfs(r + 1, 0, map, new boolean[4]);
				} else {
					dfs(r, c + 1, map, values);
				}
				values[i] = false;
			}
		}

	}

The interesting thing would be the check method. It can be written in a very clean way for each of the small 2X2 squares.
Here's the complete code. Works perfectly :)

import java.util.ArrayList;

public class Impromptu {
	ArrayList<int[][]> list = new ArrayList<int[][]>();
	int[] dx = { 0, 1, 1, 0 };
	int[] dy = { 0, 0, 1, 1 };

	public void dfs(int r, int c, int[][] map, boolean[] values) {
		if (r == 4 && c == 0) {

			check(map);
			return;
		}

		for (int i = 0; i < 4; i++) {
			if (!values[i]) {
				map[r][c] = i + 1;
				values[i] = true;
				if (c == 3) {
					dfs(r + 1, 0, map, new boolean[4]);
				} else {
					dfs(r, c + 1, map, values);
				}
				values[i] = false;
			}
		}

	}

	public int[][] clone(int[][] map) {
		int[][] ret = new int[4][4];
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				ret[i][j] = map[i][j];
			}
		}

		return ret;
	}

	public void print(int[][] map) {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println("");
		}

		System.out.println("------------------");
	}

	public boolean check(int[][] map) {
		int r = 0, c = 0;
		for (int i = 0; i < 4; i++) {
			int nr = r + 2 * dy[i];
			int nc = c + 2 * dx[i];
			boolean[] vals = new boolean[5];
			for (int j = 0; j < 4; j++) {
				int ncc = nc + dx[j];
				int nrr = nr + dy[j];
				if (vals[map[nrr][ncc]]) {
					return false;
				} else
					vals[map[nrr][ncc]] = true;
			}
		}

		for (int j = 0; j < 4; j++) {
			boolean vals[] = new boolean[5];
			for (int i = 0; i < 4; i++) {
				if (vals[map[i][j]]) {
					return false;
				} else
					vals[map[i][j]] = true;
			}
		}

		list.add(clone(map));
		print(map);
		return true;
	}

	public static void main(String args[]) {

		new Impromptu().dfs(0, 0, new int[4][4], new boolean[4]);
	}
}

- renegade403 January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my Code in C++. Have a look.

#include<iostream>
#include<stdio.h>
#define MAX 4
using namespace std;
bool NotInSqr(int mat[][MAX],int i,int j,int k,int n)
{
int srow=0,scol=0;
if(i>=0 && i<n/2)
srow=0;
else
srow=n/2;
if(j>=0 && j<n/2)
scol=0;
else
scol=n/2;
for(i=srow;i<srow+2;i++)
{
for(j=scol;j<scol+2;j++)
{
if(mat[i][j]==k)
return false;
}
}
return true;
}
bool NotInCol(int mat[][MAX],int i,int j,int k,int n)
{
int r;
for(r=0;r<i;r++)
{
if(mat[r][j]==k)
return false;
}
return true;
}
bool NotInRow(int mat[][MAX],int i,int j,int k,int n)
{
int r;
for(r=0;r<j;r++)
{
if(mat[i][r]==k)
return false;
}
return true;
}
void sudoku(int mat[][MAX],int i,int j,int *cnt,int n)
{
if(i>n || j>n)
return;
else if(i==n && j==0)
{
(*cnt)++;
int i1,j1;
for(i1=0;i1<n;i1++)
{
cout<<"\n";
for(j1=0;j1<n;j1++)
cout<<mat[i1][j1]<<" ";
}
cout<<"\n\n";
return;
}
else if(i<n && j<n)
{
int k;
for(k=1;k<5;k++)
{
if(NotInRow(mat,i,j,k,n) && NotInCol(mat,i,j,k,n) && NotInSqr(mat,i,j,k,n))
{
mat[i][j]=k;
sudoku(mat,(i+(j+1)/n),(j+1)%n,cnt,n);
mat[i][j]=0;

}
}
}
}
int main()
{
int n=4,cnt=0,mat[MAX][MAX];
memset(mat,0,sizeof(mat));
sudoku(mat,0,0,&cnt,n);
cout<<"No. of solutions are "<<cnt<<"\n";
return 0;
}

- aleena January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The brutal force solution is O(N^(N^2)) I think, , here N is the length/width of the matrix.

If you use some knowledge from combination, which means choosing 2 different integers from 4 and interchange them, then you can optimize the process to be O(N^6). And if you use hashtable, then you can make it O(N^4).

- jasonust4 January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The entire solution fits into 32 bit int (every number is 2 bits). The row fits into one byte. Only 24 (out of 256) possible byte values a valid rows. Rows cannot repeat in the same solution, so permutate 4 different rows and note wich permutations are valid solutions. That is 24x23x22x21 about quarter of a million permutations.

Now, we can do better than that. Let's say rows are conflicting if at least one of the numbers is the same at the same positions, such as:


1234
and
3241

are conflicting because 2 at second position is the same.

1234
and
3421

are not conflicting.

So, when we do the permutations, when we loop through second row and on, we can select rows that are not conflicting to the previously selected. This will enourmously reduce amount of permutations and in addition we would have to validate only subsquares.

- CT January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my java solution. it may need optimization of course :

package test;

import java.util.ArrayList;
import java.util.List;

public class SuDoku {

	public static void main(String[] args) {

		printSuDoku();

	}

	private static void printSuDoku() {
		int total = 0;
		int[][] arr = new int[][]{{1,2},{3,4}};
		List<int[][]> allComb = findAllCombinations(arr);
		List<int[]> allCombIndex = findAllCombIndex(allComb.size() -1);
		for(int i = 0; i< allCombIndex.size() ; i++){
			int[][] result = generatex4(allComb.get(allCombIndex.get(i)[0]), allComb.get(allCombIndex.get(i)[1]), allComb.get(allCombIndex.get(i)[2]), allComb.get(allCombIndex.get(i)[3]));
			if(isValidRowColumnx4(result)){
				printx4(result);
				System.out.println("----------");
				total ++;			
			}
		}
		System.out.println("total combinations : " + total);
	}

	private static void printx4(int[][] arr){
		System.out.println(arr[0][0] +"|"+arr[0][1] + "|"+arr[0][2] + "|"+arr[0][3] + "|");
		System.out.println(arr[1][0] +"|"+arr[1][1] + "|"+arr[1][2] + "|"+arr[1][3] + "|");
		System.out.println(arr[2][0] +"|"+arr[2][1] + "|"+arr[2][2] + "|"+arr[2][3] + "|");
		System.out.println(arr[3][0] +"|"+arr[3][1] + "|"+arr[3][2] + "|"+arr[3][3] + "|");
	}
	
	private static int[][] generatex4(int[][] arr1,int[][] arr2,int[][] arr3,int[][] arr4){
		int[][] result = new int[4][4];
		locatex4(result, arr1, 0, 0);
		locatex4(result, arr2, 2, 0);
		locatex4(result, arr3, 0, 2);
		locatex4(result, arr4, 2, 2);
		
		
		return result;
	}
	
	
	private static void locatex4(int[][] result, int[][] arr, int x,int y){
		result[x][y] = arr[0][0];
		result[x][y+1] = arr[0][1];
		result[x+1][y] = arr[1][0];
		result[x+1][y+1] = arr[1][1];
	}
	
	private static List<int[][]> findAllCombinations(int[][] arr){
		List<int[][]> result =  new ArrayList<int[][]>();
		
		int[] intArr = new int[]{arr[0][0], arr[0][1], arr[1][0], arr[1][1]};
		
		for(int i = 0; i<4 ; i++){
			for(int j = 0; j<4; j++){
				for(int k = 0; k<4; k++){
					for(int m = 0; m<4; m++){
						if(i!=j && i!=k && i!= m && j != k && j!=m && k!= m){
							result.add(new int[][]{{intArr[i],intArr[j]},{intArr[k],intArr[m]}});
						}						
					}
				}
			}
		}
		
		
		return result;
	}

	private static List<int[]> findAllCombIndex(int index){
		
		List<int[]> result =  new ArrayList<int[]>();
		
		for(int i = 0; i<index ; i++){
			for(int j = 0; j<index; j++){
				for(int k = 0; k<index; k++){
					for(int m = 0; m<index; m++){
						if(i!=j && i!=k && i!= m && j != k && j!=m && k!= m){
							result.add(new int[]{i,j,k,m});
						}						
					}
				}
			}
		}
		
		return result;
	}
	
	private static boolean isValidRowColumnx4(int[][] arr){
		boolean result = false;
		
		List<int[]> rowList = new ArrayList<int[]>();
		List<int[]> columnList = new ArrayList<int[]>();
		for(int i = 0; i< arr.length; i++){
			rowList.add(new int[]{arr[i][0],arr[i][1],arr[i][2],arr[i][3]});
		}
		for(int i = 0; i< arr.length; i++){
			columnList.add(new int[]{arr[0][i],arr[1][i],arr[2][i],arr[3][i]});
		}
		
		for(int i = 0; i<rowList.size() ; i++){
			if(isValid(rowList.get(i)) && isValid(columnList.get(i))){
				result = true;
			}else{
				result= false;
				break;
			}
		}
		
		return result;
	}

	private static boolean isValid(int[] arr) {
		boolean b1 = false,b2 = false,b3 = false,b4 = false;
		for(int i = 0; i< arr.length; i++){
			switch(arr[i]){
			    case 1 :
			    	b1 = true;
			    	break;
			    case 2 :
			    	b2 = true;
			    	break; 
			    case 3 :
			    	b3 = true;
			    	break;
				case 4 :
					b4 = true;
					break; 
			}
		}
		return b1 && b2 && b3 && b4;
	}



}

- Anonymous January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this way, we have 220 solutions

- Anonymous January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Aren't there 4! * 2 * 2 * 2 * 2 many possible solutions?

Consider the left top square. To fill in the square with a permutation of {1,2,3,4},
there are 4! possibilities. Determining the square, each row of the square on its right and
each column of the square on its bottom only have two possible numbers so each of them has the freedom of 2. Once you determine those three squares, the last square would have no freedom. Thus, there are 4! * 2 * 2 * 2 * 2 possible solutions.

To print all of them, use, e.g., next_permutation function with array [1,2,3,4] to fill the first square, and filling last of the square as described.

4! * 2 * 2 * 2 * 2 is just 384 so, simply store them using 384 * 16 * 4 bytes.

- Anonymous January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I was thinking along the same lines until the following counterexample. If the numbers are arranged as follows then it becomes impossible to fill the lower fourth square because both 4 and 1 must go in the lower right, which is clearly impossible.
| 1 2 | 4 3 |
| 3 4 | 1 2 |
------------ |
| 4 1 | * * |
| * * | * * |
This means we have to somehow take into account that after filling in the left top square, the top right square cannot have column with the same numbers as any row of the lower left square.

Also the following board should be impossible.
| 1 2 | 3 4 |
| 3 4 | 2 1 |
------------ |
| * * | * * |
| 4 1| * * |
In both of these cases it looks like there are two ways to fill in the lower left square rather than four, so this means that the total number of solutions should be 4!*2*4 + 4!*2*2 = 4!*2*6 = 288 instead of 384.

- Michael January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Right. I missed that point. Thanks Michael.

- Anonymous January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry, I did not get it.
If 2x2 sudoku, should be 8 possibilities.
If 4x4 sudoku, should be 288.

2x2: 
 |  1 2  |  3  4
 |  3 4  |  1  2
 ---------------
 |  4 1  |  2  3
 |  2 3  |  4  1
 
  AB  AB  BA  BA  CD  CD  DC  DC 
  CD  DC  CD  DC  AB  BA  AB  BA

- biolxj12 February 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have found 240 slutions with the following code. I thought that for the first row (top) we have 4! possibility and according to this elements we have 2 possibility for the first two columns of second row. Then, we have another 2 possibility for the last two places of second row. Here is the important point!! We should choose first two elements of the third row according to the following rules;

1 2 X Y
3 4 Z T HERE if (X == D && Z == F) || (X == F && Z == D) sudoku cannot be D FK L solved AND if there is no common element, again it cannot be solved
M NO P

Here is my code. If there is a mistaken point, please leave a comment and let me know.

import java.util.ArrayList;


public class Q3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ArrayList<String> seqs = new ArrayList<String>();
		String bos = "";
		String dolu = "1234";
		findSubSeqs(seqs, bos, dolu);
		ArrayList<String[]> sudokus = findAlternatives(seqs);
		for (int a = 0;a < sudokus.size(); a++){
			for (int b = 0; b < 4;b++){
				System.out.println(sudokus.get(0)[b]);
			}
			System.out.println("--------------------");
		}
		System.out.println(sudokus.size());
	}
	public static void findSubSeqs(ArrayList<String> seqs, String bos, String dolu){
		if (dolu.length()==0){
			seqs.add(bos);
		}
		else{
			for (int a = 0; a < dolu.length();a++){
				String ch = dolu.charAt(a) + "";
				bos += dolu.charAt(a) + "";
				findSubSeqs(seqs, bos, dolu.replaceFirst(ch, ""));
				bos = bos.substring(0, bos.length()-1);
			}
		}
	}
	public static ArrayList<String[]> findAlternatives(ArrayList<String> seqs){
		ArrayList<String[]> arr = new ArrayList<String[]>();
		for (int a = 0; a < seqs.size();a++){
			String[] temp = new String[4];
			temp[0] = seqs.get(a);
			for (int b = 0; b < 2;b++){
				if (b == 0){
					temp[1] = seqs.get(a).charAt(2) + "";
					temp[1] += seqs.get(a).charAt(3) + "";
				}
				else{
					temp[1] = seqs.get(a).charAt(3) + "";
					temp[1] += seqs.get(a).charAt(2) + "";
				}
					for (int c = 0; c < 2; c++){
						temp[1] = temp[1].substring(0,2);
						if (c == 0){
							temp[1] += seqs.get(a).charAt(0) + "";
							temp[1] += seqs.get(a).charAt(1) + "";
						}
						else{
							temp[1] += seqs.get(a).charAt(1) + "";
							temp[1] += seqs.get(a).charAt(0) + "";
						}
						for (int d = 0; d < 2; d++){
							int f = Integer.parseInt(temp[0].substring(0, 1));
							int s = Integer.parseInt(temp[1].substring(0,1));
							int [] ds = new int[2];
							int cs = 0;
							for (int count = 1; count < 5; count++){
								if (f != count && s != count){
									ds[cs++] = count;
								}
							}
							if (d == 0){
								temp[2] = ds[0] + "";
							}
							else{
								temp[2] = ds[1] + "";
							}
							for (int e = 0; e < 2; e++){
								temp[2] = temp[2].substring(0,1);
								if (e == 0){
									temp[2] += f;
									
								}
								else
									temp[2] += s;
								if (((temp[2].charAt(0) + "").equals(temp[0].charAt(2) + "") && (temp[2].charAt(1)+"").equals(temp[1].charAt(2) + "")) || ((temp[2].charAt(0) + "").equals(temp[1].charAt(2) + "") && (temp[2].charAt(1) + "").equals(temp[0].charAt(2) + ""))  ){
									break;
								}
								if ((!(temp[2].charAt(0) + "").equals(temp[0].charAt(2) + "") && !(temp[2].charAt(1)+"").equals(temp[1].charAt(2) + "")) && (!(temp[2].charAt(0) + "").equals(temp[1].charAt(2) + "") && !(temp[2].charAt(1) + "").equals(temp[0].charAt(2) + ""))){
									break;
								}
								for (int g = 1;g < 5; g++){
									if (g != Integer.parseInt(temp[2].substring(0,1)) && g != Integer.parseInt(temp[2].substring(1,2)) && g != Integer.parseInt(temp[1].substring(2,3)) &&g != Integer.parseInt(temp[0].substring(2,3)) ){
										temp[2] += g+ "";
									}
								}
								for (int g = 1;g < 5; g++){
									if (g != Integer.parseInt(temp[2].substring(0,1)) && g != Integer.parseInt(temp[2].substring(1,2)) && g != Integer.parseInt(temp[2].substring(2,3))){
										temp[2] += g+ "";
									}
								}
								temp[3] = "";
								for (int g = 0;g <4;g++){
									
									for (int h = 1;h < 5;h++){
										if (h != Integer.parseInt(temp[0].substring(g,g+1)) && h != Integer.parseInt(temp[1].substring(g,g+1)) && h != Integer.parseInt(temp[2].substring(g,g+1))){
											temp[3] += h+ "";
										}	
									}
									
								}
								arr.add(temp);
							}
							
						}
					}
			}
		}
		return arr;
		
	}

}

- nonameno January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

void backtrack(int[][4], int, int) ;

int main() {
	int a[4][4];
	backtrack(a,0,0);
}

void backtrack(int a[][4], int i, int j) {
	if(i==4) {
		printf("\n");
		for(int i=0;i<4;i++) {
			for(int j=0;j<4;j++) {
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
	}
	for(int k=1;k<=4;k++) {
		int x;
		for(x=0;x<i && a[x][j]!=k;x++);
		if(x<i)
			continue;
		for(x=0;x<j && a[i][x]!=k;x++);
		if(x<j)
			continue;
		if(i%2) {
			if(j%2) {
				if(a[i-1][j-1]==k)
					continue;
			}
			else {
				if(a[i-1][j+1]==k)
					continue;
			}
		}
		a[i][j]=k;
		backtrack(a,j==3?i+1:i,(j+1)%4);		
	}
}

- hugakkahuga January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my take to this:

import java.util.List;
import java.util.LinkedList;

class Sudoku2X2 {
	public static void main (String[] args) {
		int[][] array = {{0, 0, 0, 0}, {3, 0, 4, 0}, {0, 2, 0, 0}, {0, 0, 0, 0}};
		SudokuBoard board = new SudokuBoard(array);
		if (!board.isBoardValid()) {
			System.err.println("The input board is not valid. Exiting..");
			System.exit(1);
		}
		List<SudokuBoard> boards = getAllValidBoards(0, 0, board);
		System.out.println("Number of boards = " + boards.size());
		for (int i = 0; i < boards.size(); i++) {
			System.out.println("Board " + i + ":");
			boards.get(i).print();
		}
	}

	public static List<SudokuBoard> getAllValidBoards(int x, int y, SudokuBoard board) {
		LinkedList<SudokuBoard> boards = new LinkedList<SudokuBoard>();
		if (x >= SudokuBoard.SIZE || y >= SudokuBoard.SIZE) {
			boards.add(board);
		}
		else {
			if (!board.isEmpty(x, y)) {
				int x1 = x + 1;
				int y1 = y;
				if (x1 == SudokuBoard.SIZE) {
					x1 = 0;
					y1 ++;
				}
				boards.addAll(getAllValidBoards(x1, y1, board));
			}
			else {
				for (int i = 0; i <= SudokuBoard.SIZE; i++) {
					if (board.isMoveValid(x, y, i)) {
						SudokuBoard tempBoard = board.clone();
						tempBoard.move(x, y, i);
						int x1 = x + 1;
						int y1 = y;
						if (x1 == SudokuBoard.SIZE) {
							x1 = 0;
							y1 ++;
						}
						boards.addAll(getAllValidBoards(x1, y1, tempBoard));
					}
				}
			} 
		}
		return boards;
	}

}

class SudokuBoard {
	public static final int SIZE = 4;

	private int board[][];
	private int validator[];

	public SudokuBoard() {
		board = new int[SIZE][SIZE];
		validator = new int[SIZE];
	}

	public SudokuBoard(int[][] array) {
		board = array;
		validator = new int[SIZE];
	}

	public boolean isBoardValid() {
		for (int i = 0; i < SIZE; i++) {
			if (!validateRow(i) || !validateColumn(i) || !validateSquare(i%2, i/2)) {
				return false;
			}
		}
		return true;
	}

	public boolean isEmpty(int x, int y) {
		return (board[x][y] == 0);
	}

	public boolean isBoardComplete() {
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				if (board[i][j] == 0) {
					return false;
				}
			}
		}
		return true;
	}

	public void move(int x, int y, int move) {
		board[x][y] = move;
	}

	public boolean isMoveValid(int x, int y, int move) {
		if (x < 0 || y < 0 || move < 1 || x >= SIZE || y >= SIZE || move > SIZE) {
			return false;
		}
		else if (board[x][y] != 0) {
			return false;
		}

		board[x][y] = move;

		if (validateRow(x) && validateColumn(y) && validateSquare(x/2, y/2)) {
			board[x][y] = 0;
			return true;
		}
		board[x][y] = 0;
		return false;
	}

	private boolean validateRow(int row) {
		if (row < 0 || row >= SIZE) {
			return false;
		}
		resetValidator();
		for (int i = 0; i < SIZE; i++) {
			int element = board[row][i];
			if (element == 0) {
				continue;
			}
			if (validator[element - 1] != 0) {
				return false;
			}
			else {
				validator[element - 1] = 1;
			}
		}
		return true;
	}

	private void resetValidator() {
		for (int i = 0; i < SIZE; i++) {
			validator[i] = 0;
		}
	}

	private boolean validateColumn(int column) {
		if (column < 0 || column >= SIZE) {
			return false;
		}
		resetValidator();
		for (int i = 0; i < SIZE; i++) {
			int element = board[i][column];
			if (element == 0) {
				continue;
			}
			if (validator[element - 1] != 0) {
				return false;
			}
			else {
				validator[element - 1] = 1;
			}
		}
		return true;
	}

	private boolean validateSquare(int sqRow, int sqColumn) {
		if (sqRow < 0 || sqColumn < 0 || sqRow >= 2 || sqColumn >= 2) {
			return false;
		}
		int startX = sqRow * 2; 
		int startY = sqColumn * 2;
		resetValidator();
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				int element = board[i][j];
				if (element == 0) {
					continue;
				}
				if (validator[element - 1] != 0) {
					return false;
				}
				else {
					validator[element - 1] = 1;
				}
			}
		}
		return true;
	}

	public SudokuBoard clone() {
		int board[][] = new int[SIZE][SIZE];
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				board[i][j] = this.board[i][j];
			}
		}
		return new SudokuBoard(board);
	}

	public void print() {
		for (int i = 0; i < SIZE; i++) {
			for (int j = 0; j < SIZE; j++) {
				System.out.print(board[i][j] + " ");
			}
			System.out.println();
		}
	}
}

- Sumeet Singhal January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import copy

def findPossibleNums(grid, index):
    [i,j] = index
    possibleNums = [1,2,3,4]

    for x in range(i):
        num = grid[x][j]
        if num in possibleNums:
            possibleNums.remove(num)


    for y in range(j):
        num = grid[i][y]
        if num in possibleNums:
            possibleNums.remove(num)


    x = i%2
    y = j%2

    if x == 1:
        if grid[i-1][j-y]in possibleNums:
            possibleNums.remove(grid[i-1][j-y])
        if grid[i-1][j-y+1] in possibleNums:
            possibleNums.remove(grid[i-1][j-y+1])

    if y == 1:
        if grid[i][j-1] in possibleNums:
            possibleNums.remove(grid[i][j-1])

    return possibleNums


def find2Combo():
    twoXtwoGrid = [[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]]
    for i in xrange(4):
        for j in xrange(4):
            tempGridCollection = []

            for grid in twoXtwoGrid:
                possibleNums = findPossibleNums(grid, [i, j])

                for num in possibleNums:
                    tempGrid = copy.deepcopy(grid)
                    tempGrid[i][j] = num
                    tempGridCollection.append(tempGrid)

            twoXtwoGrid = tempGridCollection
    return twoXtwoGrid

- Adi January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a c++ solution using bit operation.

#include <cstdio>

int get(unsigned int sokudo, int index) {
	unsigned int mask1 = 1 << (2 * index), mask2 = 1 << (2 * index + 1);
	return (sokudo & (mask1 | mask2)) >> (2 * index);
}

unsigned int set(unsigned int sokudo, int index, int val) {
	int bit1 = val & 1, bit2 = val >> 1;
	unsigned int mask1 = 1 << (2 * index), mask2 = 1 << (2 * index + 1);
	unsigned int mask3 = bit1 << (2 * index), mask4 = bit2 << (2 * index + 1);
	return sokudo & (~(mask1 | mask2)) | (mask3 | mask4);
}

void print(int sokudo) {
	static int count = 0;
	printf("%d solution:\n", ++count);
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			printf("%d ", get(sokudo, i*4+j));
		}
		printf("\n");
	}
	printf("\n");
}

void dfs(int index, unsigned int sokudo, unsigned int row, unsigned int column, unsigned int block) {
	if (index == 16) {
		print(sokudo);
		return;
	}
	int x = index / 4, y = index % 4;
	for (int i = 0; i < 4; i++) {
		unsigned int mask1 = 1 << (4 * x + i);
		unsigned int mask2 = 1 << (4 * y + i);
		unsigned int mask3 = 1 << (4 * (x/2*2+y/2) + i);
		if ((row & mask1) || (column & mask2) || (block & mask3)) continue;
		sokudo = set(sokudo, index, i);
		row |= mask1, column |= mask2, block |= mask3;
		dfs(index + 1, sokudo, row, column, block);
		row ^= mask1, column ^= mask2, block ^= mask3;
	}
}

int main() {
	dfs(0, 0, 0, 0, 0);
}

- chshda January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is solution using recursion to find all possible puzzles
Give me your thougts

import java.util.ArrayList;

public class SodukoSolutions {

	public static int count = 0;
	public static int fails = 0;
	
	public static void main(String[] args) {

		int[][] board = new int[4][4];
		fillIt(board,0,0);
		System.out.println("Count of solutions: "+count);
		System.out.println("Count of failures: "+fails);

	}
	//Fills boards recursively and counts if the filling was a success or not
	public static void fillIt(int[][]board, int x, int y){
		ArrayList<Integer> pos = getPossibilities(board, x, y);
		int[][] clone = clone(board);
		if(pos.size()==0){
			fails++;
			return;
		}
		for (Integer integer : pos) {
			clone[x][y] = integer;
			if(x==3 && y==3){
				if(checkBoard(clone)){
					printBoard(clone);
					count++;
					return;
				}
				else{
					System.out.println("Failed!");
				}
			}
			if(x==3){
				fillIt(clone,0,y+1);				
			}
			else{
				fillIt(clone,x+1,y);
			}
		}
	}
	public static int[][] clone(int[][] board){
		int[][] ret = new int [4][4];
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				ret[i][j] = board[i][j];
			}
		}
		return ret;
	}
	public static void printBoard(int[][] board){
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				System.out.print(board[i][j]);
			}
			System.out.println();
		}
		System.out.println();
	}
	//Gets all the possibilities for a cell
	public static ArrayList<Integer> getPossibilities(int[][] board,int x,int y){
		ArrayList<Integer> pos = new ArrayList<Integer>();
		pos.add(1);pos.add(2);pos.add(3);pos.add(4);
		//Check rows
		for(int i = 0;i<4;i++){
			if(board[x][i]!=0){
				if(pos.contains(board[x][i])){
					pos.remove(pos.indexOf(board[x][i]));
				}
			}
		}
		//Check Columns
		for(int i = 0;i<4;i++){
			if(board[i][y]!=0){
				if(pos.contains(board[i][y])){
					pos.remove(pos.indexOf(board[i][y]));
				}
			}
		}	
		//Check squares
		int moveX = x-x%2;
		int moveY = y-y%2;
		for(int i=moveX;i<moveX+2;i++){
			for(int j=moveY;j<moveY+2;j++){
				if(board[i][j]!=0){
					if(pos.contains(board[i][j])){
						pos.remove(pos.indexOf(board[i][j]));
					}
				}
			}
		}
		return pos;
	}
	//Not really necessary since the getPossibilities function gets only valid numbers
	public static boolean checkBoard(int[][] board){
		//check rows for duplicates
		for(int i=0;i<4;i++){
			int[] bitMask = {0,0,0,0};
			for(int j=0;j<4;j++){
				if(bitMask[board[i][j]-1]==1){
					return false;
				}
				else{
					bitMask[board[i][j]-1]=1;
				}
			}
		}
		for(int i=0;i<4;i++){
			int[] bitMask = {0,0,0,0};
			for(int j=0;j<4;j++){
				if(bitMask[board[j][i]-1]==1){
					return false;
				}
				else{
					bitMask[board[j][i]-1]=1;
				}
			}
		}
		return true;
		
	}

}

- Anonymous January 26, 2015 | 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