## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

``````We can solve it by using a simple flood fill:

public final class Maze {
private static boolean[][] m_visited;
private static int[][] m_maze;

public static boolean hasPath(int[][] maze, int startRow, int startCol, int destRow, int destCol){
if(maze == null || maze.length == 0){
return false;
}
m_visited = new boolean[maze.length][maze[0].length];
m_maze = maze;
visit(startRow,startCol);
if(! m_visited[destRow][destCol]){
return false;
}
return true;
}

private static void visit(int i, int j) {
if(i < 0 || i >= m_visited.length || j < 0 || j >= m_visited[0].length || m_maze[i][j] == 1){
return;
}
if(!m_visited[i][j]){
m_visited[i][j] = true;
visit(i-1, j); // Move left
visit(i+1, j); // Move Right
visit(i, j-1); //Move top
visit(i, j+1); //Move bottom
}
}

public static void main(String[] args) {
int[][] maze = {{0, 0, 1, 1, 1},{0, 1, 0, 0, 0}, {1, 1, 1, 1, 1 },{0, 0, 0, 0, 1}};
System.out.println(hasPath(maze, 0,0,1,2));
}
}``````

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

Do a DFS. Make sure yuo don't get stuck in a cycle.

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

Nonrecursive DFS starting at the start position. Will operate in O(nm) complexity and O(nm) memory (no extra frame shifting too) where n and m are the dimensions of the binary array. This could potentially be sped up using something like A*, but that would take a bit more implementation.

``````public static boolean hasPath(int[][] arr, int[] start, int[] end){
if(arr == null || start == null || end == null){
throw new NullPointerException();
}
if(arr.length == 0 || arr[0].length == 0 || start.length !=2 || end.length != 2){
throw new IllegalArgumentException();
}

Stack<int[]> positionsToCheck = new Stack<int[]>();
while(!positionsToCheck.isEmpty()){
int[] pos = positionsToCheck.pop();
if(Arrays.equals(pos, end)){
return true;
}
if(pos[0] < 0 || pos[0] >= arr.length || pos[1] < 0 || pos[1] >= arr[0].length || arr[pos[0]][pos[1]] == 1 || alreadyChecked[pos[0]][pos[1]]){
continue;
}
}
return false;
}``````

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

Hello Zortlord,
while(!positionsToCheck.isEmpty()){
int[] pos = positionsToCheck.pop();
if(Arrays.equals(pos, end)){
return true;
}
if(pos[0] < 0 || pos[0] >= arr.length || pos[1] < 0 || pos[1] >= arr[0].length || arr[pos[0]][pos[1]] == 1 || alreadyChecked[pos[0]][pos[1]]){
continue;
}

Since pos[1] doesnt exist in the 1st iteration, wouldnt this cause an overflow exception?

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

``````#include <iostream>
#include <cstring>

using namespace std;

const int DG = sizeof(unsigned int) * 8;

void resetBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data &= ~(1 << (DG - 1 - bit));
}
}

void setBit(unsigned int &data, unsigned int bit) {
if (bit < DG) {
data |= (1 << (DG - 1 - bit));
}
}

unsigned int getBit(unsigned int data, unsigned int bit) {
unsigned int res = 0;
if (bit < DG) {
res = ((data & (1 << (DG - 1 - bit))) == 0) ? 0 : 1;
}

return res;
}

void setIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;

setBit(data[I], J);
}

void resetIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;

resetBit(data[I], J);
}

int getIJ(unsigned int data[], int i, int j, const int cols) {
int I = ((i * cols) + j) / DG;
int J = ((i * cols) + j) % DG;

return getBit(data[I], J);
}

bool findWay(unsigned int data[], int M, int N, int sx, int sy, int ex, int ey) {
bool found = false;

if ((sx == ex) && (sy == ey)) {
found = true;
} else {
if (getIJ(data, sx, sy, N) == 0) {
setIJ(data, sx, sy, N);

if (sy - 1 >= 0) {	// left
found = findWay(data, M, N, sx, sy - 1, ex, ey);
}
if (!found && (sx - 1 >= 0)) {	// top
found =	findWay(data, M, N, sx - 1, sy, ex, ey);
}
if (!found && (sy + 1 < N)) {	// right
found = findWay(data, M, N, sx, sy + 1, ex, ey);
}
if (!found && (sx + 1 < M)) {	//bottom
found = findWay(data, M, N, sx + 1, sy, ex, ey);
}
} else {
found = false;
}
}

return found;
}

