Yahoo Interview Question for SDE1s


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

- sweety November 14, 2016 | Flag Reply
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();
}
}

- sweety November 14, 2016 | Flag Reply
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();
}

- Chris November 14, 2016 | Flag Reply
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.

- NoOne November 15, 2016 | Flag Reply
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;
}

- divm01986 November 17, 2016 | Flag Reply
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

- Shubham Saxena December 07, 2016 | Flag Reply
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"

- shubh2506 December 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- nerellaramu149 June 19, 2018 | 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