## Yahoo Interview Question for SDE1s

• 0

Country: United States
Interview Type: Phone Interview

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

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

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

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

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

``````/*
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();
}``````

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

``````// 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.``````

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

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

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

__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

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

__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"

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

``````import java.util.HashSet;
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) {

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]))
}
}
}
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;
}
}
}
return;

}
}``````

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.

### 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.