## Microsoft Interview Question for Software Engineer / Developers

Country: United States

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

Breadth first search would yield shorter path.

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

Breath First Search marks a visited node so it will not be revisited. A performance tweak would be, sort the distance between an unvisited or unblocked child node and the destination, recursive down to the shortest distance node first.

For example, if the start is (1,1) and the end is (3,0) of a matrix of 10x10. The algorithm should try the path of child (1,0) before the path of child (1,2). The distance between (1,0) and (3,0) is 2. The distance between (1,2) and (3,0) is 4.

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

``````public class FindPath {

public class Point {
int x;
int y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}
}

public boolean findPath(Point start, Point end, Point current, char[][] map) {

// No path here
if (current.y < 0 || current.y >= map.length || current.x < 0 || map[current.y].length <= current.x || map[current.y][current.x] == 'x') {
return false;
}

if (current.x == end.x && current.y == end.y) {
return true;
}

return findPath(start, end, new Point(current.x - 1, current.y), map) ||
findPath(start, end, new Point(current.x + 1, current.y), map) ||
findPath(start, end, new Point(current.x, current.y + 1), map) ||
findPath(start, end, new Point(current.x, current.y - 1), map);
}
}``````

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

It could go to infinitive loop, if the whole map is not 'x'. We need to put some mark there to indicate the position has been visited like change to 'v' so that it won't be re-visit again.

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

If we look at the above code, I see that we will be able to tell if a path exists or not. But we will not be able to tell what points are followed(correct me if I missed something). Using the above, how could we find the points also?

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

It is a classical graph problem. Unless it is requested to solve it differently, BFS algorithm must be the first choice.

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

``````// by default, each node in metrics has 4 neighbors: left, right, up,down.
public void breadthfirstsearch(MetricsNode Start, MetricsNode Target, MetricsNode x)//x is hinder point.
{
Hashmap<Metrics,boolean> records=new Hashmap<Metrics,boolean>();//for recording status of nodes and visited codes
queue.push(Start);
while(!start.isempty())
{
MetricsNode temp=queue.pop();
for(Metrics nearcase: temp.neighbors)
{
if (nearcase!=x)
{

if(record.containskey(nearcase))
{
continue;
}
else if(!record.containskey(nearcase))
{
if (nearcase==Target)
{
System.out.print("find Target");

}else
{
queue.push(nearcase);
}
}
}
}
}
}``````

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

``````// by default, each node in metrics has 4 neighbors: left, right, up,down.
public void breadthfirstsearch(MetricsNode Start, MetricsNode Target, MetricsNode x)//x is hinder point.
{
Hashmap<Metrics,boolean> records=new Hashmap<Metrics,boolean>();//for recording status of nodes and visited codes
queue.push(Start);
while(!start.isempty())
{
MetricsNode temp=queue.pop();
for(Metrics nearcase: temp.neighbors)
{
if (nearcase!=x)
{

if(record.containskey(nearcase))
{
continue;
}
else if(!record.containskey(nearcase))
{
if (nearcase==Target)
{
System.out.print("find Target");

}else
{
queue.push(nearcase);
}
}
}
}
}
}``````

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

The question is find a path vs finding shortest path. We should use DSF vs BSF. Of course, the shortest path will be likely the interviewer will ask next.

The data structure already given (MxN matrix). If we need to re-construct our own data structure, we need O(mn) + O(BSF/DSF) time.

We also need to find out the real path, We also need to saved where we have visisted
(0, 0) + (0, 1) + .... (x, y)

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

public class PATH {

private static Point[][] map = new Point[2][4];
/**
* @param args
*/
public static void main(String[] args) {
initMap();
System.out.println("Is path possible "+isPathPossible(map[0][3], map[1][2]));
}

private static void initMap(){
for (int i = 0; i < 2; i++){
for (int j=0; j < 4;j++){
map[i][j] = new Point(i,j,true);
}
}
map[0][2].isValid = false;
map[0][3].isValid = false;
map[1][3].isValid = false;

}

private static boolean isPathPossible(Point start, Point end){
return findPath(start, end, start);
}

private static boolean findPath(Point start, Point end, Point current){
Point top = null;
Point left = null;
Point bottom = null;
Point right = null;
boolean result = false;
if (current.x == end.x && current.y == end.y)
return true;

if (current.x-1 >= 0 && map[current.x-1][current.y].isValid){
top = map[current.x-1][current.y];
map[current.x-1][current.y].isValid = false;
result = findPath(start, end, top);
if (result)
return true;
}

if (current.y-1 >= 0 && map[current.x][current.y-1].isValid){
left = map[current.x][current.y-1];
map[current.x][current.y-1].isValid = false;
result = findPath(start, end, left);
if (result)
return true;
}

if (current.x+1 < map.length && map[current.x+1][current.y].isValid){
bottom = map[current.x+1][current.y];
map[current.x+1][current.y].isValid = false;
result = findPath(start, end, bottom);
if (result)
return true;
}

if (current.y+1 < map[0].length && map[current.x][current.y+1].isValid){
right = map[current.x][current.y+1];
map[current.x][current.y+1].isValid = false;
result = findPath(start, end, right);
if (result)
return true;
}
return false;
}

private static class Point{
int x;
int y;
boolean isValid;

public Point(int xin, int yin, boolean validin){
x = xin;
y = yin;
isValid = validin;
}
}
}

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

