Amazon Interview Question for Software Engineers


Country: United States
Interview Type: Written Test




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

#include <stdio.h>
#include <malloc.h>
#define ROWS 4
#define COLS 5 
int exists_path(int** matrix, int currx, int curry, int endx, int endy, int maxx, int maxy)
{
    if (currx < 0 || currx > maxx)
        return 0;
    if (curry < 0 || curry > maxy)
        return 0;
    if (currx == endx && curry == endy)
        return 1;
    if (matrix[currx][curry] == 1)
        return 0;
    //printf("%0d %0d %0d %0d\n", currx, curry, endx, endy);
    matrix[currx][curry] = 1;
    return exists_path(matrix, currx+1, curry, endx, endy, maxx, maxy) ||
           exists_path(matrix, currx-1, curry, endx, endy, maxx, maxy) ||
           exists_path(matrix, currx, curry+1, endx, endy, maxx, maxy) ||
           exists_path(matrix, currx, curry-1, endx, endy, maxx, maxy);
}
int main()
{
    int** matrix;
    matrix = malloc(sizeof(int*) * ROWS);
    int i,j;
    for (i = 0; i < ROWS; i++)
    {
        matrix[i] = malloc(sizeof(int) * COLS);
    }
    for(i = 0; i < ROWS; i++)
    {
        for (j = 0; j < COLS; j++)
            matrix[i][j] = 0;
    }
    
    matrix[0][2] = 1; matrix[0][4] = 1;
    matrix[2][1] = 1; matrix[2][2] = 1; matrix[2][3] = 1; matrix[2][4] = 1;
    matrix[3][1] = 1; matrix[3][2] = 1;
    for(i = 0; i < ROWS; i++)
    {
        for (j = 0; j < COLS; j++)
            printf("%0d ", matrix[i][j]);
        printf("\n");
    }

    int path = exists_path(matrix, 1, 4, 3, 0, 3, 4);
    printf("Hello, World! %0d\n", path);

    return 0;
}

- palemgangireddy May 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works

- neo.seekr May 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should restore the original matrix

- Anonymous May 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can easily modify your code to restore its original matrix.

- w.y May 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the need of Modifying the matrix ?

matrix[currx][curry] = 1;

- ash.taunk3 June 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.blountmarquis.CareerCupQuestions;

/**
 * Created by mlblount on 5/28/2015.
 */
public class MatrixPath {

    public static boolean isPathExist(int[][] matrix, Position start, Position end){

        if(start.row < 0 || start.row >= matrix.length) return false;
        if(start.col < 0 || start.col >= matrix[0].length) return false;
        return search(matrix, start, end);
    }

    private static boolean search(int[][] matrix, Position location, Position end) {
        if(location == null) return false;
        if(location.equals(end)) return true;
        matrix[location.row][location.col] = -1;
        Position moveUp = moveUp(matrix, location);
        Position moveRight = moveRight(matrix,location);
        Position moveDown = moveDown(matrix,location);
        Position moveLeft = moveLeft(matrix,location);

        return search(matrix,moveDown,end) || search(matrix, moveLeft, end) ||
                search(matrix, moveRight, end) || search(matrix,moveUp, end);
    }

    private static Position moveLeft(int[][] matrix, Position location) {
        int keep = location.row;
        int move = location.col - 1;
        if(move < 0 || matrix[keep][move] != 0) return null;
        return new Position(keep,move);
    }

    private static Position moveDown(int[][] matrix, Position location) {
        int move = location.row + 1;
        int keep = location.col;
        if(move >= matrix.length || matrix[move][keep] != 0) return null;
        return new Position(move,keep);
    }

    private static Position moveRight(int[][] matrix, Position location) {
        int keep = location.row;
        int move = location.col + 1;
        if(move >= matrix[0].length || matrix[keep][move] != 0) return null;
        return new Position(keep,move);
    }

