Facebook Interview Question for SDE1s


Country: United States




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

public static void main(String[] args) {
		String[] game = {"########", "#@....G#", "##.##@##", "#..@..S#", "#@.....#", "########"};
		System.out.println(shortestDist(game));

	}

	public static int shortestDist(String[] game) {

		int Sx = -1;
		int Sy = -1;
		int orient = 0;
		char[][] arr = new char[game.length][game[0].length()];
		for (int i = 0; i < game.length; i++) {
			for (int j = 0; j < game[0].length(); j++) {
				arr[i][j] = game[i].charAt(j);
				if (arr[i][j] == 'S') {
					Sx = i;
					Sy = j;
				}
				if (arr[i][j] == '@') {
					orient += 1;
				}
			}
		}

		int[] min = new int[1];
		min[0] = Integer.MAX_VALUE;
		List<String> nodes = new ArrayList<String>();
		nodes.add(Sx + ":" + Sy);
		shortestDistance(arr, 0, min, Sx, Sy, arr.length - 1, arr[0].length - 1, nodes, orient);
		return min[0];
	}

	// n = length-1
	public static int shortestDistance(char[][] game, int step, int[] min, int x, int y, int n, int m,
			List<String> nodes, int orient) {
		if (x < 0 || y < 0 || x > n || y > m)
			return step;

		if (game[x][y] == '#')
			return step;

		if (game[x][y] == 'G'&& orient <= 0) {
			min[0] = Math.min(min[0], step);
			return step;
		}

		int[] v = { 1, 0, -1, 0 };
		int[] h = { 0, 1, 0, -1 };

		for (int i = 0; i < 4; i++) {
			String uf = (x + v[i]) + ":" + (y + h[i]);
			if (!nodes.contains(uf)) {
				nodes.add(uf);
				if(x + v[i] >= 0 && y + h[i] >= 0 && x + v[i] < n && y + h[i] < m &&  game[x + v[i]][y + h[i]] == '@'){
					orient -= 1;
				}
				shortestDistance(game, step + 1, min, x + v[i], y + h[i], n, m, nodes, orient);
				nodes.remove(uf);
			}
		}
		return step;
	}

- sudip.innovates September 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it's a duplicate question, but I feel honored, it was adapted with this map representation ;-)
Actually it is NP hard and constist of two parts:
- find the shortest distances among all "@", S and G --> all pair shortest path on a map.
- find the shortest route between S and G while visiting each "@". Think of all the "@" as cities and imagine the distances among the cities were already calculated. It's clear there are count(@)! (factorial) options. It's as well clear if you calculated the shortest path properly, the triangle inequality holds. There are many approximation algorithms to the problem you can use then. But the exact solution is NP-hard.

- Chris September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@majia168: what was your experience with this question?

- Chris September 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is a NP-hard problem, which is a famous problem called TSP problem. The main idea is that find all the @, and construct distance 2D array to represent the distance between different @s, and then use backtracking algorithm to get the final answer. If we just use dfs, and the time complexity is O(N!), but if we add DP algorithm, and then the time complexity if O(2^N)

- tiandiao123 September 30, 2017 | 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