CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

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;
}

- kyduke September 16, 2015 | Flag Reply
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);
		heap.add(source);
		
		Map<Integer, Point> map = new HashMap<>();
		map.put(x1*array.length + y1, source);
		heap.add(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);
				visited.add(cur);
			}
			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);
				heap.add(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.

- Iuri Sitinschi September 16, 2015 | Flag Reply
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));
    }
}

- Anonymous September 16, 2015 | Flag Reply
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.

- bharat September 22, 2015 | Flag Reply
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<>();
        Queue<Point> queue = new LinkedList<>();
        queue.add(start);
        previous.put(start, null);

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

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

            List<Point> adjacentPoints = getAdjacentPoints(matrix, point);

            for(Point adjacent : adjacentPoints) {
                if (!previous.containsKey(adjacent)) {
                    previous.put(adjacent, point);
                    queue.add(adjacent);
                }
            }
        }
    }

    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<>();
        deque.addFirst(end);

        Point previous = route.get(end);
        while (previous != null) {
            deque.addFirst(previous);
            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) {
            points.add(new Point(point.x - 1, point.y));
        }
        // right
        if (point.y + 1 < matrix[point.x].length && matrix[point.x][point.y + 1] > 0) {
            points.add(new Point(point.x, point.y + 1));
        }
        // down
        if (point.x + 1 < matrix.length && matrix[point.x + 1][point.y] > 0) {
            points.add(new Point(point.x + 1, point.y));
        }
        // left
        if (point.y - 1 >=0 && matrix[point.x][point.y - 1] > 0) {
            points.add(new Point(point.x, point.y - 1));
        }

        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 + "]";
        }
    }
}

- zaitcev.anton October 27, 2015 | 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