Flipkart Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

public static boolean solveSudoku(int[][] board){
    if(board == null){
        throw new NullPointerException("\"board\" may not be null");
    }
    Worker worker = new Worker(board);
    return worker.work();
}

static class Worker{
    int[][] board;
    HashSet<Integer>[] rowSets;
    HashSet<Integer>[] colSets;
    HashSet<Integer>[][] sqrSets;
  
    Worker(int[][] board){
        this.board = board;
        this.init();
    }

    void init(){
        this.rowSets = new HashSet<Integer>[9];
        this.colSets = new HashSet<Integer>[9];
        for(int i = 0; i < 9; i++){
            this.rowSets[i] = new HashSet<Integer>();
            this.colSets[i] = new HashSet<Integer>();
            for(int j = 1; j < 10; j++){
                this.rowSets[i].add(j);
                this.colSets[i].add(j);
            }
        }    
        this.sqrSets = new HashSet<Integer>[3][3];
        for(int x = 0; x < 3; x++){
            for(int y = 0; y < 3; y++){
                this.sqrSets[x][y] = new HashSet<Integer>();
                for(int i = 1; i < 10; i++){
                    this.sqrSets[x][y].add(i);
                }
            }
        }
        for(int x = 0; x < this.board.length; x++){
            for(int y = 0; y < this.board[x].length; y++){
                if(this.board[x][y] > 0){
                    this.setValue(x, y, this.board[x][y])
                }
            }
        }
    }

    void setValue(int x, int y, int val){
        this.board[x][y] = val;
        Integer integerVal = new Integer(val);
        this.rowSets[y].remove(integerVal);
        this.colSets[x].remove(integerVal);
        this.sqrSets[x/3][y/3].remove(integerVal);
    }

    void unsetValue(int x, int y){
        Integer integerVal = new Integer(this.board[x][y]);
        this.board[x][y] = 0;
        this.rowSets[y].add(integerVal);
        this.colSets[x].add(integerVal);
        this.sqrSets[x/3][y/3].add(integerVal);
    }
    
    HashSet<Integer> getPossibles(int x, int y){
        HashSet<Integer> possibles = new HashSet<Integer> possibles;
        for(Integer i : this.rowSets[x/3][y/3]){
            if(this.colSets[x].contains(i) && this.rowSet[y].contains(i)){
                possibles.add(i);
            }
        }
        return possibles;
    }

    boolean work(){
        int minX = -1;
        int minY = -1;
        HashSet<Integer> bestSolutions = null;
        int min = Integer.MAX_VALUE;
        outer: for(int x = 0; x < 9; x++){
            for(int y = 0; y < 9; y++){
                if(this.board[x][y] == 0){
                    HashSet<Integer> possibleSolutions = getPossibles(x, y);
                    if(possibleSolutions.size() == 0){
                        return false;
                    }
                    else if(possibleSolutions.size() == 1){
                        bestSolutions = possibleSolutions;
                        minX = x;
                        minY = y;
                        break outer;
                    }
                    else if(possibleSolutions.size() < min){
                        minX = x;
                        minY = y;
                        min = possibleSolutions.size();
                        bestSolutions = possibleSolutions;
                    }
                }
            }
        }
        if(minX == -1 && minY == -1){
            return true;
        }
        Iterator<Integer> iterator = bestSolutions.iterator();
        while(iterator.hasNext()){
            Integer val = iterator.next();
            this.setValue(minX, minY, val);
            if(this.work()){
                return true;
            }
            this.unset(minX, minY);
        }
        return false;
    }
}

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

This solution tries to solve sodoku based of given input. It puts the sudoku in final proccessed state. If given data provided has a solution it will take it to deterministic state..

