Amazon Interview Question
Software EngineersCountry: United States
Interview Type: Written Test
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;
}
}
}
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
}
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;
}
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;
}
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);
}
}
- palemgangireddy May 28, 2015