int main() {
int M;
int N;
unsigned int* data;
int input = 0;

cin >> M >> N;
const int size = (M * N - 1) / DG + 1;

data = new unsigned int[size];
memset(data, 0, sizeof(unsigned int) * size);

for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
cin >> input;

if (input != 0) {
setIJ(data, i, j, N);
}
}
}

int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;

if (findWay(data, M, N, sx, sy, ex, ey)) {
cout << "true" << endl;
} else {
cout << "false" << endl;
}

return 0;
}``````

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

In Ruby:

``````require 'thread'

def valid_move?(matrix=[], start_pt)
start_pt[0] >= 0 &&
start_pt[0] < matrix.length &&
start_pt[1] >= 0 &&
start_pt[1] < matrix.length
end

def mark_visited(visited, point)
visited[point[0]..point[1]]=true
end

def visited?(visited, point)
visited[point[0]..point[1]]
end

def move_left(start_pt)
[start_pt[0],start_pt[1]-1]
end

def move_right(start_pt)
[start_pt[0], start_pt[1]+1]
end

def move_up(start_pt)
[start_pt[0]-1,start_pt[1]]
end

def move_down(start_pt)
[start_pt[0]+1,start_pt[1]]
end

def exists_path_recursive?(matrix, start_pt, end_pt, visited,level)
puts "Level: #{level}"
puts "Start point: #{start_pt}"
puts "End point: #{end_pt}"

return true if start_pt == end_pt
if !valid_move?(matrix, start_pt)
puts "Invalid move: #{start_pt}"
return false
elsif visited?(visited,start_pt)
return false
end

puts "Mark visited: #{start_pt}"
mark_visited(visited,start_pt)
puts "Visited: #{visited}"

return exists_path?(matrix, move_left(start_pt),end_pt,visited,level+1) ||
exists_path?(matrix, move_right(start_pt),end_pt,visited,level+1) ||
exists_path?(matrix, move_up(start_pt),end_pt,visited,level+1)  ||
exists_path?(matrix, move_down(start_pt),end_pt,visited,level+1)
end

def exists_path_nonrecursive?(matrix, start_pt,end_pt, visited)
queue = Queue.new
queue << start_pt
puts "Queue size: #{queue.length}"
puts

while !queue.empty?
point = queue.pop
puts "Queue size after pop: #{queue.length}"

if visited?(visited,point)
puts
next
end

mark_visited(visited,point)
puts "Visited: #{visited}"

return true if point == end_pt

if valid_move?(matrix,move_left(point))
puts "Move left: #{move_left(point)}"
queue << move_left(point)
puts "Queue size after push: #{queue.length}"
end

if valid_move?(matrix,move_right(point))
puts "Move right: #{move_right(point)}"
queue << move_right(point)
puts "Queue size after push: #{queue.length}"
end

if valid_move?(matrix,move_up(point))
puts "Move up: #{move_up(point)}"
queue << move_up(point)
puts "Queue size after push: #{queue.length}"
end

if valid_move?(matrix,move_down(point))
puts "Move down: #{move_down(point)}"
queue << move_down(point)
puts "Queue size after push: #{queue.length}"
end

puts
end

return false
end

matrix=[
[0,0,1,0,1],
[0,0,0,0,0],
[0,1,1,1,1],
[0,1,1,0,0],
[0,0,1,0,0]
]

start_pt=[4,1]
end_pt=[0,3]

visited={}

puts "Exists path? #{exists_path_nonrecursive?(matrix,start_pt,end_pt,visited)}"``````

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

``````/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package Dummy;

import java.io.IOException;
import java.util.Stack;
import java.util.StringTokenizer;