    private static Position moveUp(int[][] matrix, Position location) {
        int move = location.row - 1;
        int keep = location.col;
        if(move < 0 || matrix[move][keep] != 0) return null;
        return new Position(move,keep);
    }

    public static void main(String[] args){

        int[][] matrix = new int[][]{
                                        {0,0,1,0,1},
                                        {0,0,0,0,0},
                                        {0,1,1,1,1},
                                        {0,1,1,0,0},
                                        {0,0,0,0,0}
                                    };
        Position start = new Position(1,4);
        Position end = new Position(3,0);
        System.out.println("is path exist? : " + MatrixPath.isPathExist(matrix,start,end)); //output true
        start = new Position(0,0);
        end = new Position(2,1);
        System.out.println("is path exist? : " + MatrixPath.isPathExist(matrix,start,end)); //output false

    }

    private static class Position {
        int row;
        int col;

        public Position(int x, int y){
            this.row = x;
            this.col = y;
        }
        public Position(Position p){
            this.row = p.row;
            this.col = p.col;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Position)) return false;

            Position position = (Position) o;

            if (col != position.col) return false;
            if (row != position.row) return false;

            return true;
        }

        @Override
        public int hashCode() {
            int result = row;
            result = 31 * result + col;
            return result;
        }
    }
}

- mlblount45 May 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks, it works!!

- anom May 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In a hurry, here is just the pseudocode

pseudocode
=========

1. let  (a,b) be the first zero element in 2d matrix of values Value
    a. If (a,b)==null, return false
    b. else percolation(a,b)

//Assume that the Value matrix is 4*5 matrix as given here

a-horizontal index, b vertical index

percolation(int a, int b)
{
if(a!=3)
{
find list L=[(xa,y1),(xa,y2)....(xa,yN)] where (xa,yi)=(x(a+1)),yi)=0  // top zero, the corresponding bottom is also zero

if L==null, return false

prev a=a, prevb=b

for each coord in L:
{
if adjacent(coord,(a,b))
{
a=coord(x)+1
b=coord(y)
percolation(a,b)
}
}
if preva==a && prevb==b return false
}
else return true
}

- monica_shankar May 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I see recursive solutions listed which are fine and will work.
However, an alternative is to use an iterative BFS with a queue, which favours O(1) space rather than O(n), generally will find a path in fewer steps or iterations, and will also find a shortest path.

- Jason May 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

typedef struct Position {
	Position() : row(-1), col(-1) {}
	Position(size_t r, size_t c) : row(r), col(c) {}
	size_t row;
	size_t col;
} position_t;

