Microsoft Interview Question Software Engineer / Developers
Country: United States
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.
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);
}
}
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.
// 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.
{
LinkedList<MetricsNode> queue=new LinkedList<MetricsNode>();//for breadth first search
Hashmap<Metrics,boolean> records=new Hashmap<Metrics,boolean>();//for recording status of nodes and visited codes
reocrds.add(Start, true);
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))
{
records.add(nearcase, true);
if (nearcase==Target)
{
System.out.print("find Target");
}else
{
queue.push(nearcase);
}
}
}
}
}
}
// 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.
{
LinkedList<MetricsNode> queue=new LinkedList<MetricsNode>();//for breadth first search
Hashmap<Metrics,boolean> records=new Hashmap<Metrics,boolean>();//for recording status of nodes and visited codes
reocrds.add(Start, true);
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))
{
records.add(nearcase, true);
if (nearcase==Target)
{
System.out.print("find Target");
}else
{
queue.push(nearcase);
}
}
}
}
}
}
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)
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;
}
}
}
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;
using System.Threading.Tasks;
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)
newPoint.Add(StackCopy(currentPoint, p.X - 1, p.Y));
}
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)
newPoint.Add(StackCopy(currentPoint, p.X, p.Y - 1));
}
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)
newPoint.Add(StackCopy(currentPoint, p.X, p.Y + 1));
}
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)
newPoint.Add(StackCopy(currentPoint, p.X+1, p.Y));
}
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; }
}
}
Please review and pass feedback.
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;
}
}
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
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,
std::vector<std::vector<unsigned char>>& roadMap,
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;
}
if (roadMap[start.row][start.col] == 1 ||
roadMap[end.row][end.col] == 1) {
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
roadMap[curPos.row][curPos.col] = 2;
posToVisit.pop();
}
return false;
}
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
{
Console.WriteLine("Path not found");
}
}
}
}
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)
{
path.Add(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(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)
{
path.Add(start);
}
else
{
path.Remove(start);
}
}
if (pathFound == false)
{
path.Clear();
path = null;
}
}
return pathFound;
}
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)
Breadth first search would yield shorter path.
- Anonymous September 05, 2014