import java.security.InvalidParameterException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class CCup_5194452572307456 {
	private static final int LEN = 9;
	private final int MATLEN = (int) Math.sqrt(LEN);
	private Cell[][] cells = new Cell[LEN][LEN];

	class Cell {
		public boolean done = false;
		@SuppressWarnings("serial")
		public HashSet<Byte> ele = new HashSet<Byte>() {
			@Override
			public String toString() {
				Iterator<Byte> iter = ele.iterator();
				StringBuilder builder = new StringBuilder();

				builder.append("[");

				while (iter.hasNext()) {
					builder.append(iter.next());
					if (iter.hasNext()) {
						builder.append(",");
					}
				}

				builder.append("]");

				return builder.toString();
			}
		};
	}

	public CCup_5194452572307456(byte[][] board) {
		if (board.length == LEN) {
			for (byte[] inner : board) {
				if (inner.length != LEN) {
					throw new InvalidParameterException("Board length is not "
							+ LEN);
				}
			}
		} else {
			throw new InvalidParameterException("Board length is not " + LEN);
		}

		init();

		for (int x = 0; x < LEN; ++x) {
			for (int y = 0; y < LEN; ++y) {
				if (board[x][y] != 0) {
					setValue(x, y, board[x][y]);
				}
			}
		}
	}

	private void setValue(int x, int y, int value) {
		cells[x][y].ele.clear();
		cells[x][y].ele.add((byte) value);
		cells[x][y].done = true;

		for (int i = 0; i < LEN; ++i) {
			if (i != y) {
				cells[x][i].ele.remove((Byte) (byte) value);
			}

			if (i != x) {
				cells[i][y].ele.remove((Byte) (byte) value);
			}
		}

		int xx = x % MATLEN;
		int yy = y % MATLEN;

		x /= MATLEN;
		y /= MATLEN;

		for (int i = 0; i < MATLEN; ++i) {
			for (int j = 0; j < MATLEN; ++j) {
				if ((i != xx) || (j != yy)) {
					cells[MATLEN * x + i][MATLEN * y + j].ele
							.remove((Byte) (byte) value);
				}
			}
		}
	}

	private void init() {
		for (int i = 0; i < LEN; ++i) {
			for (int j = 0; j < LEN; ++j) {
				cells[i][j] = new Cell();
				cells[i][j].done = false;

				for (int k = 0; k < LEN; ++k) {
					cells[i][j].ele.add((byte) (k + 1));
				}
			}
		}
	}

	@Override
	public String toString() {
		StringBuilder builder = new StringBuilder();

		for (int i = 0; i < LEN; ++i) {
			for (int j = 0; j < LEN; ++j) {
				builder.append(String.format("%1$20s",
						cells[i][j].ele.toString()
								+ (cells[i][j].done ? "*" : "")));
			}
			builder.append(System.getProperty("line.separator"));
		}

		return builder.toString();
	}

	public static void main(String[] args) {
		byte[][] data = new byte[CCup_5194452572307456.LEN][CCup_5194452572307456.LEN];
		Scanner input = new Scanner(System.in);

		System.out.println("Enter puzzle <Enter 0 for blank tiles>: ");
		for (int i = 0; i < LEN; ++i) {
			for (int j = 0; j < LEN; ++j) {
				System.out.print("Enter coord [" + (i + 1) + "," + (j + 1)
						+ "]: ");
				data[i][j] = (byte) input.nextInt();
			}
		}

		CCup_5194452572307456 cup = new CCup_5194452572307456(data);
		cup.resolve();
		System.out.println("Temp Solution: ");
		System.out.println(cup);
		input.close();
	}

	private void resolve() {
		boolean yetToResolve = true;

		while (yetToResolve) {
			yetToResolve = false;

			for (int i = 0; i < LEN; ++i) {
				for (int j = 0; j < LEN; ++j) {
					if ((!cells[i][j].done) && (cells[i][j].ele.size() == 1)) {
						yetToResolve = true;
						setValue(i, j, cells[i][j].ele.iterator().next());
					}
				}
			}
		}
	}
}

- Bharat Kumar Arya May 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

you didn't handle the cases where there are no cells that can accommodate only 1 value. Hard sudokus need you to guess at some point. And that guessing would mimic a back-tracking algorithm.

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

// A Backtracking program  in C++ to solve Sudoku problem
#include <stdio.h>
 
