Amazon Interview Question
Software Engineer / DevelopersCountry: India
As all the nodes are at equi-distance a simple bfs will do the job. There is no need of Dijkstra.
#include <cstdio>
#include <queue>
using namespace std ;
#define SIZE 6
typedef struct point {
int x ;
int y ;
int length ;
}point ;
static int visited[SIZE][SIZE] ;
int matrix[SIZE][SIZE] = {
{1,1,0,1,0,0},
{0,1,0,1,1,1},
{1,1,1,1,0,1},
{0,1,1,1,0,1},
{0,0,1,0,0,1},
{0,0,1,1,0,1}
};
bool isValidMove (int x, int y) {
if ( x >=0 && x < SIZE && y >= 0 && y < SIZE ){
if ( (matrix[x][y] == 1) && (visited[x][y] != 1) )
return true ;
}
return false ;
}
int shortestPathLengthBFS () {
queue<point> q ;
int x = 0, y = 0, pLength = 0;
point p ;
p.x = x ;
p.y = y ;
p.length = pLength ;
// printf ( "x = %d, y = %d, length = %d", x, y, pLength );
visited[p.x][p.y] = 1 ;
q.push(p);
while (!q.empty()) {
p = q.front() ;
q.pop () ;
pLength = p.length ;
x = p.x ;
y = p.y ;
// printf ( "\nx = %d, y = %d, length = %d", x, y, pLength );
if ( p.x == SIZE-1 && p.y == SIZE-1 )
return p.length ;
if ( isValidMove(x-1,y) ) {
p.x = x - 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\nup" ) ;
q.push (p) ;
}
if ( isValidMove(x,y+1) ) {
p.x = x ;
p.y = y + 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\nright" ) ;
q.push (p) ;
}
if ( isValidMove (x,y-1) ) {
p.x = x;
p.y = y - 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\nleft" ) ;
q.push (p) ;
}
if ( isValidMove(x+1,y) ) {
p.x = x + 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y] = 1 ;
// printf ("\ndown" ) ;
q.push (p) ;
}
}
return -1 ;
}
int main () {
printf ("\n%d\n", shortestPathLengthBFS() );
}
How to print path ? You are supposed to print co-ordinates that come in path, not all co-ordinate fatched by BFS.
Your idea is great!
and I implemented your idea,
here is my code:
public static int get_shortest_path(int[][] test){
if(test[0][0]==0||test[test.length-1][test[0].length-1]==0){
return Integer.MAX_VALUE;
}
int[][] map=new int[test.length][test[0].length];
map[0][0]=1;
boolean change=true;
while(change){ //If there is no update, then we finish.
change=false;
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
if(test[i][j]==1){
int up=Integer.MAX_VALUE;
int down=Integer.MAX_VALUE;
int left=Integer.MAX_VALUE;
int right=Integer.MAX_VALUE;
if(i>0){
up=(map[i-1][j]==0?Integer.MAX_VALUE:map[i-1][j]);
}//check up
if(i<test.length-1){
down=(map[i+1][j]==0?Integer.MAX_VALUE:map[i+1][j]);
}//check down
if(j>0){
left=(map[i][j-1]==0?Integer.MAX_VALUE:map[i][j-1]);
}//check left
if(j<test[0].length-1){
right=(map[i][j+1]==0?Integer.MAX_VALUE:map[i][j+1]);
}//check right
int a=Math.min(up, down);
int b=Math.min(left,right);
int update=Math.min(a, b);
if(update==Integer.MAX_VALUE){
continue;
}
if(map[i][j]==0){
map[i][j]=update+1;
change=true;
}
else{
if(map[i][j]>update+1){
map[i][j]=update+1;
change=true;
}
}
}
}
}
}
int results=map[map.length-1][map[0].length-1];
if(results==0){
return Integer.MAX_VALUE;
}
else
return results-1;
}
The Matrix is a representation of a graph. Using, shortest path algorithms like Dijkstra's would fetch u the result.
How is this a matrix representation of a graph?
In graph a[i][j] represents the edge between node i and j but dont seem to be the case here. Could you please explain.
Thats what I feel.. its not directed, so you can't apply Dijkstra... You might reach to a weird state of graph if you do that.. We will have too many ties and we will will be jumping back and forth on two forks (if there is one)
Vincet.. ok, So what would be the complexity of this algo? Won't the starting from (0,0) and keep following the 1 by updating the path by +1 and using the stack for backtracking be efficient? It will be linear in number of 1s in matrix..
I think your algo may potentially more efficient than using Dijkstra. How about the spaces?
You mean space complexity? I will use a stack for backtraacking thats it. Even in case of Dijkstra you will use a binary heap or fibbonaci which will be more or same expensive as stack...
Shorest path and prints the path from backward
#include <cstdio>
#include <queue>
using namespace std ;
#define SIZE 6
typedef struct point {
int x ;
int y ;
int length ;
}point ;
typedef struct path {
int x;
int y;
bool visited ;
}path ;
static path visited[SIZE][SIZE] ;
int matrix[SIZE][SIZE] = {
{1,1,0,1,0,0},
{0,1,0,1,1,1},
{1,1,1,1,0,1},
{0,1,1,1,0,1},
{0,0,1,0,0,1},
{0,0,1,1,0,1}
};
bool isValidMove (int x, int y) {
if ( x >=0 && x < SIZE && y >= 0 && y < SIZE ){
if ( (matrix[x][y] == 1) && !(visited[x][y].visited ) )
return true ;
}
return false ;
}
void findPath () {
int x = visited[SIZE-1][SIZE-1].x , y = visited[SIZE-1][SIZE-1].y ;
while (true) {
printf ( "\nx = %d, y = %d", x , y ) ;
if ( x == 0 && y == 0 )
break ;
int temp_x = visited[x][y].x ;
int temp_y = visited[x][y].y ;
x = temp_x ;
y = temp_y ;
}
}
int shortestPathLengthBFS () {
queue<point> q ;
int x = 0, y = 0, pLength = 0 ;
point p ;
for ( int i = 0 ; i < SIZE ; i ++ ) {
for ( int j = 0 ; j < SIZE ;j ++ ) {
visited[i][j].visited = false ;
visited[i][j].x = -1 ;
visited[i][j].y = -1 ;
}
}
p.x = x ;
p.y = y ;
p.length = pLength ;
// printf ( "x = %d, y = %d, length = %d", x, y, pLength );
visited[p.x][p.y].visited = true ;
q.push(p);
while (!q.empty()) {
p = q.front() ;
q.pop () ;
pLength = p.length ;
x = p.x ;
y = p.y ;
// printf ( "\nx = %d, y = %d, length = %d", x, y, pLength );
if ( p.x == SIZE-1 && p.y == SIZE-1 ) {
printf ( "\n\nPath is : from (x = %d , y = %d)\n\n", x, y ) ;
findPath () ;
return p.length ;
}
if ( isValidMove(x-1,y) ) {
p.x = x - 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\nup" ) ;
q.push (p) ;
}
if ( isValidMove(x,y+1) ) {
p.x = x ;
p.y = y + 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\nright" ) ;
q.push (p) ;
}
if ( isValidMove (x,y-1) ) {
p.x = x;
p.y = y - 1 ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\nleft" ) ;
q.push (p) ;
}
if ( isValidMove(x+1,y) ) {
p.x = x + 1 ;
p.y = y ;
p.length = pLength + 1 ;
visited[p.x][p.y].visited = true ;
visited[p.x][p.y].x = x ;
visited[p.x][p.y].y = y ;
// printf ("\ndown" ) ;
q.push (p) ;
}
}
return -1 ;
}
int main () {
printf ("\n%d\n", shortestPathLengthBFS() );
}
Use a stack
set all '1's in the array to be -1 or something
start at your initial point,
look up, down, left right, and add all valid positions onto the stack.
change all valid position to be current distance (0 for initial point) +1 if this number is less than it's current value (or if it's -1).
pop next coordinate off stack, and repeat
By the time the stack is empty, your destination should be either -1 or some positive number. If it's -1 that means no path exists, if it's some positive number, that would be the shortest possible path. To find the path, just start from the end, and move to the adjacent square that is 1 less than the current square. repeat until you hit the starting point
import java.util.ArrayList;
class Point{
public int x;
public int y;
public Point(int x,int y){
this.x=x;
this.y=y;
}
}
public class Walk_from_0_0_to_n_n {
/*
* You have a matrix of size n*n with entries either 1 or 0.
* 1 means there is a path, 0 means no path.
* Find shortest path and print it from (0,0) to (n-1, n-1)
*/
public static void setvalue(int[][]test){
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
if((int)(Math.random()*4)>2){
test[i][j]=0;
}
else{
test[i][j]=1;
}
}
}
}
public static void show(int[][] test){
for(int i=0;i!=test.length;i++){
for(int j=0;j!=test[0].length;j++){
System.out.print(test[i][j]+" ");
}
System.out.println();
}
}
public static int get_shortest_path(int[][]test){
if(test[0][0]==0||test[test.length-1][test[0].length-1]==0){
return Integer.MAX_VALUE;
}
ArrayList<Point> map=new ArrayList<Point>();
int a=find_path(0,0,4,map,test);
int b=find_path(0,0,3,map,test);
if(a==Integer.MAX_VALUE&&b==Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
else{
return Math.min(a, b);
}
}
public static int find_path(int x,int y,int direct,ArrayList<Point> map,int[][] test){
if(checkHas(map,x,y)){
return Integer.MAX_VALUE;
}
else{
map.add(new Point(x,y));
}
if(x==test.length-1&&y==test[0].length-1){
return 1;
}
int go_down=Integer.MAX_VALUE;
int go_right=Integer.MAX_VALUE;
int go_up=Integer.MAX_VALUE;
int go_left=Integer.MAX_VALUE;
@SuppressWarnings("unchecked")
ArrayList<Point> map1=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map2=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map3=(ArrayList<Point>) map.clone();
@SuppressWarnings("unchecked")
ArrayList<Point> map4=(ArrayList<Point>) map.clone();
if(x<test.length-1&&test[x+1][y]==1&&direct!=1){
go_down=find_path(x+1,y,3,map1,test);
}
if(y<test[0].length-1&&test[x][y+1]==1&&direct!=2){
go_right=find_path(x,y+1,4,map2,test);
}
if(x>0&&test[x-1][y]==1&&direct!=3){
go_up=find_path(x-1,y,1,map3,test);
}
if(y>0&&test[x][y-1]==1&&direct!=4){
go_left=find_path(x,y-1,2,map4,test);
}
int a=Math.min(go_right, go_down);
int b=Math.min(go_up, go_left);
int result=Math.min(a, b);
if(result==Integer.MAX_VALUE){
return result;
}
else{
return result+1;
}
}
public static boolean checkHas(ArrayList<Point>map,int x,int y){
for(int i=0;i!=map.size();i++){
if(map.get(i).x==x&&map.get(i).y==y){
return true;
}
}
return false;
}
public static void main(String[] args) {
int size=7;
int[][] test=new int[size][size];
setvalue(test);
show(test);
System.out.println("Shortest Path: "+get_shortest_path(test));
}
}
#include <iostream>
void print_sol(int *x_q,int * y_q,int * l_q,int reer)
{
if (reer>0)
print_sol(x_q,y_q,l_q,l_q[reer]);
std::cout<<x_q[reer]<<" "<<y_q[reer]<<"\n";
}
int main (int argc, char * const argv[]) {
#define N 5
int map[N][N]={
{1,1,1,1,1},
{1,0,0,0,0},
{1,0,1,1,1},
{1,0,1,0,1},
{1,1,1,0,1},
};
int mark[N][N];
int offset[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int i,j;
for (i=0;i<N;i++) for (j=0;j<N;j++)
mark[i][j]=0;
int x_q[N*N];
int y_q[N*N];
int l_q[N*N];
int head=0;
int reer=0;
int found=0;
mark[0][0]=1;
x_q[0]=0;y_q[0]=0;
while (head<=reer)
{
if (head>=N*N) break;
int c_p_x=x_q[head];
int c_p_y=y_q[head];
for (i=0;i<4&&!found;i++)
{
int n_p_x=c_p_x + offset[i][0];
int n_p_y=c_p_y + offset[i][1];
if (n_p_x<0||n_p_x>=N||
n_p_y<0||n_p_y>=N)
continue;
if (mark[n_p_x][n_p_y])
continue;
if (map[n_p_x][n_p_y])
{
reer++;
x_q[reer]=n_p_x;
y_q[reer]=n_p_y;
l_q[reer]=head;
mark[n_p_x][n_p_y]=1;
}
if (n_p_x==N-1&&n_p_y==N-1)
{
found=1;
print_sol(x_q, y_q, l_q, reer);
break;
}
}
if (found) break;
head++;
}
if (!found)
std::cout<<"No Solution.\n";
return 0;
}
The approach is very simple. Use the concept of Dynamic programming. No need to go for graphical methods. Below is the code for a simple example:
#include<stdio.h>
#include<limits.h>
#define R 4
#define C 4
#define I 100000
int min(int x, int y, int z);
int minCost(int cost[R][C], int m, int n)
{
int i, j,k;
// Instead of following line, we can use int tc[m+1][n+1] or
// dynamically allocate memoery to save space. The following line is
// used to keep te program simple and make it working on all compilers.
int tc[R][C];
tc[0][0] = cost[0][0];
/* Initialize first column of total cost(tc) array */
for (i = 1; i <= m; i++)
{
if(cost[i][0]==0)
break;
tc[i][0] = tc[i-1][0] + cost[i][0];
}
for(k=i;k<=m;k++)
{
tc[k][0]=I;
}
/* Initialize first row of tc array */
for (j = 1; j <= n; j++)
{
if(cost[0][j]==0)
break;
tc[0][j] = tc[0][j-1] + cost[0][j];
}
for(k=j;k<=m;k++)
{
tc[0][k]=I;
}
/* Construct rest of the tc array */
for (i = 1; i <= m; i++)
{
for (j = 1; j <= n; j++)
{
if(cost[i][j]==0)
{
tc[i][j]=I;
}
else
{
tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + 1;
}
}
}
return tc[m][n];
}
/* A utility function that returns minimum of 3 integers */
int min(int x, int y, int z)
{
if (x < y)
return (x < z)? x : z;
else
return (y < z)? y : z;
}
/* Driver program to test above functions */
int main()
{
int cost[R][C] = { {1, 0, 1, 1},
{0, 1, 1, 1},
{1, 0, 0, 1},
{1, 0, 1, 1}
};
printf(" %d ", minCost(cost, 3, 3));
getchar();
return 0;
}
Dijstra's algorithm:
vector<int> shortest_path(vector<int> arr, int cols, int rows) {
if (cols <= 0 || rows <= 0 || arr.size() != cols*rows) return vector<int>();
vector<float> min_dist(cols*rows, numeric_limits<float>::max());
vector<bool> visited(cols*rows, false);
vector<int> previous(cols*rows, -1);
//
priority_queue<pair<int, float> > pq;
min_dist[0] = 0;
pq.push_back(make_pair(0,0));
while (!pq.empty()) {
pair<int, float> elem = pq.front();
pq.pop();
vector<int> neighbors = GetNeighbors(elem.first);
for (int i = 0; i < neighbors.size(); i++) {
int n_ix = neighbors[i];
if (visited[n_ix] || arr[n_ix] == 0) continue;
float dist = elem.first + DistanceBetween(elem.first, neighbors[i]);
if (dist < min_dist[neighbors[i]]) {
min_dist[n_ix] = dist;
previous[n_ix] = elem.first;
pq.push(make_pair(n_ix, dist));
}
visited[elem.first] = true;
}
//
// Back track to get path
vector<int> path;
path.push_back(cols*rows); // (n,n)
while (true) {
int prev = previous[path.back()];
if (prev < 0) break;
path.push_back(prev);
}
reverse(path.begin(), path.end());
return path;
}
Do a BFS and be done with it.
- Anonymous August 13, 2012