/**
*
* @author
*/
public class Dummy02 {

static Stack<int[]> accesspoints=new Stack<int[]>();

public static boolean findPath(int[][] points, int[] startpt, int[] endpt)
{

int[][] pointsvisited=new int[points.length][points[0].length];

visitpoint(points,pointsvisited,startpt);

for(int[] coord:accesspoints)
{
if((coord[0]==endpt[0])&&(coord[1]==endpt[1]))
return true;
}

return false;

}

public static void visitpoint(int[][] points, int[][] pointsvisited , int [] currentpoint)
{
if(currentpoint[0]<0||currentpoint[0]>=points.length||currentpoint[1]<0||currentpoint[1]>=points[0].length||
pointsvisited[currentpoint[0]][currentpoint[1]]==1||points[currentpoint[0]][currentpoint[1]]==1)
{
return ;
}

pointsvisited[currentpoint[0]][currentpoint[1]]=1;
visitpoint(points,pointsvisited,new int[]{currentpoint[0]+1,currentpoint[1]});
visitpoint(points,pointsvisited,new int[]{currentpoint[0]-1,currentpoint[1]});
visitpoint(points,pointsvisited,new int[]{currentpoint[0],currentpoint[1]+1});
visitpoint(points,pointsvisited,new int[]{currentpoint[0],currentpoint[1]-1});

}

static StringTokenizer st;

public static void main(String args[]) throws IOException
{
System.out.println("Enter the dimensions of the value matrix");
int length=nextInt();
System.out.println("Enter the matrix");
for(int i=0;i<length;i++)
{
{
points[i][j]=nextInt();
}
}
int[] startpt=new int[2];
int[] endpt=new int[2];

System.out.println("Enter the starting point");
for(int i=0;i<2;i++)
{
startpt[i]=nextInt();
}
System.out.println("Enter the coordinates of end point");
for(int i=0;i<2;i++)
{
endpt[i]=nextInt();
}

boolean value=findPath(points,startpt,endpt);

if(value)
System.out.println("There exist a path");
else
System.out.println("There exist no path");

}

public static int nextInt() throws IOException
{
return Integer.parseInt(nextToken());
}

public static String nextToken() throws IOException
{
while(st==null||!st.hasMoreTokens())
{
if(line==null)
return line;

st=new StringTokenizer(line.replaceAll("", " "));
}
return st.nextToken();
}

}``````

in input just flip for x and y

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

1. Create a List of separate graphs of each connected component of 1s
2. given 2 points check if they're in the same graph if so, path is possible, if not, no path possible.

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

Since we're not looking at the shortest path, I would try greedy best first search algorithm, as it generally finds the solution faster than regular BFS or DFS.
The calculated distance between two nodes would be the sum of the horizontal distance and the vertical distance, since we can't move in diagonals.

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

As above said,this can be done using dfs as well as bfs.Here's I implemented the same

``````#include <bits/stdc++.h>
using namespace std;
#define maxx 100
#define pb push_back
#define pii pair<int,int>
vector<pii>vpii[maxx];
#define inf 0x7fffffff
int X[]={+1,-1,0,0};//possible movements
int Y[]={0,0,+1,-1};
vector<int>v[maxx];
bool vis[maxx][maxx];
int a[4][5];
struct data
{
int x,y;
void set(int i,int j)
{
x=i;
y=j;
}
};
void dfs(data s)
{
vis[s.x][s.y]=true;
for(int i=0;i<4;i++)
{
data t;
int t1=s.x+X[i];
int t2=s.y+Y[i];
if(vis[t1][t2]==false && t1<4 && t1>=0 && t2>=0 && t2<5&& a[t1][t2]==0)
{
vis[t1][t2]=true;
t.set(t1,t2);
dfs(t);
}
}
}
int main() {
memset(vis,false,sizeof vis);
for(int i=0;i<4;++i)
for(int j=0;j<5;++j)
cin>>a[i][j];
data start,endd;
cin>>start.x>>start.y;
cin>>endd.x>>endd.y;
dfs(start);
if(vis[endd.x][endd.y])
cout<<"true";
else
cout<<"false";
return 0;
}``````

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

Note- In my dfs function,see in the IF condition please remove the extra ; before 4 and 5.I don't know why but I am unable to remove that.Thank you :)

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

``````package com.pc.careerCup;