I see that there is recursive algorithm being used. Is there a need to have recursive algorithm? I was able to achieve this with the below code. I agree that there is still a need to optimize the way we check for visited nodes.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace matrixnxn
{
class Program
{
static int endX = 3, endY = 3;
static int m = 3, n = 4;
static int[,] matrix = new int[,] { { 0, 1, 0, 0, 0 },
//0,0 0,1 0,2 0,3 0,4
{ 0, 0, 1, 0, 0 },
//1,0 1,1 1,2 1,3 1,4
{ 0, 1, 0, 0, 1 },
//2,0 2,1 2,2 2,3 2,4
{ 0, 0, 1, 0, 0 }
//3,0 3,1 3,2 3,3 3,4
};
static void Main(string[] args)
{

int startX=1,StartY=1;

var x=FindPath(startX, StartY, endX, endX);
}

private static Stack<Point> FindPath(int startX, int StartY, int endX1, int endX2)
{
Queue<Stack<Point>> paths = new Queue<Stack<Point>>();

Stack<Point> temp = new Stack<Point>();
temp.Push(new Point() { X = startX, Y = StartY });
paths.Enqueue(temp);

while(paths.Count>0)
{
Stack<Point> currentPoint = paths.Dequeue();

if (currentPoint.Peek().X == endX && currentPoint.Peek().Y == endY)
return currentPoint;

List<Stack<Point>> newPoint = FindPoints(currentPoint);

foreach (var item in newPoint)
paths.Enqueue(item);
}

return null;
}

private static List<Stack<Point>> FindPoints(Stack<Point> currentPoint)
{
Point p = currentPoint.Peek();

List<Stack<Point>> newPoint = new List<Stack<Point>>();

if (p.X - 1 >= 0 && p.Y >= 0 && matrix[p.X-1,p.Y]==0)
{
var list = currentPoint.Where(x => x.X == p.X -1&& x.Y == p.Y).ToList();
if(list.Count==0)
}

if (p.X >= 0 && p.Y - 1 >= 0 && matrix[p.X, p.Y-1] == 0)
{
var list = currentPoint.Where(x => x.X == p.X && x.Y == p.Y-1).ToList();
if (list.Count == 0)
}

if (p.X <= m && p.Y + 1 <= n && matrix[p.X, p.Y+1] == 0)
{
var list = currentPoint.Where(x => x.X == p.X && x.Y == p.Y+1).ToList();
if (list.Count == 0)
}

if (p.X + 1 <= m && p.Y <= n && matrix[p.X+1, p.Y] == 0)
{
var list = currentPoint.Where(x => x.X == p.X +1&& x.Y == p.Y).ToList();
if (list.Count == 0)
}

return newPoint;
}

private static Stack<Point> StackCopy(Stack<Point> currentPoint, int p1, int p2)
{
Point[] currentPointArray = new Point[currentPoint.Count];

currentPoint.CopyTo(currentPointArray,0);

Stack<Point> returnStack=new Stack<Point>();

for(int i=currentPointArray.Length-1;i>=0;i--)
returnStack.Push(currentPointArray[i]);

returnStack.Push(new Point() { X = p1, Y = p2 });

return returnStack;
}
}

class Point
{
public int X { get; set; }

public int Y { get; set; }
}
}

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

Can you please explain this code

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

And you haven't specified the blocks also

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

Hi Shekhar, if you were to look at the matrix, you would find 1s in them. instead of having "x" I have "1" to show that you cannot go through that point.

in FindPoints I am checking if the next move(top, bottom, left, right) is allowed or not.

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

``````public class CMain {

public static void main(String[] args){

Point p = new Point(0, 0);

p.findPath(new Point(0,0), new Point(5,5), p, new char[10][10]);

}
}

