Amazon Interview Question Software Developers
Country: United States
Interview Type: Written Test
My attempts at DP:
// This is the text editor interface.
// Anything you type or change here will be seen by the other person in real time.
#include <stdlib.h>
#include <vector>
#include <map>
#include <iostream>
using namespace std;
class Point {
public:
Point(int _x, int _y) { x = _x; y = _y; visited = false;}
bool operator==(const Point & rhs) {
//if (this == &rhs) { return(true); }
if ((this->x == rhs.x) &&
(this->y == rhs.y)) {
return(true);
}
else {
return(false);
}
}
bool operator<(const Point & rhs) const {
if (x != rhs.x) {
return(x < rhs.x);
}
else {
return(y < rhs.y);
}
}
Point & operator=(const Point & rhs) {
if (this == &rhs) { return(*this); }
x = rhs.x;
y = rhs.y;
return(*this);
}
void print() { cout << x << ":" << y << endl; }
void setvisited() { visited = true; }
bool getvisited() { return(visited); }
private:
int x;
int y;
bool visited;
};
typedef std::map<Point, vector<Point> > _btMap;
static _btMap btMap;
void ReadMatrix(int matrix[][5], int rows, int cols)
{
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
Point pt(i, j);
std::vector<Point> vecpt;
if (matrix[i][j] == 1) continue;
if (i > 0) {
if (matrix[i-1][j] == 0) { vecpt.push_back(Point(i-1, j)); }
}
if (j > 0) {
if (matrix[i][j-1] == 0) { vecpt.push_back(Point(i, j-1)); }
}
if (i < rows-1) {
if (matrix[i+1][j] == 0) { vecpt.push_back(Point(i+1, j)); }
}
if (j < cols-1) {
if (matrix[i][j+1] == 0) { vecpt.push_back(Point(i, j+1)); }
}
if (vecpt.size()) {
// cout << "inserting for i: " << i << "j:" << j << endl;
btMap[pt] = vecpt;
}
}
}
}
bool SrchRec(Point & src, Point & dest, bool & done)
{
if (done) { return(true); }
if (btMap.count(dest) > 0) {
//dest.print();
dest.setvisited();
vector<Point> & vecpt = btMap[dest];
for (size_t i = 0; i < vecpt.size(); i++) {
if (vecpt[i].getvisited() == true) { continue; }
//cout << "can be reached via" << endl;
//vecpt[i].print();
if (vecpt[i] == src) {
done = true;
return(true);
}
if (!SrchRec(src, vecpt[i], done)) { continue; }
else { done = true; return(true); }
}
}
return(false);
}
int main()
{
int matrix[][5] = { {0, 0, 1, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 1},
{0, 1, 1, 0, 0}
};
//cout << "Reading matrix" << endl;
ReadMatrix(matrix, 4, 5);
//cout << "done reading matrix" << endl;
bool done = false;
Point src(3,3), dest(0,3);
if (SrchRec(src, dest, done)) {
std::cout << "true" << endl;
}
else {
std::cout << "false" << endl;
}
return(0);
}
BFS using C++.
class Position {
public:
int _x;
int _y;
Position(int x, int y) :
_x(x),
_y(y) {
}
bool operator== (const Position& rhs) {
return _x == rhs._x && _y == rhs._y;
}
};
vector<Position> neighbors(const Position& curr, const vector<vector<int>>& puzzle) {
vector<Position> neighbors = {
Position(curr._x - 1, curr._y),
Position(curr._x + 1, curr._y),
Position(curr._x, curr._y - 1),
Position(curr._x, curr._y + 1)
};
for (auto it = neighbors.begin(); it != neighbors.end();) {
const Position& p = *it;
if (p._x == -1 || p._x == puzzle[0].size() || p._y == -1 || p._y == puzzle.size()) {
it = neighbors.erase(it);
}
else {
++it;
}
}
return neighbors;
}
bool pathExists(vector<vector<int>> &puzzle,
const Position& start,
const Position& end) {
queue<Position> Q;
Q.push(start);
puzzle[start._y][start._x] = 1;
while (Q.size() > 0) {
Position curr = Q.front();
Q.pop();
if (curr == end) {
return true;
}
for (Position& neighbor : neighbors(curr, puzzle)) {
if (puzzle[neighbor._y][neighbor._x] == 0) {
puzzle[neighbor._y][neighbor._x] = 1;
Q.push(neighbor);
}
}
}
return false;
}
BFS using C++.
class Position {
public:
int _x;
int _y;
Position(int x, int y) :
_x(x),
_y(y) {
}
bool operator== (const Position& rhs) {
return _x == rhs._x && _y == rhs._y;
}
};
vector<Position> neighbors(const Position& curr, const vector<vector<int>>& puzzle) {
vector<Position> neighbors = {
Position(curr._x - 1, curr._y),
Position(curr._x + 1, curr._y),
Position(curr._x, curr._y - 1),
Position(curr._x, curr._y + 1)
};
for (auto it = neighbors.begin(); it != neighbors.end();) {
const Position& p = *it;
if (p._x == -1 || p._x == puzzle[0].size() || p._y == -1 || p._y == puzzle.size()) {
it = neighbors.erase(it);
}
else {
++it;
}
}
return neighbors;
}
bool pathExists(vector<vector<int>> &puzzle,
const Position& start,
const Position& end) {
queue<Position> Q;
Q.push(start);
puzzle[start._y][start._x] = 1;
while (Q.size() > 0) {
Position curr = Q.front();
Q.pop();
if (curr == end) {
return true;
}
for (Position& neighbor : neighbors(curr, puzzle)) {
if (puzzle[neighbor._y][neighbor._x] == 0) {
puzzle[neighbor._y][neighbor._x] = 1;
Q.push(neighbor);
}
}
}
return false;
}
BFS using C++.
class Position {
public:
int _x;
int _y;
Position(int x, int y) :
_x(x),
_y(y) {
}
bool operator== (const Position& rhs) {
return _x == rhs._x && _y == rhs._y;
}
};
vector<Position> neighbors(const Position& curr, const vector<vector<int>>& puzzle) {
vector<Position> neighbors = {
Position(curr._x - 1, curr._y),
Position(curr._x + 1, curr._y),
Position(curr._x, curr._y - 1),
Position(curr._x, curr._y + 1)
};
for (auto it = neighbors.begin(); it != neighbors.end();) {
const Position& p = *it;
if (p._x == -1 || p._x == puzzle[0].size() || p._y == -1 || p._y == puzzle.size()) {
it = neighbors.erase(it);
}
else {
++it;
}
}
return neighbors;
}
bool pathExists(vector<vector<int>> &puzzle,
const Position& start,
const Position& end) {
queue<Position> Q;
Q.push(start);
puzzle[start._y][start._x] = 1;
while (Q.size() > 0) {
Position curr = Q.front();
Q.pop();
if (curr == end) {
return true;
}
for (Position& neighbor : neighbors(curr, puzzle)) {
if (puzzle[neighbor._y][neighbor._x] == 0) {
puzzle[neighbor._y][neighbor._x] = 1;
Q.push(neighbor);
}
}
}
return false;
}
public class Path2D {
public static boolean isPathPresent(int[][] in, int i, int j, Cordinates c, boolean visit[][]) {
if(!c.validCords(in.length-1,in[0].length-1,i,j)) return false;
if(i == c.e_i && j == c.e_j) return true;
if(!visit[i][j] && in[i][j] ==0) {
visit[i][j] = true;
return isPathPresent(in, i+1, j, c, visit) || isPathPresent(in, i-1, j, c, visit)
||isPathPresent(in, i, j+1, c, visit) || isPathPresent(in, i, j-1, c, visit) ;
}
return false;
}
public static void main(String[] args) {
int m = 4;
int n = 3;
int[][] mat = { {0, 0, 1, 0, 1},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 1},
{0, 1, 1, 0, 0} };
boolean[][] visit = new boolean[m][n];
for(int i=0; i< m;i++){
for(int j=0; j<n; j++) {
visit[i][j] = false;
}
}
Cordinates c = new Cordinates();
c.s_i = 3;
c.s_j = 0;
c.e_i = 0;
c.e_j= 2;
System.out.println("Have path ? " +isPathPresent(mat, 3, 0, c, visit));
}
}
class Cordinates {
public int s_i, s_j, e_i, e_j;
public int c_i, c_j;
public boolean validCords(int m, int n, int i, int j) {
if(i > m || j > n || i < 0 || j < 0) return false;
return true;
}
}
#include<bits/stdc++.h>
using namespace std;
#define R 3
#define C 5
#define rep(i,a,n) for(int i=a;i<n;i++)
int X[] = {-1,0,1,0};
int Y[] = {0,-1,0,1};
bool V[4][5];
bool visit(int M[4][5],int s_i,int s_j,int end_i,int end_j)
{
cout << "i: " << s_i << " j: " << s_j << endl;
M[s_i][s_j] = true;
if(s_i == end_i && s_j == end_j)
return true;
rep(i,0,4)
{
//cout << i << endl;
if((s_i+X[i]) < R && (s_j + Y[i]) < C && (s_i+X[i]) >= 0 && (s_j + Y[i]) >= 0 && !M[s_i+X[i]][s_j + Y[i]] && visit(M,s_i + X[i],s_j + Y[i],end_i,end_j))
return true;
}
return false;
}
int main()
{
int matrix[][5] = { {0, 0, 1, 1, 1},
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 1}
};
rep(i,0,4)
rep(j,0,5)
if(matrix[i][j])
V[i][j] = true;
else
false;
if(visit(matrix,0,0,2,3))
cout << "present\n";
else
cout << "not\n";
return 0;
}
I would suggest to run a simple DFS and calculate connectivity component for each vertex. It would allow to answer several questions like "pathExists(from, to)" on the same input without calculating the path each time for each new input.
public class ConnectivityComponents {
private final Map<Position, Integer> components = new HashMap<>();
public ConnectivityComponents(int[][] matrix) {
find(matrix);
}
private void find(int[][] matrix) {
int component = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) { // allowed
Position position = new Position(i, j);
if (!components.containsKey(position)) {
dfs(matrix, position, component++);
}
}
}
}
}
private void dfs(int[][] matrix, Position position, int component) {
components.put(position, component);
getAdjacentPositions(matrix, position).stream().filter(p -> !components.containsKey(p)).forEach(p -> {
dfs(matrix, p, component);
});
}
private List<Position> getAdjacentPositions(int[][] matrix, Position position) {
List<Position> positions = new ArrayList<>();
// up
if (position.x - 1 >= 0 && matrix[position.x - 1][position.y] == 0) {
positions.add(new Position(position.x - 1, position.y));
}
// down
if (position.x + 1 < matrix.length && matrix[position.x + 1][position.y] == 0) {
positions.add(new Position(position.x + 1, position.y));
}
// left
if (position.y - 1 >= 0 && matrix[position.x][position.y - 1] == 0) {
positions.add(new Position(position.x, position.y - 1));
}
// right
if (position.y + 1 < matrix[position.x].length && matrix[position.x][position.y + 1] == 0) {
positions.add(new Position(position.x, position.y + 1));
}
return positions;
}
public boolean hasPath(Position start, Position end) {
Integer startComponent = components.get(start);
Integer endComponent = components.get(end);
return startComponent != null && startComponent.equals(endComponent);
}
private static class Position {
final int x;
final int y;
Position(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Object o) {
if (o == null || o.getClass() != Position.class) {
return false;
}
Position p = (Position) o;
return x == p.x && y == p.y;
}
public int hashCode() {
return 13*x + 23*y;
}
}
public static void main(String[] args) {
int[][] input = new int[][]{{0,0,1,0,1},{0,1,0,0,0},{0,1,1,1,1},{0,1,1,0,0}};
ConnectivityComponents test = new ConnectivityComponents(input);
System.out.println(test.hasPath(new Position(3, 0), new Position(0, 3)));
}
}
using System;
using System.Diagnostics;
namespace AlgoTest
{
class MainClass
{
/*
0, 1, 1, 0, 0
0, 1, 1, 1, 1
0, 0, 1, 0, 0
0, 0, 1, 0, 1
0, 0, 1, 0, 1
0, 0, 0, 0, 1
0, 0, 0, 0, 1
*/
public static void Main (string[] args)
{
int[, ] matrix = { {
0, 0, 0, 0, 1
}
, {
0, 0, 0, 0, 1
}
, {
0, 0, 1, 0, 1
}
, {
0, 0, 1, 0, 1
}
, {
0, 0, 1, 0, 0
}
, {
0, 1, 1, 1, 1
}
, {
0, 0, 1, 0, 0
}
};
Position start1 = new Position (0, 6);
Position end1 = new Position (4, 4);
bool res = pathExists (matrix, start1, end1, Direction.None);
Console.WriteLine (res);
}
// 5, 4
public static bool pathExists(int[,] matrix, Position start, Position end, Direction heading)
{
Debug.Print
(start.x.ToString () + ", " + start.y.ToString ());
if (start.x == end.x && start.y == end.y)
return true;
bool pathexists = false;
// directional guidance
Direction navVertDir = ((end.y - start.y) < 0) ? Direction.Down : Direction.Up;
Direction navHorDir = ((end.x - start.x) < 0) ? Direction.Left : Direction.Right;
if (navVertDir == Direction.Up && (start.y < (matrix.GetLength (0)) && heading != Direction.Down
&& matrix [start.y + 1, start.x] != 1)) {
start.y += 1;
pathexists = pathExists (matrix, start, end, navVertDir);
}
if (!pathexists && navVertDir == Direction.Down && (start.y > 0 && heading != Direction.Up && matrix [start.y - 1, start.x] != 1)) {
start.y -= 1;
pathexists = pathExists (matrix, start, end, navVertDir);
}
if (!pathexists && navHorDir == Direction.Right && (start.x < (matrix.GetLength (1)) && heading != Direction.Left
&& matrix [start.y, start.x + 1] != 1)) {
start.x += 1;
pathexists = pathExists (matrix, start, end, navHorDir);
}
if (!pathexists && navHorDir == Direction.Left && (start.x > 0 && heading != Direction.Right && matrix [start.y, start.x - 1] != 1)) {
start.x -= 1;
pathexists = pathExists (matrix, start, end, navHorDir);
}
if (!pathexists && (start.y < (matrix.GetLength (0)) && heading != Direction.Down
&& matrix [start.y + 1, start.x] != 1)) {
start.y += 1;
pathexists = pathExists (matrix, start, end, Direction.Up);
}
else if (!pathexists && (start.y > 0 && heading != Direction.Up && matrix [start.y - 1, start.x] != 1)) {
start.y -= 1;
pathexists = pathExists (matrix, start, end, Direction.Down);
}
if (!pathexists && (start.x < (matrix.GetLength (1)) && heading != Direction.Left
&& matrix [start.y, start.x + 1] != 1)) {
start.x += 1;
pathexists = pathExists (matrix, start, end, Direction.Right);
}
else if (!pathexists && (start.x > 0 && heading != Direction.Right && matrix [start.y, start.x - 1] != 1)) {
start.x -= 1;
pathexists = pathExists (matrix, start, end, Direction.Left);
}
return pathexists;
}
}
public enum Direction {
Up, Down, None,Right, Left
}
public class Position
{
public int x, y;
public Position(int _x, int _y)
{
this.x = _x;
this.y = _y;
}
public override bool Equals(System.Object obj)
{
// If parameter is null return false.
if (obj == null)
{
return false;
}
return this.x == ((Position)obj).x && this.y == ((Position)obj).y;
}
}
}
A breadth first search solution
bool pathFinder(vector<vector<int> > & grid, pair<int, int> start, pair<int, int> end){
int row = grid.size();
int col = grid[0].size();
unordered_set<int> visited;
queue<pair<int, int> > q;
q.push(start);
visited.insert(start->first * col + start->second);
while(!q.empty()){
pair<int, int> p = q.front();
q.pop();
int y = p->first;
int x = p->second;
if(y == end->first && x == y->second){
return true;
}
visited.insert(y * col + x);
// right
if(x + 1 < col && grid[y][x+1] != 1 && visited.find(y * col + x + 1) == visited.end()){
q.push({y, x + 1});
}
// left
if(x - 1 >= 0 && grid[y][x-1] != 1 && visited.find(y * col + x - 1) == visited.end()){
q.push({y, x - 1});
}
// down
if(y + 1 < row && grid[y+1][x] != 1 && visited.find((y + 1) * col + x) == visited.end()){
q.push({y + 1, x});
}
// up
if(y - 1 >= 0 && grid[y-1][x] != 1 && visited.find((y - 1) * col + x) == visited.end()){
q.push({y - 1, x});
}
}
return false;
}
static void Main(string[] args)
{
int[,] array = { { 0, 0, 1, 1, 1 },
{ 0, 1, 0, 0, 0 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 1 },
};
if (checkIfPathExists(array, 3, 0, 1, 2))
Console.WriteLine("True");
else
Console.WriteLine("False");
}
static Boolean checkIfPathExists(int[,] array, int startRow, int startCol, int endRow, int endCol)
{
Dictionary<int, Dictionary<int, int>> currentStackOfCells = new Dictionary<int, Dictionary<int, int>>();
if (!canGoToNextCell(array, startRow, startCol, currentStackOfCells)) return false;
if (!canGoToNextCell(array, endRow, endCol, currentStackOfCells)) return false;
return FindPath(array, startRow, startCol, endRow, endCol, currentStackOfCells);
}
static Boolean FindPath(int[,] array, int currentRow, int currentCol, int endRow, int endCol, Dictionary<int, Dictionary<int, int>> currentStackOfCells)
{
if (!currentStackOfCells.ContainsKey(currentRow))
currentStackOfCells[currentRow] = new Dictionary<int, int>();
currentStackOfCells[currentRow][currentCol] = 1; //push current cell into visited cell's list
Boolean retCd = false;
if ((currentRow == endRow) && (currentCol == endCol)) retCd = true;
if ((!retCd) && canGoToNextCell(array, currentRow - 1, currentCol, currentStackOfCells)) //try to go up
retCd = FindPath(array, currentRow - 1, currentCol, endRow, endCol, currentStackOfCells);
if ((!retCd) && canGoToNextCell(array, currentRow + 1, currentCol, currentStackOfCells)) //try to go down
retCd = FindPath(array, currentRow + 1, currentCol, endRow, endCol, currentStackOfCells);
if ((!retCd) && canGoToNextCell(array, currentRow, currentCol - 1, currentStackOfCells)) //try to go left
retCd = FindPath(array, currentRow, currentCol - 1, endRow, endCol, currentStackOfCells);
if ((!retCd) && canGoToNextCell(array, currentRow, currentCol + 1, currentStackOfCells)) //try to go right
retCd = FindPath(array, currentRow, currentCol + 1, endRow, endCol, currentStackOfCells);
currentStackOfCells[currentRow].Remove(currentCol); //remove cell from the visited cell's list
return retCd;
}
static Boolean canGoToNextCell(int[,] array, int nextRow, int nextCol, Dictionary<int, Dictionary<int, int>> currentStackOfCells)
{
//check if out of boundaries
if (nextRow < 0) return false;
if (nextRow >= array.GetLength(0)) return false;
if (nextCol < 0) return false;
if (nextCol >= array.GetLength(1)) return false;
//end out of boundaries check
//check if current cell is 0
if (array[nextRow, nextCol] == 1) return false;
//check if we already visited this cell and going in cycles
if (currentStackOfCells.ContainsKey(nextRow))
if (currentStackOfCells[nextRow].ContainsKey(nextCol)) return false;
return true;
}
A* algorithm
- Iuri Sitinschi September 18, 2015import java.util.Map; import java.util.HashMap; import java.util.Set; import java.util.HashSet; import java.util.Queue; import java.util.PriorityQueue; public class AStar { private Queue<Point> queue; private Map<Integer, Point> points; private Set<Point> visited; private int [][] adjacencyMatrix; private Point end; class Point implements Comparable<Point> { int x; int y; int min; // min distance int hash; // approximate distance to end point Point predeccessor; Point(int x, int y) { this.x = x; this.y = y; min = Integer.MAX_VALUE; if (end != null) { hash = (int) Math.sqrt(Math.pow(x - end.x, 2) + Math.pow(y - end.y, 2)); } } @Override public int compareTo(Point p) { return Integer.valueOf(min + hash).compareTo(p.min + p.hash); } @Override public boolean equals(Object o) { if (o == null || o.getClass() != Point.class) { return false; } Point p = (Point) o; if (x == p.x && y == p.y) { return true; } return false; } @Override public int hashCode() { return 13*x + 23*y; } } public int findShortestPath(int [][] adjacencyMatrix, int x1, int y1, int x2, int y2) { if (adjacencyMatrix == null) { throw new IllegalArgumentException("Matrix is null"); } queue = new PriorityQueue<>(); points = new HashMap<>(); visited = new HashSet<>(); this.adjacencyMatrix = adjacencyMatrix; end = new Point(x2, y2); Point start = new Point(x1, y1); start.min = 0; queue.add(start); points.put(x1*adjacencyMatrix.length + y1, start); Point cur = null; while (!(cur = queue.poll()).equals(end)) { if (!visited.contains(cur)) { visit(cur, cur.x - 1, cur.y); visit(cur, cur.x, cur.y - 1); visit(cur, cur.x, cur.y + 1); visit(cur, cur.x + 1, cur.y); visited.add(cur); } } cur = points.get(x2*adjacencyMatrix.length + y2); // end point int shortestDistance = cur.min; System.out.println("Shortest path: "); while (cur != null) { System.out.print(" (" + cur.x + ", " + cur.y + ")"); cur = cur.predeccessor; } return shortestDistance; } private void visit(Point cur, int i, int j) { if (i >= 0 && i < adjacencyMatrix.length && j >= 0 && j < adjacencyMatrix[0].length && adjacencyMatrix[i][j] != 0) { Point p = points.get(i*adjacencyMatrix.length + j); boolean fUpdate = false; if (p == null) { p = new Point(i, j); fUpdate = true; } else if (cur.min + adjacencyMatrix[i][j] < p.min) { fUpdate = true; queue.remove(p); } if (fUpdate) { p.min = cur.min + adjacencyMatrix[i][j]; p.predeccessor = cur; points.put(i*adjacencyMatrix.length + j, p); queue.add(p); } } } }