bool PathExists(vector<vector<char>>& grid, size_t r, size_t c, size_t y, size_t x, queue<string>& result, char obstacle)
{
	string pos, origin;
	ostringstream oss, oss1;
	set<string> visited;
	map<string, string> route;
	vector<position_t> positions;
	positions.push_back(position_t(r, c));
	oss << r << c;
	origin = oss.str();
	oss.str("");
	while (!positions.empty()) {
		vector<position_t> nextHops(positions);
		positions.clear();
		for (vector<position_t>::const_iterator it = nextHops.begin(); it != nextHops.end(); it++) {
			oss1.str("");
			oss1 << it->row << it->col;
			// Go Down
			if (it->row + 1 < grid.size())
				if (it->row + 1 == y && it->col == x) {// Reach destination. The first reach is the shortest path
					oss.str("");
					oss << it->row + 1 << it->col;
					result.push(oss.str());
					pos = oss1.str();
					result.push(pos);
					while (pos != origin && route.find(pos) != route.end()) {
						pos = route[pos];
						result.push(pos);
					}
					return true;
				} else if (grid[it->row + 1][it->col] != obstacle) {// Obstacle. Cancel this route
					oss.str("");
					oss << it->row + 1 << it->col;
					if (visited.find(oss.str()) == visited.end()) { // Prevent loop
						positions.push_back(position_t(it->row + 1, it->col));
						route.emplace(oss.str(), oss1.str());
						visited.emplace(oss.str());
					}
				}
			// Go Right
			if (it->col + 1 < grid[it->row].size())
				if (it->row == y && it->col + 1 == x) {// Reach destination. The first reach is the shortest path
					oss.str("");
					oss << it->row << it->col + 1;
					result.push(oss.str());
					pos = oss1.str();
					result.push(pos);
					while (pos != origin && route.find(pos) != route.end()) {
						pos = route[pos];
						result.push(pos);
					}
					return true;
				} else if (grid[it->row][it->col + 1] != obstacle) {
					oss.str("");
					oss << it->row << it->col + 1;
					if (visited.find(oss.str()) == visited.end()) { // Prevent loop
						positions.push_back(position_t(it->row, it->col + 1));
						route.emplace(oss.str(), oss1.str());
						visited.emplace(oss.str());
					}
				}
			// Go Up
			if (it->row > 0)
				if (it->row - 1 == y && it-> col == x) {// Reach destination. The first reach is the shortest path
					oss.str("");
					oss << it->row - 1 << it->col;
					result.push(oss.str());
					pos = oss1.str();
					result.push(pos);
					while (pos != origin && route.find(pos) != route.end()) {
						pos = route[pos];
						result.push(pos);
					}
					return true;
				} else if (grid[it->row - 1][it->col] != obstacle) {
					oss.str("");
					oss << it->row - 1 << it->col;
					if (visited.find(oss.str()) == visited.end()) { // Prevent loop
						positions.push_back(position_t(it->row - 1, it->col));
						route.emplace(oss.str(), oss1.str());
						visited.emplace(oss.str());
					}
				}
			// Go Left
			if (it->col > 0)
				if (it->row == y && it->col + 1 == x) {// Reach destination. The first reach is the shortest path
					oss.str("");
					oss << it->row << it->col - 1;
					result.push(oss.str());
					pos = oss1.str();
					result.push(pos);
					while (pos != origin && route.find(pos) != route.end()) {
						pos = route[pos];
						result.push(pos);
					}
					return true;
				} else if (grid[it->row][it->col - 1] != obstacle) {
					oss.str("");
					oss << it->row << it->col - 1;
					if (visited.find(oss.str()) == visited.end()) { // Prevent loop
						positions.push_back(position_t(it->row, it->col - 1));
						route.emplace(oss.str(), oss1.str());
						visited.emplace(oss.str());
					}
				}
		}
	}
	return false;
}

- Teh Kok How May 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++11 solution based on DFS

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
bool DFS(const vector< vector <int> >& A,pair<int,int> start, pair<int,int> stop, vector< vector <bool> >& visited) {
	int nrows=A.size();
	int ncols=A[0].size();
	if(start==stop)
		return true;
	visited[start.first][start.second]=true;
	bool result=false;
	// check up
	if ( start.first>0 ) 
		if (!visited[start.first-1][start.second] && !A[start.first-1][start.second] ) 
			result|=DFS(A,pair<int,int>(start.first-1,start.second),stop,visited);
	// check down
	if ( start.first<nrows-1 ) 
		if (!visited[start.first+1][start.second] && !A[start.first+1][start.second] ) 
			result|=DFS(A,pair<int,int>(start.first+1,start.second),stop,visited);
	// check left
	if ( start.second>0 ) 
		if (!visited[start.first][start.second-1] && !A[start.first][start.second-1] ) 
			result|=DFS(A,pair<int,int>(start.first,start.second-1),stop,visited);
	// check right
	if ( start.second< ncols-1 ) 
		if (!visited[start.first][start.second+1] && !A[start.first][start.second+1] ) 
			result|=DFS(A,pair<int,int>(start.first,start.second+1),stop,visited);
	return result;
}
bool DFS(const vector< vector <int> >& A,const pair<int,int>& start,const pair<int,int>& stop) {
	vector< vector <bool> > visited (A.size(), vector<bool>(A[0].size(),false));
	return DFS(A,start,stop,visited);
}
int main() {
	vector < vector <int> > A {
		{0,0,1,0,1},
		{0,0,0,0,0},
		{0,1,1,1,1},
		{0,1,1,0,0}
	};
	vector < vector <int> > B {
		{0,0,1,1,1},
		{0,1,0,0,0},
		{1,1,1,1,1},
		{0,0,0,0,1}
	};
	cout<<"Output:"<<DFS(A,pair<int,int>(0,0),pair<int,int>(3,0))<<endl;
	cout<<"Output:"<<DFS(B,pair<int,int>(0,0),pair<int,int>(1,2))<<endl;
}

