## Amazon Interview Question for SDE-2s

Country: United States

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

C++, A* algorithm

``````#include <iostream>
#include <vector>
#include <map>

using namespace std;

int cityBlockDistance(pair<int, int> a, pair<int, int> b) {
int x, y;

x = a.first - b.first;
if (x < 0) x = -x;
y = a.second - b.second;
if (y < 0) y = -y;

return x + y;
}

vector<pair<int, int>> findPathAStar(vector<vector<int>> original, pair<int, int> start, pair<int, int> end) {
vector<vector<int>> matrix;
vector<pair<int, int>> path;
multimap<int, pair<pair<int, int>, vector<pair<int, int>>>> candidate;
multimap<int, pair<pair<int, int>, vector<pair<int, int>>>>::iterator it;
pair<int, int> p;
int x, y, w, h;

matrix = original;

matrix[start.second][start.first] = 0;
path.push_back(start);
candidate.insert(make_pair(cityBlockDistance(start, end), make_pair(start, path)));

h = matrix.size() - 1;
w = matrix[0].size() - 1;
while (candidate.size()) {
it = candidate.begin();
p = it->second.first;
x = p.first;
y = p.second;

if (x == end.first && y == end.second) {
return it->second.second;
}

if (x > 0 && matrix[y][x - 1] == 1) {
p = make_pair(x - 1, y);
matrix[y][x - 1] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
if (x < w && matrix[y][x + 1] == 1) {
p = make_pair(x + 1, y);
matrix[y][x + 1] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
if (y > 0 && matrix[y - 1][x] == 1) {
p = make_pair(x, y - 1);
matrix[y - 1][x] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
if (y < h && matrix[y + 1][x] == 1) {
p = make_pair(x, y + 1);
matrix[y + 1][x] = 0;
path = it->second.second;
path.push_back(p);
candidate.insert(make_pair(cityBlockDistance(p, end), make_pair(p, path)));
}
candidate.erase(it);
}

path.clear();
return path;
}

int main(int argc, char* argv[]) {
int data[10][10] = {
{0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 1, 1, 1},
{0, 0, 1, 1, 1, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 0, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
vector<pair<int, int>> path;
vector<vector<int>> matrix;
vector<int> row;
int i;

for (i = 0; i < 10; i++) {
row.clear();
row.assign(data[i], data[i] + 10);
matrix.push_back(row);
}

path = findPathAStar(matrix, make_pair(1, 1), make_pair(8, 8));
for (i = 0; i < path.size(); i++) {
cout << path[i].first << ", " << path[i].second << "\n";
}

return 0;
}``````

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

``````import java.util.Map;
import java.util.Set;
import java.util.Queue;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.lang.Comparable;

public class Dijkstra {

class Point implements Comparable<Point>{
int x;
int y;
int min;
Point predeccessor;

Point(int x, int y) {
this.x = x;
this.y = y;
min = Integer.MAX_VALUE;
predeccessor = null;
}

@Override
public int compareTo(Point p) {
if (min < p.min) {
return -1;
} else if (min > p.min) {
return 1;
} else {
return 0;
}
}

@Override
public boolean equals(Object o) {
if (o != null && o.getClass() == Point.class) {
Point point = (Point) o;
if (this.x == point.x && this.y == point.y) {
return true;
}
}

return false;
}

@Override
public int hashCode() {
return 13*x +23*y;
}
}

public void printShortestPath(int [][] array, int x1, int y1, int x2, int y2) {
Queue<Point> heap = new PriorityQueue<>();
Point source = new Point(x1, y1);
source.min = 0;
Point dest = new Point(x2, y2);

Map<Integer, Point> map = new HashMap<>();
map.put(x1*array.length + y1, source);
Set<Point> visited = new HashSet<>();
Point cur = null;
while (!(cur = heap.poll()).equals(dest)) {
if (!visited.contains(cur)) {
visit(cur, array, cur.x - 1, cur.y, map, heap);
visit(cur, array, cur.x, cur.y - 1, map, heap);
visit(cur, array, cur.x, cur.y + 1, map, heap);
visit(cur, array, cur.x + 1, cur.y, map, heap);
}
if (heap.isEmpty()) {
System.out.println("Point are not connected!");
return;
}
}

cur = map.get(x2*array.length + y2);
while (cur != null) {
System.out.println("(" + cur.x + ", " + cur.y + ")");
cur = cur.predeccessor;
}
}

private void visit(Point cur, int [][] array, int i, int j, Map<Integer, Point> map, Queue<Point> heap) {
if (i >= 0 && i < array.length && j >= 0 && j < array[0].length && array[i][j] != 0) {
Point p = map.get(i*array.length + j);
boolean fUpdated = false;
if (p == null) {
p = new Point(i, j);
p.min = cur.min + array[i][j];
fUpdated = true;
} else if (p.min > cur.min + array[i][j]) {
p.min = cur.min + array[i][j];
heap.remove(p);
fUpdated = true;
}
if (fUpdated) {
p.predeccessor = cur;
map.put(i*array.length + j, p);
}
}
}

public static void main(String [] args) {
int [][] array = new int [][] {
{0,0,0,1,0,1},
{0,0,0,1,0,1},
{1,1,1,1,0,1},
{0,0,1,1,0,1},
{0,1,1,1,0,1},
{1,1,0,1,0,1},
{1,1,0,1,0,1}
};

Dijkstra dijkstra = new Dijkstra();
dijkstra.printShortestPath(array, 6, 0, 0, 3);
}

}``````

O(NxM) space. Quadratic time complexity because of heap.remove(p) (is liniar). If implement own version of min-heap with ability to update priority, algorithm becomes linearithmic.

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

``````public class Path2DArray {

private static class Location {
int x;
int y;

public Location(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj) {
Location loc = (Location) obj;
return this.x == loc.x && this.y == loc.y;
}

@Override
public String toString() {
return "(" + x + "," + y + ")";
}
}

public void printPath(int[][] input, Location origin, Location destination) {
boolean[][] visited = new boolean[input.length][input[0].length];
pathUtil(input, visited, origin, destination, "");
}

private void pathUtil(int[][] input, boolean[][] visited, Location current, Location destination, String path) {
if (current.equals(destination)) {
path += destination.toString();
System.out.println(path);
return;
}

int x = current.x;
int y = current.y;
visited[x][y] = true;
path += current.toString();
int row = visited.length;
int col = visited[0].length;
if (x - 1 >= 0 && y - 1 >= 0 && !visited[x - 1][y - 1] && input[x - 1][y - 1] == 1)
pathUtil(input, visited, new Location(x - 1, y - 1), destination, path);
if (x - 1 >= 0 && y + 1 < col && !visited[x - 1][y + 1] && input[x - 1][y + 1] == 1)
pathUtil(input, visited, new Location(x - 1, y + 1), destination, path);
if (x + 1 < row && y - 1 >= 0 && !visited[x + 1][y - 1] && input[x + 1][y - 1] == 1)
pathUtil(input, visited, new Location(x + 1, y - 1), destination, path);
if (x - 1 >= 0 && !visited[x - 1][y] && input[x - 1][y] == 1)
pathUtil(input, visited, new Location(x - 1, y), destination, path);
if (x + 1 < row && !visited[x + 1][y] && input[x + 1][y] == 1)
pathUtil(input, visited, new Location(x + 1, y), destination, path);
if (y + 1 < col && !visited[x][y + 1] && input[x][y + 1] == 1)
pathUtil(input, visited, new Location(x, y + 1), destination, path);
if (y - 1 > 0 && !visited[x][y - 1] && input[x][y - 1] == 1)
pathUtil(input, visited, new Location(x, y - 1), destination, path);
if (x + 1 < row && y + 1 < col && !visited[x + 1][y + 1] && input[x + 1][y + 1] == 1)
pathUtil(input, visited, new Location(x + 1, y + 1), destination, path);
}

public static void main(String[] args) {
int[][] input1 = {
{0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 0, 0, 1, 0, 1, 0, 0, 0},
{0, 1, 1, 0, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 1, 0, 0, 1, 1, 1},
{0, 0, 1, 1, 1, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 0, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

int[][] input2 = {
{0,0,0,1,0,1},
{0,0,0,1,0,1},
{1,1,1,1,0,1},
{0,0,1,1,0,1},
{0,1,1,1,0,1},
{1,1,0,1,0,1},
{1,1,0,1,0,1}
};

Location origin = new Location(1,1);
Location destination = new Location(8,8);

Path2DArray path2DArray = new Path2DArray();
path2DArray.printPath(input1, origin, destination);

path2DArray.printPath(input2, new Location(6,0), new Location(0,3));
}
}``````

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

Treat the given matrix as graph where a point will have a connection to its neighbours iff the adjacent point is 1. Using BSF/DSF we can find the path from given point to other point.

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

Simply use DFS to find shortest path on un-weighted graph represented by 2d array

``````public class ShortestPath {
private Collection<Point> path;

public ShortestPath(int[][] matrix, Point start, Point end) {
Map<Point, Point> previous = new HashMap<>();
previous.put(start, null);

while (!queue.isEmpty()) {
Point point = queue.poll();

if (point.equals(end)) {
path = calculatePath(previous, end);
break;
}

}
}
}
}

public Collection<Point> getPath() {
return path != null ? Collections.unmodifiableCollection(path) : Collections.emptyList();
}

private Collection<Point> calculatePath(Map<Point, Point> route, Point end) {
Deque<Point> deque = new ArrayDeque<>();

Point previous = route.get(end);
while (previous != null) {
previous = route.get(previous);
}

return deque;
}

private List<Point> getAdjacentPoints(int[][] matrix, Point point) {
List<Point> points = new ArrayList<>();
// up
if (point.x - 1 >= 0 && matrix[point.x - 1][point.y] > 0) {
}
// right
if (point.y + 1 < matrix[point.x].length && matrix[point.x][point.y + 1] > 0) {
}
// down
if (point.x + 1 < matrix.length && matrix[point.x + 1][point.y] > 0) {
}
// left
if (point.y - 1 >=0 && matrix[point.x][point.y - 1] > 0) {
}

return points;
}

static class Point {
final int x;
final int y;

Point(int x, int y) {
this.x = x;
this.y = y;
}

public int hashCode() {
return 7 * x + 13 * y;
}

public boolean equals(Object other) {
if (other == null) return false;
if (other == this) return true;

if (other instanceof Point) {
Point o = (Point) other;
return this.x == o.x && this.y == o.y;
}

return false;
}

public String toString() {
return "[" + x + "," + y + "]";
}
}
}``````

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.