public class Point {

int x;
int y;

public Point(int _x,int _y){
this.x=_x;
this.y=_y;
}

public boolean findPath(Point start,Point end,Point current,char[][] map){
if(
current.x<0 || current.y<0 ||
current.x >= (map[current.y].length -1 ) ||
current.y >= (map.length-1) ||
map[current.y][current.x]=='X'
)
return false;

if(current.x==end.x && current.y==end.y){
System.out.println(current.x +" , "+ current.y);
return true;
}

if(current.x<end.x ){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x+1,current.y),map);
}
else if(current.x>end.x ){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x-1,current.y),map);
}
else if (current.y<end.y){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x,current.y+1),map);
}
else if (current.y>end.y){
System.out.println(current.x +" , "+ current.y);
return findPath(start,end,new Point(current.x,current.y-1),map);
}
else
return false;

}

}``````

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

Why not A* search, it will be shortest path and best solution

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

I've had this question in one of the interviews, the best way to do this is BFS, I've implemented this in Java, let me know if you want the solution

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

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

BFS/DFS will do, but I prefer doing it with a dynamic connectivity approach as union-find.

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

Here is my solution: BFS.
See the full solution here (code + tests): cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-find-path.html

Here is the solution code.

``````#include <queue>
#include <vector>

struct Position {
unsigned int row;
unsigned int col;

Position(unsigned int posR = 0,
unsigned int posC = 0)
: row(posR), col(posC)
{}

bool operator==(const Position& rhs) const
{
return row == rhs.row && col == rhs.col;
}
};

// Road Map for each Grid
// 0 - available path
// 1- blocked
// 2 - visited (not available for later search)
bool PathFinder(const Position& start,
const Position& end,
const unsigned int MATRIX_ROW,
const unsigned int MATRIX_COL)
{
if (start.row >= MATRIX_ROW || start.col >= MATRIX_COL ||
end.row >= MATRIX_ROW || end.col >= MATRIX_COL) {
return false;
}

return false;
}

std::queue<Position> posToVisit;
posToVisit.push(start);

while (!posToVisit.empty()) {
const Position curPos = posToVisit.front();

// found the path
if (curPos == end) {
return true;
}

// Position in the corodinate of row and col
// (row = 0, col = 0) in the northwest corner
// (row = MATRIX_ROW, rol = MATRIX_COL) in the southeast corner
if (curPos.row > 0) {
Position northPos{ curPos.row - 1, curPos.col };
if (roadMap[northPos.row][northPos.col] == 0) { // available path
posToVisit.push(northPos);
}
}
if (curPos.row < (MATRIX_ROW - 1)) {
Position southPos{ curPos.row + 1, curPos.col };
if (roadMap[southPos.row][southPos.col] == 0) {// available path
posToVisit.push(southPos);
}
}
if (curPos.col > 0) {
Position westPos{ curPos.row, curPos.col - 1 };
if (roadMap[westPos.row][westPos.col] == 0) {// available path
posToVisit.push(westPos);
}
}
if (curPos.col < (MATRIX_COL - 1)) {
Position eastPos{ curPos.row, curPos.col + 1 };
if (roadMap[eastPos.row][eastPos.col] == 0) {// available path
posToVisit.push(eastPos);
}
}
// mark this grid as visited

posToVisit.pop();
}

return false;
}``````

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

My understanding of the question is you not just should verify path exists, but actually print it out. My idea - use stack for traversal and queue for storing resulting path. Here's my solution (C#) with few test cases:

``````using System;
using System.Collections.Generic;

