Amazon Interview Question Interns
Country: India
Interview Type: In-Person
public class Sudoku {
static boolean checkeer(int [][]arr, int n){
int Rowsum = n*(n+1)/2;
int Colsum = Rowsum;
int finalsum = Colsum;
int RowDuplicate = 0;
int colDuplicate = 0;
int Coldata =0;
int RowData =0;
for(int i = 0; i < n; i++){
RowDuplicate = 0;
RowData = 0;
Rowsum =finalsum;
Colsum = finalsum;
Coldata = 0;
colDuplicate =0;
for(int count =0; count < n; count++ ){
if(arr[i][count] >= 1 && arr[i][count]<=9 && arr[count][i] >=1 && arr[count][i] <= 9){
Rowsum-= arr[i][count];
Colsum -= arr[count][i];
RowData = arr[i][count];
Coldata = arr[count][i];
if(((RowDuplicate & 1 << RowData) == 1)||((colDuplicate & 1 << Coldata) == 1)){
return false;
} else {
RowDuplicate |= 1 << RowData;
colDuplicate |= 1 << Coldata;
}
} else {
return false;
}
}
if(Colsum != 0 || Rowsum != 0){
return false;
}
}
return true;
}
public static void main(String []args){
int[][] sudoko1 ={ {5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9}
};
boolean result = checkeer(sudoko1,9);
System.out.print(result);
}
}
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
bool checkSudoku(unsigned char sudoku[][9])
{
bool tmp[9];
unsigned char ch;
int count = 0;
for(int i=0;i<9;i++){
memset(tmp, false, sizeof(tmp));
for(int j=0;j<9;j++){
ch = sudoku[i][j];
if(tmp[ch-1])
return false;
tmp[ch-1]= true;
}
}
for(int i=0;i<9;i++){
memset(tmp, false, sizeof(tmp));
for(int j=0;j<9;j++){
ch = sudoku[j][i];
if(tmp[ch-1])
return false;
tmp[ch-1]= true;
}
}
for (int i=0;i<9;i=i+3){
for(int j=0;j<9;j=j+3){
memset(tmp, false,sizeof(tmp));
for(int m=i;m<i+3;m++){
for (int n=j;n<j+3;n++){
ch=sudoku[m][n];
if(tmp[ch-1])
return false;
tmp[ch-1]=ch;
}
}
}
}
return true;
}
int main ()
{
unsigned char sudokutest[9][9]={
{5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9}
};
if(checkSudoku(sudokutest))
cout<<"Filled Sudoku is OK"<<endl;
else
cout<<"Filled Sudoku is wrong"<<endl;
return 0;
}
public class Sudoku {
static boolean checkeer(int [][]arr, int n){
int Rowsum = n*(n+1)/2;
int Colsum = Rowsum;
int finalsum = Colsum;
int RowDuplicate = 0;
int colDuplicate = 0;
int Coldata =0;
int RowData =0;
for(int i = 0; i < n; i++){
RowDuplicate = 0;
RowData = 0;
Rowsum =finalsum;
Colsum = finalsum;
Coldata = 0;
colDuplicate =0;
for(int count =0; count < n; count++ ){
if(arr[i][count] >= 1 && arr[i][count]<=9 && arr[count][i] >=1 && arr[count][i] <= 9){
Rowsum-= arr[i][count];
Colsum -= arr[count][i];
RowData = arr[i][count];
Coldata = arr[count][i];
if(((RowDuplicate & 1 << RowData) == 1)||((colDuplicate & 1 << Coldata) == 1)){
return false;
} else {
RowDuplicate |= 1 << RowData;
colDuplicate |= 1 << Coldata;
}
} else {
return false;
}
}
if(Colsum != 0 || Rowsum != 0){
return false;
}
}
return true;
}
public static void main(String []args){
int[][] sudoko1 ={ {5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9}
};
boolean result = checkeer(sudoko1,9);
System.out.print(result);
}
}
#include<iostream>
using namespace std;
const int LENGTH = 9;
bool checkRow(int sudo[LENGTH][LENGTH],int rownum){
int auxarr[LENGTH] = {0};
for(int i = 0; i<LENGTH; i++){
if(auxarr[sudo[rownum][i]-1] == 0){
auxarr[sudo[rownum][i]-1] = 1;
}else{
return false;
}
}
return true;
}
bool checkColumn(int sudo[LENGTH][LENGTH],int colnum){
int auxarr[LENGTH] = {0};
for(int i = 0; i<LENGTH; i++){
if(auxarr[sudo[i][colnum]-1] == 0){
auxarr[sudo[i][colnum]-1] = 1;
}else{
return false;
}
}
return true;
}
bool checkSubMatrix(int sudo[LENGTH][LENGTH], int startx, int starty){
int auxarr[LENGTH] = {0};
for(int i=startx;i<startx+3;i++){
for(int j=starty;j<starty+3;j++){
if(auxarr[sudo[i][j]-1] == 0){
auxarr[sudo[i][j]-1] = 1;
}else{
return false;
}
}
}
return true;
}
int main(){
int sudoku[LENGTH][LENGTH]={{5,3,4,6,7,8,9,1,2},
{6,7,2,1,9,5,3,4,8},
{1,9,8,3,4,2,5,6,7},
{8,5,9,7,6,1,4,2,3},
{4,2,6,8,5,3,7,9,1},
{7,1,3,9,2,4,8,5,6},
{9,6,1,5,3,7,2,8,4},
{2,8,7,4,1,9,6,3,5},
{3,4,5,2,8,6,1,7,9}
};
int startx = 0;
int starty = 0;
bool result = 1;
for(int i=0;i<LENGTH;i++){
result = result &
checkRow(sudoku,i) &
checkColumn(sudoku,i) &
checkSubMatrix(sudoku,startx,starty);
starty += 3;
if(result){
if(starty >= LENGTH){
starty = 0;
startx += 3;
}
}else{
cout<<"\n Incorrect Solution";
break;
}
}
if(result){
cout<<"\n Correct Solution";
}
}
Time Complexity O(n^3) space complexity O(9)
Algo:
1. Take a bool buffer[9] = {false};
2. row validation: scan row and for each element check if(buffer[row_element]) return false; else buffer[row_element] = true; after finish of a row scan buffer and check if(buffer[i] == false) return false; now before scaning to next row reinitialize buffer = {false};
3. column validation: do the same as for row.
4. return true; this is case when everything is okay.
Algo:
1. Take a bool buffer[9] = {false};
2. row validation: scan row and for each element check if(buffer[row_element]) return false; else buffer[row_element] = true; after finish of a row scan buffer and check if(buffer[i] == false) return false; now before scaning to next row reinitialize buffer = {false};
3. column validation: do the same as for row.
4. return true; this is case when everything is okay.
take all the elements in an array elements[ rows ][ columns ] ( elements [ 9 ][ 9 ]; )
//keep in mind that 1+2+3+4+5+6+7+8+9=45;
Row Validation :
1. consider first row.
2. check whether all the elements are above 0. if not return and print ' not valid'.
3. add all the elements and find the sum.
4. if sum is 45, then go to next row and iterate the above three steps until the 9th row.
5. if sum is not 45, then return and print ' not valid'.
// Do the same validation for all the 9 columns.
// Do the same validation for all the 9 sub grids.
If above 3 validations are passed, print that the puzzle is valid.
sudoku checker ... didn't compile it or anything like that...
- Sri September 30, 2013class Sudoku { private void reset(HashSet<Integer> set) { if (!set.isEmpty()) { set = new HashSet<Integer>(); } for (int i = 1; i < 10; i++) set.add(i); } private boolean checkRow(int[][] board, HashSet<Integer> set) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (!set.remove(board[i][j])) return false; } reset(set); } return true; } private boolean checkCol(int[][] board, HashSet<Integer> set) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (!set.remove(board[j][i])) return false; } reset(set); } return true; } private boolean checkBox(int[][] board, HashSet<Integer> set) { for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int row = i*3; row < i*3 + 3; row++) { for (int col = j*3; col < j*3 + 3; col++) { if (!set.remove(board[row][col])) return false; } } reset(set); } } return true; } public boolean check(int[][] board) { HashSet<Integer> set = new HashSet<Integer>(); reset(set); return (checkRow(board,set) && checkCol(board,set) && checkBox(board,set)); } }