// UNASSIGNED is used for empty cells in sudoku grid
#define UNASSIGNED 0
 
// N is used for size of Sudoku grid. Size will be NxN
#define N 9
 
// This function finds an entry in grid that is still unassigned
bool FindUnassignedLocation(int grid[N][N], int &row, int &col);
 
// Checks whether it will be legal to assign num to the given row,col
bool isSafe(int grid[N][N], int row, int col, int num);
 
/* Takes a partially filled-in grid and attempts to assign values to
  all unassigned locations in such a way to meet the requirements
  for Sudoku solution (non-duplication across rows, columns, and boxes) */
bool SolveSudoku(int grid[N][N])
{
    int row, col;
 
    // If there is no unassigned location, we are done
    if (!FindUnassignedLocation(grid, row, col))
       return true; // success!
 
    // consider digits 1 to 9
    for (int num = 1; num <= 9; num++)
    {
        // if looks promising
        if (isSafe(grid, row, col, num))
        {
            // make tentative assignment
            grid[row][col] = num;
 
            // return, if success, yay!
            if (SolveSudoku(grid))
                return true;
 
            // failure, unmake & try again
            grid[row][col] = UNASSIGNED;
        }
    }
    return false; // this triggers backtracking
}
 
/* Searches the grid to find an entry that is still unassigned. If
   found, the reference parameters row, col will be set the location
   that is unassigned, and true is returned. If no unassigned entries
   remain, false is returned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col)
{
    for (row = 0; row < N; row++)
        for (col = 0; col < N; col++)
            if (grid[row][col] == UNASSIGNED)
                return true;
    return false;
}
 
/* Returns a boolean which indicates whether any assigned entry
   in the specified row matches the given number. */
bool UsedInRow(int grid[N][N], int row, int num)
{
    for (int col = 0; col < N; col++)
        if (grid[row][col] == num)
            return true;
    return false;
}
 
/* Returns a boolean which indicates whether any assigned entry
   in the specified column matches the given number. */
bool UsedInCol(int grid[N][N], int col, int num)
{
    for (int row = 0; row < N; row++)
        if (grid[row][col] == num)
            return true;
    return false;
}
 
/* Returns a boolean which indicates whether any assigned entry
   within the specified 3x3 box matches the given number. */
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num)
{
    for (int row = 0; row < 3; row++)
        for (int col = 0; col < 3; col++)
            if (grid[row+boxStartRow][col+boxStartCol] == num)
                return true;
    return false;
}
 
/* Returns a boolean which indicates whether it will be legal to assign
   num to the given row,col location. */
bool isSafe(int grid[N][N], int row, int col, int num)
{
    /* Check if 'num' is not already placed in current row,
       current column and current 3x3 box */
    return !UsedInRow(grid, row, num) &&
           !UsedInCol(grid, col, num) &&
           !UsedInBox(grid, row - row%3 , col - col%3, num);
}
 
/* A utility function to print grid  */
void printGrid(int grid[N][N])
{
    for (int row = 0; row < N; row++)
    {
       for (int col = 0; col < N; col++)
             printf("%2d", grid[row][col]);
        printf("\n");
    }
}
 
/* Driver Program to test above functions */
int main()
{
    // 0 means unassigned cells
    int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                      {5, 2, 0, 0, 0, 0, 0, 0, 0},
                      {0, 8, 7, 0, 0, 0, 0, 3, 1},
                      {0, 0, 3, 0, 1, 0, 0, 8, 0},
                      {9, 0, 0, 8, 6, 3, 0, 0, 5},
                      {0, 5, 0, 0, 9, 0, 6, 0, 0},
                      {1, 3, 0, 0, 0, 0, 2, 5, 0},
                      {0, 0, 0, 0, 0, 0, 0, 7, 4},
                      {0, 0, 5, 2, 0, 6, 3, 0, 0}};
    if (SolveSudoku(grid) == true)
          printGrid(grid);
    else
         printf("No solution exists");
 
    return 0;
}

- vishgupta92 August 17, 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