- montreal6 June 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class AmazonExistsPath {

	public static void main(String[] args) {
		
		GraphExistentPath graphExistentPath = new GraphExistentPath();
		
		int [][] matriz = new int[5][4];

		for (int cols=0;cols<4;cols++){
			for (int rows=0;rows<5;rows++){
				if ( (cols==1 && rows ==1) || (rows==2 && cols ==1) || (rows==4 && cols ==2) )
				{
					matriz[rows][cols]=1;
					graphExistentPath.addVertex(""+rows+cols, false);
				}else
				{
					matriz[rows][cols]=0;
					graphExistentPath.addVertex(""+rows+cols, true);
				}   
			}
		}
		
		for (int indexVetex=0;indexVetex<20;indexVetex++){
			
			System.out.println(graphExistentPath.getVextex(indexVetex));
		}
		
		
		int starti = 3, startj=1, finj=2, fini=0; 
		
		addNeighbor( graphExistentPath);
		
		System.out.println(graphExistentPath.reviewPathExists(new String(""+starti+startj), new String(""+finj+fini)));
		
	}
	
	
	private static void addNeighbor(GraphExistentPath graphExistentPath){
		
		for (int indexVetex=0;indexVetex<20;indexVetex++){
			
			try{
			graphExistentPath.addNeighbor(indexVetex, graphExistentPath.getVextex(indexVetex-1));
			}catch(Exception e){
				
			}
			try{
			graphExistentPath.addNeighbor(indexVetex, graphExistentPath.getVextex(indexVetex+1));
			}catch(Exception e){
				
			}
			try{
				graphExistentPath.addNeighbor(indexVetex, graphExistentPath.getVextex(indexVetex+5));	
			}catch(Exception e){
				
			}
			try{
				graphExistentPath.addNeighbor(indexVetex, graphExistentPath.getVextex(indexVetex-5));	
			}catch(Exception e){
				
			}
			
			
		}
		
		 System.out.println("graphExistentPath "+graphExistentPath.adjList);
		
	} 

}


class StackExistentPath
{
	private final int SIZE = 20;
	private int[] stack;
	private int top;
	
	public StackExistentPath()          
	{
	   stack = new int[SIZE];    // make array
	   top = -1;
	}
	
	public void push(int j)   // put item on stack
	{
		stack[++top] = j; }
	
	public int pop()          // take item off stack
	{ 
		stack[top] = -1;
		return stack[top--]; }
	
	public int peek()         // peek at top of stack
	{ 
		return stack[top]; 
	}
	
