Microsoft Interview Question Senior Software Development Engineers
Team: advance algorithm
Country: United States
Interview Type: Written Test
Will the answers to 2 and 3 in your list after the code always be compatible (i.e, two paths that don't cross on white squares) ?
What's the memory usage like in the worst case grid for a very large N?
To make sure that white cell will not be used second time we can pass the same boolean array 'visited' used on step (2) to step (3).
Another possible way is to flip the cell to black state once it's visited, in this case we don't even need array 'visited', but it's require modification of the initial array.
The worst case for 'findPath' that come to mind is when 'start' and 'target' cell will be located on different corners of the array, for example 'start = Cell(0,0)' and 'target = Cell(N-1, N-1)'. In this case it's require 2N memory to store cells in the queue + we use cells with the memorization.
This will miss some answers. As u are doing BFS, u'll get shortest path to Grey cell. However, it might be possible that the shortest path to grey cell blocks the path from grey cell to destination cell.
e.g. case where above solution will fail
-1 => start
-2 => destination
0 => white space
1 => black space
2 => grey space
-1 0 0 0 0
0 0 0 1 0
0 1 0 2 0
0 1 1 1 1
0 0 0 0 -2
The solution to this is to take the longer path (from source to right edge of square, down to 2's row, then to 2) to grey cell, and then go from there to destination.
Hitesh's example is a good one !
Wont work for this case.
Instead. We can apply a DFS from the cell (0, 0) and accept a path only if reaches the cell (N-1, N-1) and we encounter the gray cell during our traversal.
During the recursive call, we pass a
gray_used
flag and accept a path if it reaches (N-1, N-1) and the flag is true on reaching that cell.
8 directions , counting all paths
int count;
bool seengrey; //externals for convenience
void _countpaths(A, i, j)
{
if( i<0 || j<0 || i==A.length || j==A.length) return; //out of bounds
if( i==A.length-1 && j==A.length-1 && seengrey) count++, return; //end of proper path
if( A[i][j] == 1 ) return; //black
if( A[i][j] == 2 ) {
if( seengrey ) return; //grey but already seen grey
else seengrey = true; //just discovered grey
}
else A[i][j]=1; //white so mark it black
for(int u=-1; u<2; u++)
for(int v=1; v<2; v++)
if( !(u==0 && v==0) ) countpaths(A, i+u, j+v);
if( A[i][j] == 1) A[i][j]=0; //if black, was original white
else seengrey=false; //else it was grey, so unmark seeing grey
}
int countpaths(A)
{
count=0, _countpaths(A,0,0), return count;
}
private static class Step{
int x, y;
public Step(int xVal, int yVal){
x = xVal;
y = yVal;
}
@Override
public int hashCode(){
int prime = 31;
int result = 1;
result = result * prime + x;
result = result * prime + y;
return result;
}
@Override
public boolean equals(Object obj){
if(obj == null){
return false;
}
if(this == obj){
return true;
}
if(getClass() != obj.getClass()){
return false;
}
Step step = (Step)obj;
if(step.x != x || step.y != y){
return false;
}
return true;
}
}
public static ArrayList<Step> getAdjSteps(Step curStep, int[][] matrix){
ArrayList<Step> ret = new ArrayList<Step>();
int curX = curStep.x, curY = curStep.y;
if(curX - 1 >= 0){
ret.add(new Step(curX - 1, curY));
}
if(curX + 1 <= matrix.length - 1){
ret.add(new Step(curX + 1, curY));
}
if(curY - 1 >= 0){
ret.add(new Step(curX, curY - 1));
}
if(curY + 1 <= matrix[0].length - 1){
ret.add(new Step(curX, curY + 1));
}
return ret;
}
enum Status {VISITED, UNVISITED};
public static boolean findGreyPath(int[][] matrix){
Map<Step, Status> visited = new HashMap<Step, Status>();
Stack<Step> path = new Stack<Step>();
Step start = new Step(0,0);
Step end = new Step(matrix.length - 1, matrix[0].length - 1);
path.push(start);
visited.put(start, Status.VISITED);
boolean ret = findGreyPathInternal(matrix, path, visited, end);
if(ret){
Step tmpStep = null;
Iterator<Step> ite = path.iterator();
while(ite.hasNext()){
tmpStep = ite.next();
System.out.format("->[%d, %d]", tmpStep.x, tmpStep.y);
}
}
return ret;
}
public static boolean findGreyPathInternal(int[][] matrix, Stack<Step> path, Map<Step, Status> visited, Step exit){
if(!path.isEmpty()){
Step curStep = path.peek();
for(Step s: getAdjSteps(curStep, matrix)){
if(visited.get(s) == null && (matrix[s.x][s.y] == 0 || matrix[s.x][s.y] == 2)){
path.push(s);
visited.put(s, Status.VISITED);
if(s.equals(exit)){
boolean hasGrey = false;
Step tmpStep = null;
Iterator<Step> ite = path.iterator();
while(ite.hasNext()){
tmpStep = ite.next();
if(matrix[tmpStep.x][tmpStep.y] == 2){
hasGrey = true;
}
}
if(hasGrey){
return true;
}
}// end "== exit"
boolean ret = findGreyPathInternal(matrix, path, visited, exit);
if(ret){
return true;
}
}// end if
}// end for-each step
visited.remove(path.pop());
}// end if stack empty
return false;
}
public static void main(String[] args) throws Exception {
int[][] matrix = new int[6][6];
matrix[0] = new int[]{0, 1, 1, 1, 1, 1};
matrix[1] = new int[]{0, 0, 0, 0, 1, 1};
matrix[2] = new int[]{1, 0, 1, 0, 1, 0};
matrix[3] = new int[]{1, 2, 1, 0, 1, 0};
matrix[4] = new int[]{1, 0, 0, 0, 1, 0};
matrix[5] = new int[]{1, 1, 1, 0, 0, 0};
System.out.println(findGreyPath(matrix));
}
Ans: ->[0, 0]->[1, 0]->[1, 1]->[2, 1]->[3, 1]->[4, 1]->[4, 2]->[4, 3]->[5, 3]->[5, 4]->[5, 5]true
public class Matgame {
public static void main(String[] args)
{
// TODO Auto-generated method stub
Matrix matrix = new Matrix();
matrix.printTheMatrixValues();
matrix.findThePath(matrix.mat[0][0]);
matrix.printSuccessPath();
}
}
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;
public class Matrix
{
int rows;
int columns;
ArrayList<Node>successPath = new ArrayList<Node>();
Node mat[][];
void enterRowsAndColumns()
{
Scanner input = new Scanner(System.in);
System.out.println("Enter the rows of the matrix : \n");
this.rows = input.nextInt();
System.out.println("Enter the columns of the matrix : \n");
this.columns = input.nextInt();
}
Matrix()
{
enterRowsAndColumns();
this.mat = new Node[this.rows][this.columns];
buildMatrixWithUserInput();
}
public void printSuccessPath(){
int i=0;
System.out.println("\nSuccess path is:");
while(i < this.successPath.size())
{
System.out.println(this.successPath.get(i).id);
i++;
}
}
private void buildMatrixWithUserInput()
{
System.out.println("Enter the values in the matrix\n");
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
for(int i=0;i<this.rows;i++)
for(int j=0;j<this.columns;j++)
{
int num = input.nextInt();
mat[i][j] = new Node(num, i*rows + j, i, j, false);
}
}
void printTheMatrixValues()
{
System.out.println("\n");
for(int i=0;i<this.rows;i++)
{
System.out.println("\n");
for(int j=0;j<this.columns;j++)
{
System.out.print(this.mat[i][j].value + " ");
}
}
}
void printTheMatrixIDs()
{
System.out.println("\n");
for(int i=0;i<this.rows;i++)
{
System.out.println("\n");
for(int j=0;j<this.columns;j++)
{
System.out.print(this.mat[i][j].id + " ");
}
}
}
public boolean findThePath(Node n) {
// TODO Auto-generated method stub
//Perform the first node check
if(n.x==0 && n.y==0)
{
//this is the first node, check if we can start from here
if(n.value==0)
{
this.successPath.add(n);
}
else
{
System.out.println("No path exists");
return false;
}
}
//Perform the last node check
if(n.x==rows-1 && n.y==columns-1)
{
//This is the last node
if(n.value == 0)
{
boolean flag = false;
//check if the success path contains 2
int i=0;
while(i != this.successPath.size()-1)
{
if(this.successPath.get(i).value == 2)
{
flag = true;
break;
}
i++;
}
if(flag)
return true;
else
return false;
}
}
//Get the node's neighbours
ArrayList<Node> neighbours = new ArrayList<Node>();
neighbours = getNeighboursWith0or2(n);
if (neighbours.size()==0)
{
//System.out.println("Hi: n id : " + n.id);
if(n.id == 0)
{
System.out.println("No success path");
}
return false;
}
for(Node k: neighbours)
{
if(this.successPath.contains(k))
{
continue;
}
this.successPath.add(k);
boolean success = findThePath(k);
if(success)
return true;
else
{
this.successPath.remove(k);
}
}
return false;
}
private ArrayList<Node> getNeighboursWith0or2(Node n)
{
// TODO Auto-generated method stub
ArrayList<Node> neighbours = new ArrayList<Node>();
if(n.id > this.columns)
{
Node up = getNodeWithId(n.id - this.columns);
if(up.value ==0 || up.value == 2)
{
neighbours.add(up);
//System.out.println("ADDED UPPER");
}
}
if(n.id <= (this.rows*this.columns-1) - this.columns)
{
Node down = getNodeWithId(n.id + this.columns);
if(down.value ==0 || down.value == 2)
{
neighbours.add(down);
//System.out.println("ADDED DOWN");
}
}
if(n.id % this.columns != 0)
{
Node left = getNodeWithId(n.id - 1);
if(left.value == 0 || left.value == 2)
{
neighbours.add(left);
//System.out.println("ADDED LEFT");
}
}
if((n.id+1) % this.columns != 0)
{
Node right = getNodeWithId(n.id + 1);
if(right.value ==0 || right.value == 2)
{
neighbours.add(right);
//System.out.println("ADDED RIGHT");
}
}
//System.out.println(neighbours.size());
return neighbours;
}
private Node getNodeWithId(int id)
{
int col = id % (this.columns);
int row = id / this.columns;
return this.mat[row][col];
}
}
public class Node
{
int value;
int id;
int x;
int y;
boolean visited;
Node(int value, int id, int x, int y, boolean visited)
{
this.value = value;
this.id = id;
this.x = x;
this.y = y;
this.visited = visited;
}
}
CONSOLE:
Enter the rows of the matrix :
6
Enter the columns of the matrix :
6
Enter the values in the matrix
0
0
2
1
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
0
0
1
1
1
1
0
1
1
0
0
1
0
0
0
0
0
0 0 2 1 1 1
1 1 0 1 1 1
1 1 0 1 1 1
1 0 0 1 1 1
1 0 1 1 0 0
1 0 0 0 0 0
Success path is:
0
1
2
8
14
20
19
25
31
32
33
34
28
29
35
I have written code to confirm whether metric contains a path via gray point. However it is not able to print the path found.
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Testyourskills
{
/// <summary>
/// <p>There is a matrix which contains white cells , black cells and only one gray cell, need to go from (0,0) to (N-1, N-1)
/// if Array[N][N]
/// <br>constraints:
/// <br>a. The path should cover only white cells and should go via grey cell.
/// <br>b. The node once visited cannot be visited again.
/// <br>
/// <br>White cells are represented by 0, black cells by 1 and grey cell by 2.</p>
/// @Author : Pramod Kumar Chandoria
/// </summary>
public class MetrixPath
{
public static bool FindPath(Cell[,] array, int destination)
{
var queue = new Queue<Cell>();
bool midPointVisited = false;
//var path = new List<Cell>();
Cell lastSplit = null;
EnqueCell(queue, array[0, 0], destination);
while (queue.Count > 0)
{
var cell = queue.Dequeue();
if (cell.x == destination && cell.y == destination)
{
if (midPointVisited)
{
Console.WriteLine("Path found via gray point");
return true;
}
else
{
continue;
}
}
else if (cell.value == 2)
{
midPointVisited = true;
}
int count = queue.Count();
if (cell.x < destination)
{
EnqueCell(queue, array[cell.x + 1, cell.y], destination);
}
if (cell.y < destination)
{
EnqueCell(queue, array[cell.x, cell.y + 1], destination);
}
if (cell.x > 0)
{
EnqueCell(queue, array[cell.x - 1, cell.y], destination);
}
if (cell.y > 0)
{
EnqueCell(queue, array[cell.x, cell.y - 1], destination);
}
}
Console.WriteLine("Path not found");
return false;
}
public static void EnqueCell(Queue<Cell> queue, Cell currentCell, int destination)
{
if (currentCell.x <= destination
&& currentCell.y <= destination
&& !currentCell.visited
&& currentCell.value > 0
&& currentCell.value < 3)
{
currentCell.visited = true;
queue.Enqueue(currentCell);
}
}
}
public class Cell
{
internal bool visited;
internal int x;
internal int y;
internal int value;
}
public class TestMatrixPath
{
public static void Main(string[] args)
{
int[,] intArray = new int[4, 4] {
{ 1, 1, 1, 0 },
{ 1, 1, 2, 1 },
{ 1, 0, 0, 1 },
{ 1, 1, 0, 1 }
};
intArray = new int[4, 4] {
{ 1, 1, 2, 1 },
{ 1, 1, 0, 1 },
{ 1, 0, 0, 1 },
{ 1, 0, 0, 1 }
};
Cell[,] array = new Cell[4, 4];
for (int i = 0; i < 4; i++ )
{
for (int j = 0; j < 4; j++)
{
array[i, j] = new Cell { value = intArray[i, j], visited = false, x = i, y = j };
}
}
MetrixPath.FindPath(array, 3);
}
}
}
1. Write a function of the form:
public static void findPath(int row, int col, int maxRow, int maxCol){
if(row >= maxRow || col >= maxCol){
return;
}
if(row == maxRow -1 && col == maxCol-1){
numOfPaths++;
return;
}
if(visited[row][col])
return;
visited[row][col] = true;
findPath(row + 1, col, maxRow, maxCol);
findPath(row, col+1, maxRow, maxCol);
}
2. Use this function to reach from (0,0) to the cell marked gray. Suppose gray cell has coordinate as (x,y), function call in that case would be findPath(0, 0, x, y).
3. In second part use this function to reach from (x,y) to (m-1, n-1)
Another way for two directions.
You should be able to:
Recolour some "blocking lines" outwardling from the grey point to black (to block paths that go around the grep point).
Then recolour the grey point to white.
Now we just have to find paths through the white points.
Because these two directions prevent cycles, the model is a DAG.
So we can compute number of paths to any white square from any possible previous white square and fill out a table.
This won't work always.
Looks you assuming there's only one route to grey grid from (0,0)
IN case there's more than one route to grey grid, then for each route to grey grid we need to traverse frm grey to end. Simply choosing one route and trying to get end from grey might not always succeed.
Anyway, there's no fuss needed about grey grid and all.
Simply use your code to traverse from (0.0) to destination grid, and check if any of the grid in path is grey, if yes this is the path, else backtrack.
Yes, doesn't look you covering all travel directions
in short something like
bool getPath(r,c)
{
bool ret = false;
int oriColor;
if (r<0 || r>N || c<0 || c>N) return false;
if (r==N && c == N)
{
if (grey)
{
print("the path is\n");
return true;
}
else return false;
}
oriColor = Grid[r][c];
if (Grid[r][c] == GREY) grey = true;
Grid[r][c] = visited;
ret = getPath(r, c-1);
if (ret)
{
print(%d %d", r, c-1);
return true;
}
ret = getPath(r, c+1);
if (ret)
{
print(%d %d", r, c+1);
return true;
}
ret = getPath(r-1, c);
if (ret)
{
print(%d %d", r-1, c);
return true;
}
ret = getPath(r+1, c);
if (ret)
{
print(%d %d", r+1, c);
return true;
}
ret = getPath(r+1, c-1);
if (ret)
{
print(%d %d", r+1, c-1);
return true;
}
ret = getPath(r+1, c+1);
if (ret)
{
print(%d %d", r+1, c+1);
return true;
}
ret = getPath(r-1, c-1);
if (ret)
{
print(%d %d", r-1, c-1);
return true;
}
ret = getPath(r-1, c+1);
if (ret)
{
print(%d %d", r, c-1);
return true;
}
if (!ret)
{
Grid[r][c] = oriColor;
if (oriColor == grey) grey = false;
}
return false;
}
@Varun
He has some loose ends in his explanation, but it should work if he calculates total paths as:
DFS_countpaths( (0,0), (a,b) ) * DFS_countpaths( (a,b), (n-1,n-1) );
You solution will fail on something like this:
0 0 0 0 0
0 1 0 1 0
0 1 x 1 0
0 0 0 1 0
in both case - whether we can go to 4 direction or 8.
Because, when you find path from A to X it will be:
p p p 0 0
0 1 p 1 0
0 1 x 1 0
0 0 0 1 0
and where is no path from X to B not including first path.
8 direction , counting all paths
int count;
bool seengrey;
void _countpaths(A, i, j)
{
if( i<0 || j<0 || i==A.length || j==A.length) return; //out of bounds
if( i==A.length-1 && j==A.length-1 && seengrey) count++, return; //ends proper path
if( A[i][j] == 1 ) return; //black
if( A[i][j] == 2 ) {
if( seengrey ) return; //grey but already seen grey
else seengrey = true; //just discovered grey
}
else A[i][j]=1; //white so mark it black
for(int u=-1; u<2; u++)
for(int v=1; v<2; v++)
if( !(u==0 && v==0) ) countpaths(A, i+u, j+v);
if( A[i][j] == 1) A[i][j]=0; //if black, was original white
else seengrey=false; //else it was grey, so unmark seeing grey
return;
}
int countpaths(A)
{
count=0;
return _countpaths(A,0,0);
}
Typed it raw.
I guess, and not sure yet, that the following algorithm works.
int[] path = GetPath(); // From (0,0) to (N - 1, N - 1)
boolean good_path = PathCrossesGreyNode(path);
while (good_path == false) {
AddCostToPath(path); // for any edge on this path, increase the edge cost by a constant
path = GetPath();
good_path = PathCrossesGreyNode(path);
}
Here I have assume that one move in only two direction. For movement in all the eight directions code needs to be modified accordingly.
Actually, see responses to your 2 direction code.
It is not at all obvious how to extend that to the 8 direction (cycling Dir. graph) model.
Because the paths from (0,0) to grey, and paths from grey to (N-1,N-1) will depend on each other, so you can't use "the product rule" from combinatorics.
And the product rule bit is assuming you meant that (which is the way to make your idea for 2 direction case work).
Scan through the matrix and form a undirected graph with 0s and 2s vertices and do a BFS or DFS?
DFS.
Main reason against BFS is that it won't work.
It works "layer by layer" and the first vertex to be seen by some path will not be allowed to be part of another path (because of the visited flag being set already).
For example if your code does down before right.
down then right might reserve a vertex even though
right then down could also have a path going through there
And there are other reasons.
Start at 0,0 and reach n-1,n-1. I still don't see a problem using BFS. The problem says it should "contain only white cells" and not "contain all white cells".
Please explain?
public List<Cell> findPath(int[][] arr, boolean[][] visited, Cell start, Cell target) { final Queue<Cell> queue = new LinkedList<Cell>(); queue.add(start); while (!queue.isEmpty()) { final Cell current = queue.poll(); final int x = current.getX(); final int y = current.getY(); visited[x][y] = true; final List<Cell> path = current.getPath(); path.add(current); if (x == target.getX() && y == target.getY()) { return path; } optionalQueueAdd(arr, visited, new Cell(x + 1, y, path), queue); optionalQueueAdd(arr, visited, new Cell(x, y + 1, path), queue); optionalQueueAdd(arr, visited, new Cell(x - 1, y, path), queue); optionalQueueAdd(arr, visited, new Cell(x, y - 1, path), queue); } return null; } public void optionalQueueAdd(int[][] arr, boolean[][] visited, Cell newCell, Queue<Cell> queue) { if (newCell.getX() < arr.length && newCell.getY() < arr.length && newCell.getX() >= 0 && newCell.getY() >= 0 && !visited[newCell.getX()][newCell.getY()] && arr[newCell.getX()][newCell.getY()] != 1) { queue.add(newCell); } }Modification of BFS.
- anonymous October 23, 20131. Find the gray cell in the array
2. Find and save path between (0,0) and gray cell index using 'findPath'
3. Find and save path between gray cell index and (N-1, N-1) using 'findPath'
4. Concatenate paths
The procedure 'findPath' could be optimized (with next steps checking only right and bottom cells).