Amazon Interview Question for Software Engineer / Developers

• 0

Country: India

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

Do a BFS and be done with it.

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

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

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

How to print path ? You are supposed to print co-ordinates that come in path, not all co-ordinate fatched by BFS.

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

Please see below (scroll down a bit), I also have coded for it.

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

this is flood fill algorithm

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

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

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

The Matrix is a representation of a graph. Using, shortest path algorithms like Dijkstra's would fetch u the result.

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

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.

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

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)

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

To ashutosh.dhiman: search the Dijkstra algo in wikipedia. There is an example.

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

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..

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

I think your algo may potentially more efficient than using Dijkstra. How about the spaces?

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

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...

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

My frd, do you mind to post your code solution here? I am afraid of misunderstanding your algo. Thank you

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

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

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

dijkstra's algorithm

If you encounter 0, then the distance will be infinity

I am not sure whether this is the best solution. I ll think about it later

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

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

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

use A*

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

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

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

}

}

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

How to solve this problem by using knowledge of Graph?

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

Hey did not get the funda of variable "direct", why are u using it, Could you elaborate more ..

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

``````#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 reer=0;
int found=0;
mark[0][0]=1;
x_q[0]=0;y_q[0]=0;
{

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

}

if (!found)
std::cout<<"No Solution.\n";
return 0;
}``````

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

Any graph's shortest path algorithm should work here

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

Will warshal algorithm work? I guess so...

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

first made a graph from the given matrix.
then apply shortest path algorithm like dijekstra.
no need to think complicated algorithm.
this is the same problem asked in Amazon_India_Programming_Contest.

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

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

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

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

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

Regard an entry as a node and all of its neighbouring entry as its children, then perform a DFS will do it

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.