	public boolean isEmpty()  // true if nothing on stack
	{
		return (top == -1); }

}  

	class VertexExistentPath
	{
		public String label;        // label (e.g. 'A')
		public boolean active;
		public boolean wasVisited;

		public VertexExistentPath(String lab, boolean active)
		
	    {
			label = lab;
			this.active = active;
			wasVisited = false;
	    }
		
		public String toString(){
			
			return label+" "+active;
		}
	
	} 

	class GraphExistentPath
	{
		private final int MAX_VERTS = 20;
		private VertexExistentPath vertexList[]; 
		private int numberVerts;          
		private int indexListAdjacent;          
		private StackExistentPath theStack;
	    Map<Integer, LinkedList<VertexExistentPath>> adjList;
	    TreeMap<String, Integer> shortestPath = new TreeMap<String, Integer>();
		
		public GraphExistentPath()              
		{
			
			vertexList = new VertexExistentPath[MAX_VERTS];
		    numberVerts = 0;
		    indexListAdjacent = 0;
		    theStack = new StackExistentPath();
		    adjList = new HashMap<Integer, LinkedList<VertexExistentPath>>();
		} 
	
		public void addVertex(String lab, boolean active)
	   {
			VertexExistentPath vertexExistentPath=new VertexExistentPath(lab, active);
			vertexList[numberVerts++] = vertexExistentPath;
			adjList.put(indexListAdjacent++, new LinkedList<VertexExistentPath>());
	   }
		
	   public void addNeighbor(int v1, VertexExistentPath v2) {
		   if (v2!=null)
		   adjList.get(v1).add(v2);
	   }
	   
	   public List<VertexExistentPath> getNeighbors(int v1) {
	        return adjList.get(v1);
	   }
	   
	   public VertexExistentPath getVextex(int index)
	   {
		   return vertexList[index].active?vertexList[index]:null;
	   }
	   
		public void displayVertex(int v)
	    {
			System.out.print(vertexList[v].label);
	    }
		
		public boolean reviewPathExists(String vertixBase, String vertixToFind)  // depth-first search
		{                               
			
			int indexVertixBase = findIndexVertex(vertixBase);
			int indexVertixToFind = findIndexVertex(vertixToFind);
			int counterDepth = 0;
			int vertexUnvisited = -1;
			StringBuilder chainCharofGrahp = new StringBuilder();
			
			if (indexVertixBase > -1){
				
		    	vertexList[indexVertixBase].wasVisited = true;  
			    theStack.push(indexVertixBase); 
			    counterDepth++;
			    chainCharofGrahp.append(vertixBase+"-");

			    while( !theStack.isEmpty()  )     
		        {
		         
			    	vertexUnvisited = getUnvisitedNeighbor( theStack.peek() );
			    	
			    	if(vertexUnvisited == -1) 
			    		theStack.pop();
			    	else                        
			    	{
			    		
			    		counterDepth++;
			    		chainCharofGrahp.append(vertexList[vertexUnvisited].label+"-");
			    		 
			    		//System.out.println("label "+vertexList[vertexUnvisited].label);
			    		
			    		if (vertexUnvisited == indexVertixToFind){
			    			
			    			shortestPath.put(chainCharofGrahp.toString(), counterDepth);	
			    			chainCharofGrahp = new StringBuilder();
			    			counterDepth = 0;
			    			break;
			    		}
			    		
			    		vertexList[vertexUnvisited].wasVisited = true;  // mark it
			    		theStack.push(vertexUnvisited);                 // push it
			    	}
		        } 
				    
			    
			    for(int j=0; j<numberVerts; j++)          
			    	vertexList[j].wasVisited = false;
				
				
			}
			
			
			return !shortestPath.isEmpty();
		    
		}
		
		private int findIndexVertex(String labelVertex){
			
		 	for (int i=0; i<vertexList.length;i++){
		 		
		 		if( vertexList[i].label.equalsIgnoreCase(labelVertex) ){
		 			return i;
		 		}
		 		
		 	}
		 	
		 	return -1;
		}
		
		public int getUnvisitedNeighbor(int v1) {
			
			String key = null;
			
			for ( VertexExistentPath vertexExistentPath:  adjList.get(v1) ){
				
				if (vertexExistentPath.active &&   !vertexList[findIndexVertex(vertexExistentPath.label)].wasVisited){
					key = vertexExistentPath.label;
					break;
				}
					
			}
				
				
	        return findIndexVertex(key);
	   }
		
	}

- israAzul June 21, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More