Yahoo Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
private static void Sudoku(int[][] mat) {
int n = mat.length;
int col=0;
for (int i = 0; i < n; i++) {
col =0;
if (i == 0) {
while (col < n) {
mat[i][col] = col;
col++;
}
}
else {
while(col<n) {
System.out.println(col);
if (col+1 < n) {
mat[i][col] = mat[i-1][col+1];
col++;
}
else {
mat[i][col] = mat[i-1][0];
break;
}
}
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
System.out.print(mat[i][j]);
}
System.out.println();
}
}
/*
this is related to solving a sodoku but it seems to not require backtracking if a proper greedy strategy
is followed, that is, pick the field with the least options to choose a number from.
e.g. in above sample there are 5 fields with numbers to choose from, 3 have 2 options, 2 have one option.
If choosing from one that has two options, maybe the choice is not good and backtracking is required.
I didn't find the prove that the greedy choice always leads to a solution without need for backtracking,
but i failed to come up with a counter-sample.
Below implementation is quite bad with O(n^5), here's how to optimize:
1. create for each cell a set containing the potential numbers. this takes O(n³) time and O(n³) space
2. go through all the sets and put them into a prio queue, so that the smallest set is on top (O(n²))
3. while this prio-queue is not empty, take the top element
if the cell hasn't already been set, set the value of that cell it referes to to the first
potential value given by this set, update all sets in the row and column and place them into
the queue or, if you can, update original items in queue (bubble up, heapify, ...)
this has an upper bound of O(n * lg(n³)) because the prio queue can contain O(n³) items
This brings it down to O(n³)
*/
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <list>
#include <utility>
#include <limits>
using namespace std;
using Matrix = vector<vector<int>>;
using SetMatrix = vector<vector<unordered_set<int>>>;
class MatrixCompleter
{
private:
Matrix matrix_; // state of the matrix
public:
MatrixCompleter(const Matrix& m) : matrix_(m) { }
void solve()
{
while(true) // O(n^2)
{
int fv = -1;
int fx = -1;
int fy = -1;
int fc = matrix_.size() + 1;
for(int x = 0; x < matrix_.size(); x++)
{
for(int y = 0; y < matrix_.size(); y++)
{
// O(n^4)
unordered_set<int> fn = getFreeNumbers(x, y); // O(n^5)
if(fn.size() > 0 && fn.size() < fc)
{
fx = x;
fy = y;
fv = *(fn.begin());
fc = fn.size();
}
}
}
if(fx >= 0) matrix_[fx][fy] = fv;
else break;
}
}
void print()
{
for(int y = 0; y < matrix_.size(); y++)
{
for(int x = 0; x < matrix_.size(); x++)
{
cout << matrix_[x][y] << " ";
}
cout << endl;
}
}
private:
unordered_set<int> getFreeNumbers(int x, int y)
{
unordered_set<int> result;
if(matrix_[x][y] != 0) return result;
for(int i = 1; i <= matrix_.size(); i++) result.insert(i);
for(int i = 0; i < matrix_.size(); i++)
{
if(matrix_[i][y] != 0) result.erase(matrix_[i][y]);
if(matrix_[x][i] != 0) result.erase(matrix_[x][i]);
}
return result;
}
};
int main()
{
auto mc = MatrixCompleter(
{
{1, 2, 0},
{0, 1, 0},
{0, 0, 1}
});
cout << "\ncase 1 input" << endl;
mc.print();
mc.solve();
cout << "\ncase 1 output" << endl;
mc.print();
mc = MatrixCompleter(
{
{1, 0, 0},
{0, 1, 0},
{0, 0, 1}
});
cout << "\ncase 2 input" << endl;
mc.print();
mc.solve();
cout << "\ncase 2 output" << endl;
mc.print();
}
// These sort of problems are kids play in ZoomBA
// We first create a regular expression match from the templates given
// Here, we replace 0 -> .? to ensure only one char matches for 0
def matching_rows( template_row , all_permutations ){
template = str(template_row,'').replace('0','.?')
select( all_permutations ) :: { str($.item,'') =~ template }
}
// A join result sudoku is valid if and only if
// the column splitting are all unique
def valid_sudoku( m , n ){
!exists ( [0:n] ) :: {
s = set ( [0:n] ) -> { m[$.item][$.$.item] }
#|s| != n
}
}
// get the template
my_template = [ [1, 2, 0], [0, 1, 0], [0, 0, 1] ]
// generate the permutations
perms = join( @ARGS = list([1:4]) -> { [1:4].list } ) :: {
#|set($.item)| == #|$.item|
}
// from the templates, get the permutations which can be used for
// generating the input argument for the join
args = list ( my_template ) -> {
matching_rows( $.item , perms )
}
// finally join the options to solve the sudoku as a join problem
results = join ( @ARGS = args ) :: {
valid_sudoku ( $.item , 3 )
}
println( results )
// and it is still less than 42 lines of code.
//Time Complexity: O(N^2) where N is the size of the matrix. Space: O(N).
public int[][] fillMatrix(int[][] m){
if(m == null || m.length == 0 || m[0].length == 0){
throw new IllegalArgumentException();
}
boolean[][] rowData = new boolean[m.length][10];
boolean[][] colData = new boolean[m.length][10];
for(int i = 0; i < m.length; i++){
for(int c = 0; c < m[0].length; c++){
if(m[i][c] != 0){
rowData[i][m[i][c]] = true;
colData[c][m[i][c]] = true;
}
}
}
boolean r =fillHelp(m,0,0,rowData,colData);
}
private boolean fillHelp(int[][] m, int r, int c, boolean[][] rowDetail, boolean[][] colDetail){
while(r < m.length){
while(c < m.length){
if(m[r][c] == 0){
for(int i = 1; i <= 9; i ++){
if(!rowDetail[r][i] && !colDetail[c][i])
{
m[r][c] = i;
rowDetail[r][i] = true;
colDetail[c][i] = true;
result = fillHelp(m,r,c+1,rowDetail,colDetail)
if(result){
return true;
}
rowDetail[r][i] = false;
colDetail[c][i] = false;
m[r][c] = 0;
}
}
return false;
}else{
c++;
}
}
c = 0;
r++;
}
return true;
}
__author__ = 'shubham.saxena'
def solveMatrix(arr, n):
i,j = findUnassignedLocation(arr, n)
if(i == -1):
return True
m = 1
while(m <= n):
if(isSafe(arr, m, n, i, j)):
arr[i][j] = m
if(solveMatrix(arr, n)):
return True
arr[i][j] = 0
m += 1
return 0
def findUnassignedLocation(arr, n):
i=0
while(i<n):
j=0
while(j<n):
if(arr[i][j] == 0):
return i,j
break
j += 1
i += 1
return -1, -1
def safeInRow(arr, k, n, row_num):
i = 0
while(i<n):
if(arr[row_num][i] == k):
return 1
i += 1
return 0
def safeInCol(arr, k, n, col_num):
i = 0
while(i<n):
if(arr[i][col_num] == k):
return 1
i += 1
return 0
def isSafe(arr, m, n, i, j):
return (1-safeInRow(arr, m, n, i))*(1-safeInCol(arr, m, n, j))
if __name__ == '__main__':
arr = [[1,2,0],[0,1,0],[0,0,1]]
n = 3
print solveMatrix(arr, n)
print arr
__author__ = 'shubham.saxena'
def solveMatrix(arr, n):
i,j = findUnassignedLocation(arr, n)
if(i == -1):
return True
m = 1
while(m <= n):
if(isSafe(arr, m, n, i, j)):
arr[i][j] = m
if(solveMatrix(arr, n)):
return True
arr[i][j] = 0
m += 1
return 0
def findUnassignedLocation(arr, n):
i=0
while(i<n):
j=0
while(j<n):
if(arr[i][j] == 0):
return i,j
break
j += 1
i += 1
return -1, -1
def safeInRow(arr, k, n, row_num):
i = 0
while(i<n):
if(arr[row_num][i] == k):
return 1
i += 1
return 0
def safeInCol(arr, k, n, col_num):
i = 0
while(i<n):
if(arr[i][col_num] == k):
return 1
i += 1
return 0
def isSafe(arr, m, n, i, j):
return (1-safeInRow(arr, m, n, i))*(1-safeInCol(arr, m, n, j))
if __name__ == '__main__':
n = int(raw_input())
arr = [[1,2,0], [0,1,0], [0,0,1]]
if(solveMatrix(arr, n)):
print arr
else:
print "Solution Doesn't Exist"
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.Set;
public class Sudoko {
public static void main(String[] args) {
int a[][] = { { 1, 2, 0 ,0}, {0, 0, 1, 0 }, {4, 0, 0, 1 },{4, 0, 0, 1 } };
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
Sudoku(a);
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}
private static void Sudoku(int[][] mat) {
LinkedHashMap<Integer,Set<Integer>> map = new LinkedHashMap<>();
for(int i=0;i<mat[0].length;i++)
map.put(i, new HashSet<>());
for(int i=0;i<mat.length;i++) {
for(int j=0;j<mat[0].length;j++) {
if(mat[i][j]!=0) {
if(!map.get(i).contains(mat[i][j]))
map.get(i).add(mat[i][j]);
}
}
}
for(int i=0;i<mat.length;i++) {
for(int j=0;j<mat[0].length;j++) {
if(mat[i][j]==0) {
int temp=1;
while(temp<mat.length && map.get(i).contains(temp)) {
temp++;
}
mat[i][j] = temp;
map.get(i).add(temp);
}
}
}
return;
}
}
private static void Sudoku(int[][] mat) {
- sweety November 14, 2016int n = mat.length;
int col=0;
for (int i = 0; i < n; i++) {
col =0;
if (i == 0) {
while (col < n) {
mat[i][col] = col;
col++;
}
}
else {
while(col<n) {
System.out.println(col);
if (col+1 < n) {
mat[i][col] = mat[i-1][col+1];
col++;
}
else {
mat[i][col] = mat[i-1][0];
break;
}
}
}
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
System.out.print(mat[i][j]);
}
System.out.println();
}
}