namespace FindPathInMNMatrix
{
public enum NodeType
{
Undefined,
Visited,
Blocked
}

public class Position
{
public uint Row { get; set; }

public uint Column { get; set; }

public Position(uint row, uint column)
{
Row = row;
Column = column;
}

public override bool Equals(System.Object obj)
{
if (obj == null)
{
return false;
}

Position p = obj as Position;
if ((System.Object)p == null)
{
return false;
}

return (Row == p.Row) && (Column == p.Column);
}

public bool Equals(Position p)
{
if ((object)p == null)
{
return false;
}

return (Row == p.Row) && (Column == p.Column);
}

public static bool operator ==(Position a, Position b)
{
if (System.Object.ReferenceEquals(a, b))
{
return true;
}

if (((object)a == null) || ((object)b == null))
{
return false;
}

return a.Row == b.Row && a.Column == b.Column;
}

public static bool operator !=(Position a, Position b)
{
return !(a == b);
}

public override int GetHashCode()
{
return (int)(Row ^ Column);
}
}

class MainClass
{
/// <summary>
/// Finds path
/// </summary>
/// <remarks>
/// Idea: we use stack for traversal and queue for putting path nodes. We check in all 4 directions if
///       adjacent node isn't blocked and not visited and if so - add it to stack. We don't find any of
///       such adjacent nodes - we don't include the current node as part of path
/// </remarks>
/// <param name="nodeMap">node map (M * N)</param>
/// <param name="M">node map horizontal length</param>
/// <param name="N">node map vertical length</param>
/// <param name="start">start position</param>
/// <param name="end">end position</param>
/// <param name="queue">resulting path</param>
/// <returns>true if path found, false otherwise</returns>
static bool FindPath(NodeType[,] nodeMap, uint M, uint N, Position start, Position end, out Queue<Position> path)
{
bool pathFound = false;
bool includeInPath = false;
Stack<Position> stack = null;
path = null;
uint temp;

if (nodeMap != null && nodeMap.Length == M * N)
{
path = new Queue<Position>();

stack = new Stack<Position>();
nodeMap[start.Row, start.Column] = NodeType.Visited;
stack.Push(start);

while(stack.Count != 0)
{
start = stack.Pop();
includeInPath = false;

if (start == end)
{
path.Enqueue(start);
pathFound = true;
break;
}

if (start.Row > 0 && nodeMap[start.Row - 1, start.Column] == NodeType.Undefined)
{
temp = start.Row - 1;
nodeMap[temp, start.Column] = NodeType.Visited;
stack.Push(new Position(temp, start.Column));
includeInPath = true;
}

if (start.Row < N - 1 && nodeMap[start.Row + 1, start.Column] == NodeType.Undefined)
{
temp = start.Row + 1;
nodeMap[temp, start.Column] = NodeType.Visited;
stack.Push(new Position(temp, start.Column));
includeInPath = true;
}

if (start.Column > 0 && nodeMap[start.Row, start.Column - 1] == NodeType.Undefined)
{
temp = start.Column - 1;
nodeMap[start.Row, temp] = NodeType.Visited;
stack.Push(new Position(start.Row, temp));
includeInPath = true;
}

if (start.Column < M - 1 && nodeMap[start.Row, start.Column + 1] == NodeType.Undefined)
{
temp = start.Column + 1;
nodeMap[start.Row, temp] = NodeType.Visited;
stack.Push(new Position(start.Row, temp));
includeInPath = true;
}

if (includeInPath == true)
{
path.Enqueue(start);
}
}

if (pathFound == false)
{
path.Clear();
path = null;
}
}

return pathFound;
}

static void Main(string[] args)
{
/*NodeType[,] nodeMap = {
{ NodeType.Undefined, NodeType.Undefined, NodeType.Undefined, NodeType.Blocked},
{ NodeType.Undefined, NodeType.Undefined, NodeType.Blocked, NodeType.Blocked},
{ NodeType.Undefined, NodeType.Undefined, NodeType.Undefined, NodeType.Undefined},
};*/
/*NodeType[,] nodeMap = {
{ NodeType.Undefined, NodeType.Blocked, NodeType.Undefined, NodeType.Blocked},
{ NodeType.Undefined, NodeType.Undefined, NodeType.Blocked, NodeType.Blocked},
{ NodeType.Undefined, NodeType.Undefined, NodeType.Undefined, NodeType.Undefined},
};*/
/*NodeType[,] nodeMap = {
{ NodeType.Undefined, NodeType.Blocked, NodeType.Undefined, NodeType.Blocked},
{ NodeType.Undefined, NodeType.Undefined, NodeType.Blocked, NodeType.Blocked},
{ NodeType.Undefined, NodeType.Undefined, NodeType.Undefined, NodeType.Blocked},
};*/
NodeType[,] nodeMap = {
{ NodeType.Undefined, NodeType.Undefined, NodeType.Undefined, NodeType.Blocked},
{ NodeType.Blocked, NodeType.Blocked, NodeType.Undefined, NodeType.Blocked},
{ NodeType.Blocked, NodeType.Undefined, NodeType.Undefined, NodeType.Undefined},
};
Queue<Position> path = null;

bool pathFound = FindPath(nodeMap, 4, 3, new Position(0, 0), new Position(2, 3), out path);

if (pathFound == true && path != null && path.Count != 0)
{
Position position = path.Dequeue();
Console.Write("[{0}, {1}]", position.Row, position.Column);

while (path.Count != 0)
{
Console.Write("-->");
position = path.Dequeue();
Console.Write("[{0}, {1}]", position.Row, position.Column);
}
}
else
{
}
}
}
}``````

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