public class MetricPath{

public static void main(String args[]){
int[][] a={{0,0,1,0,1},
{0,0,0,0,0},
{0,1,1,1,1},
{0,1,1,0,0}};
int[][] visited= a;
System.out.println("Result : " + isPath(a,  0, 3,3, 0, visited));
}

private static boolean isPath(int[][] a, int x, int y, int endX, int endY, int[][] visited){
System.out.print("{" + x + "," + y + "} ->");

if(x == endX && y==endY){
return true;
}

boolean result=false;
visited[x][y]=1;

//Move up
if(x-1>=0 && (visited[x-1][y]!=1)){

result=isPath(a, x-1, y, endX, endY, visited);
}

//Move down
if((!result) && (x+1 < a.length) && (visited[x+1][y]!=1)){
result=isPath(a, x+1, y, endX, endY, visited);
}

//Move left
if((!result) && (y-1 >=0 )&& (visited[x][y-1]!=1)){
result=isPath(a, x, y-1,endX, endY, visited);
}

//Move right
if((!result) && (y + 1 <a[0].length) && (visited[x][y+1]!=1)){
result=isPath(a, x, y+1,endX, endY, visited );
}
return result;
}
}``````

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

i/p: {0, 3} ,{ 3, 0}
o/p: Result:True,
{0,3} ->{1,3} ->{1,2} ->{1,1} ->{0,1} ->{0,0} ->{1,0} ->{2,0} ->{3,0}

i/p {0, 3} ,{ 3, 3}
o/p: Result: True

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

Why you guys have to put so many code for a DFS? DFS recursive should only be as simple as this:

``````class Solution:
matrix=[]
xlimit=0
ylimit=0
endpoint=[]
stack=[]
result=0

def findpath(self,matrix,startpoint,endpoint):
self.matrix = matrix
self.xlimit=len(matrix)
self.ylimit=len(matrix[0])
self.endpoint=endpoint
self.stack.append([startpoint[0],startpoint[1]])
self.DFS(startpoint[0],startpoint[1])

if self.result <> 0:
return True
return False

def DFS(self,x,y):
if x==self.endpoint[0] and y==self.endpoint[1]:
print 'we reached it finally this is the path:', self.stack
self.result+=1
return
if x+1<self.xlimit and self.matrix[x+1][y]==0 and [x+1,y] not in self.stack:
self.stack.append([x+1,y])
self.DFS(x+1,y)
self.stack.pop()
if x-1>=0 and self.matrix[x-1][y]==0 and [x-1,y] not in self.stack:
self.stack.append([x-1,y])
self.DFS(x-1,y)
self.stack.pop()
if y+1<self.ylimit and self.matrix[x][y+1]==0 and [x,y+1] not in self.stack:
self.stack.append([x,y+1])
self.DFS(x,y+1)
self.stack.pop()
if y-1>=0 and self.matrix[x][y-1]==0 and [x,y-1] not in self.stack:
self.stack.append([x,y-1])
self.DFS(x,y-1)
self.stack.pop()``````

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

Why you guys have to write this many code. A DFS recursive should be as simple as this

``````class Solution:
matrix=[]
xlimit=0
ylimit=0
endpoint=[]
stack=[]
result=0

def findpath(self,matrix,startpoint,endpoint):
self.matrix = matrix
self.xlimit=len(matrix)
self.ylimit=len(matrix[0])
self.endpoint=endpoint
self.stack.append([startpoint[0],startpoint[1]])
self.DFS(startpoint[0],startpoint[1])

if self.result <> 0:
return True
return False

def DFS(self,x,y):
if x==self.endpoint[0] and y==self.endpoint[1]:
print 'we reached it finally this is the path:', self.stack
self.result+=1
return
if x+1<self.xlimit and self.matrix[x+1][y]==0 and [x+1,y] not in self.stack:
self.stack.append([x+1,y])
self.DFS(x+1,y)
self.stack.pop()
if x-1>=0 and self.matrix[x-1][y]==0 and [x-1,y] not in self.stack:
self.stack.append([x-1,y])
self.DFS(x-1,y)
self.stack.pop()
if y+1<self.ylimit and self.matrix[x][y+1]==0 and [x,y+1] not in self.stack:
self.stack.append([x,y+1])
self.DFS(x,y+1)
self.stack.pop()
if y-1>=0 and self.matrix[x][y-1]==0 and [x,y-1] not in self.stack:
self.stack.append([x,y-1])
self.DFS(x,y-1)
self.stack.pop()``````

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

Simple DFS approch would work.

1. Add start Node to Stack
2. Continue 3. till stack is not empty or goal node reached
3. Explore top, bottom, left, right. Add to stack

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