why not use DFS but BFS??

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

Guys, sorry, my solution above had a bug. Here's the one without it:

``````public enum NodeType
{
Undefined,
Visited,
Blocked
}

public class Position
{
public uint Row { get; set; }

public uint Column { get; set; }

public Position(uint row, uint column)
{
Row = row;
Column = column;
}

public override bool Equals(System.Object obj)
{
if (obj == null)
{
return false;
}

Position p = obj as Position;
if ((System.Object)p == null)
{
return false;
}

return (Row == p.Row) && (Column == p.Column);
}

public bool Equals(Position p)
{
if ((object)p == null)
{
return false;
}

return (Row == p.Row) && (Column == p.Column);
}

public static bool operator ==(Position a, Position b)
{
if (System.Object.ReferenceEquals(a, b))
{
return true;
}

if (((object)a == null) || ((object)b == null))
{
return false;
}

return a.Row == b.Row && a.Column == b.Column;
}

public static bool operator !=(Position a, Position b)
{
return !(a == b);
}

public override int GetHashCode()
{
return (int)(Row ^ Column);
}
}

class MainClass
{
/// <summary>
/// Finds path
/// </summary>
/// <remarks>
/// Idea: we use stack for traversal and list for putting path nodes. We check in all 4 directions if
///       adjacent node isn't blocked and not visited and if so - add it to stack. We don't find any of
///       such adjacent nodes - we don't include the current node as part of path
/// </remarks>
/// <param name="nodeMap">node map (M * N)</param>
/// <param name="M">node map horizontal length</param>
/// <param name="N">node map vertical length</param>
/// <param name="start">start position</param>
/// <param name="end">end position</param>
/// <param name="queue">resulting path</param>
/// <returns>true if path found, false otherwise</returns>
static bool FindPath(NodeType[,] nodeMap, uint M, uint N, Position start, Position end, out List<Position> path)
{
bool pathFound = false;
bool includeInPath = false;
Stack<Position> stack = null;
path = null;
uint temp;

if (nodeMap != null &&
nodeMap.Length == M * N &&
nodeMap[start.Row, start.Column] != NodeType.Blocked &&
nodeMap[end.Row, end.Column] != NodeType.Blocked)
{
path = new List<Position>();

stack = new Stack<Position>();
nodeMap[start.Row, start.Column] = NodeType.Visited;
stack.Push(start);

while(stack.Count != 0)
{
start = stack.Pop();
includeInPath = false;

if (start == end)
{
pathFound = true;
break;
}

if (start.Row > 0 && nodeMap[start.Row - 1, start.Column] == NodeType.Undefined)
{
temp = start.Row - 1;
nodeMap[temp, start.Column] = NodeType.Visited;
stack.Push(start);
stack.Push(new Position(temp, start.Column));
includeInPath = true;
}

if (start.Row < N - 1 && nodeMap[start.Row + 1, start.Column] == NodeType.Undefined)
{
temp = start.Row + 1;
nodeMap[temp, start.Column] = NodeType.Visited;
if (includeInPath == false)
{
stack.Push(start);
}
stack.Push(new Position(temp, start.Column));
includeInPath = true;
}

if (start.Column > 0 && nodeMap[start.Row, start.Column - 1] == NodeType.Undefined)
{
temp = start.Column - 1;
nodeMap[start.Row, temp] = NodeType.Visited;
if (includeInPath == false)
{
stack.Push(start);
}
stack.Push(new Position(start.Row, temp));
includeInPath = true;
}

if (start.Column < M - 1 && nodeMap[start.Row, start.Column + 1] == NodeType.Undefined)
{
temp = start.Column + 1;
nodeMap[start.Row, temp] = NodeType.Visited;
if (includeInPath == false)
{
stack.Push(start);
}
stack.Push(new Position(start.Row, temp));
includeInPath = true;
}

if (includeInPath == true)
{
}
else
{
path.Remove(start);
}
}

if (pathFound == false)
{
path.Clear();
path = null;
}
}

return pathFound;
}``````

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

``````Apply BFS, Considering A[i,j] <-> A[i,j+1] an edge if neither A[i,j] nor A[i,j+1] is marked as 'X'
Similarly consider A[i,j] <-> A[i+1,j] as edge  if neither A[i,j] nor A[i+1,j] is marked as 'X'``````

This will also give you shortest path as well
Complexity :
Time : O(Count of vertices which are not marked as 'X')
Space : O(M*N)

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.