class Solution:
matrix = []
xlimit = 0
ylimit = 0
result = 1

def findpath(self, matrix, startpoint):
self.matrix = matrix
self.xlimit = len(matrix)
self.ylimit = len(matrix[0])
nsteps = self.DFS(startpoint[0],startpoint[1])
if nsteps == 0:
return -1
return nsteps

def DFS(self,x,y):
if x+1 < self.xlimit:
if self.matrix[x+1][y] == 1:
self.result += 1
return self.DFS(x+1, y)
elif self.matrix[x+1][y]==9:
return self.result
if y+1 < self.ylimit:
if self.matrix[x][y+1] == 1:
self.result += 1
return self.DFS(x, y+1)
elif self.matrix[x][y+1]==9:
return self.result
if x-1 >= 0:
if self.matrix[x-1][y] == 1:
self.result += 1
return self.DFS(x-1, y)
elif self.matrix[x-1][y]==9:
return self.result
if y-1 >= 0:
if self.matrix[x][y-1] == 1:
self.result += 1
return self.DFS(x, y-1)
elif self.matrix[x][y-1]==9:
return self.result

a = Solution()
print(a.findpath([[1,0,0],[1,0,0],[1,9,1]], (0, 0)))
b = Solution()
print(b.findpath([[1,1,1,1],[0,1,1,1],[0,1,0,1],[1,1,9,1],[0,0,1,1]], (0,0)))

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

``````class Solution:
matrix = []
xlimit = 0
ylimit = 0
result = 1

def findpath(self, matrix, startpoint):
self.matrix = matrix
self.xlimit = len(matrix)
self.ylimit = len(matrix[0])
nsteps = self.DFS(startpoint[0],startpoint[1])
if nsteps == 0:
return -1
return nsteps

def DFS(self,x,y):
if x+1 < self.xlimit:
if self.matrix[x+1][y] == 1:
self.result += 1
return self.DFS(x+1, y)
elif self.matrix[x+1][y]==9:
return self.result
if y+1 < self.ylimit:
if self.matrix[x][y+1] == 1:
self.result += 1
return self.DFS(x, y+1)
elif self.matrix[x][y+1]==9:
return self.result
if x-1 >= 0:
if self.matrix[x-1][y] == 1:
self.result += 1
return self.DFS(x-1, y)
elif self.matrix[x-1][y]==9:
return self.result
if y-1 >= 0:
if self.matrix[x][y-1] == 1:
self.result += 1
return self.DFS(x, y-1)
elif self.matrix[x][y-1]==9:
return self.result

a = Solution()
print(a.findpath([[1,0,0],[1,0,0],[1,9,1]], (0, 0)))
b = Solution()
print(b.findpath([[1,1,1,1],[0,1,1,1],[0,1,0,1],[1,1,9,1],[0,0,1,1]], (0,0)))``````

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

Here is the solution to reach a destination 9 in a matrix

``````class Solution:
matrix = []
xlimit = 0
ylimit = 0
result = 1

def findpath(self, matrix, startpoint):
self.matrix = matrix
self.xlimit = len(matrix)
self.ylimit = len(matrix[0])
nsteps = self.DFS(startpoint[0],startpoint[1])
if nsteps == 0:
return -1
return nsteps

def DFS(self,x,y):
if x+1 < self.xlimit:
if self.matrix[x+1][y] == 1:
self.result += 1
return self.DFS(x+1, y)
elif self.matrix[x+1][y]==9:
return self.result
if y+1 < self.ylimit:
if self.matrix[x][y+1] == 1:
self.result += 1
return self.DFS(x, y+1)
elif self.matrix[x][y+1]==9:
return self.result
if x-1 >= 0:
if self.matrix[x-1][y] == 1:
self.result += 1
return self.DFS(x-1, y)
elif self.matrix[x-1][y]==9:
return self.result
if y-1 >= 0:
if self.matrix[x][y-1] == 1:
self.result += 1
return self.DFS(x, y-1)
elif self.matrix[x][y-1]==9:
return self.result

a = Solution()
print(a.findpath([[1,0,0],[1,0,0],[1,9,1]], (0, 0)))
b = Solution()
print(b.findpath([[1,1,1,1],[0,1,1,1],[0,1,0,1],[1,1,9,1],[0,0,1,1]], (0,0)))``````

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.