## Facebook Interview Question for SDE1s

Country: United States

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

use DP
traverse from left to right and up to down.
cost[i][j]= min(cost[i-1][j] + possible_cost, cost[i][j-1] + possible_cost)
got it at last.

start from right bottom, use the cost value to get the previous point (either [i-1][j] or [i][j-1]) and print it. do it iteratelly to reach the start point.

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

``````public int minCost(final int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return -1;
}

for (int x = 1; x < matrix[0].length; ++x) {
matrix[0][x] = Math.max(matrix[0][x], matrix[0][x - 1]);
}
for (int y = 1; y < matrix[0].length; ++y) {
matrix[y][0] = Math.max(matrix[y][0], matrix[y - 1][0]);
}

for (int y = 1; y < matrix.length; ++y) {
for (int x = 1; x < matrix[0].length; ++x) {
matrix[y][x] = Math.max(matrix[y][x], Math.min(matrix[y][x - 1], matrix[y - 1][x]));
}
}
return matrix[matrix.length - 1][matrix[0].length - 1] - matrix[0][0];
}

public List<int[]> shortestPath(final int[][] matrix) {
int minPath = minCost(matrix);
if (minPath == -1) {
return null;
}

List<int[]> path = new ArrayList<>(matrix.length + matrix[0].length - 1);
int x = matrix[0].length - 1;
int y = matrix.length - 1;

while (x != 0 || y != 0) {
if (x > 0 && y > 0) {
if (matrix[y - 1][x] > matrix[y][x - 1]) {
--x;
} else {
--y;
}
} else if (x > 0) {
--x;
} else {
--y;
}
}
return path;
}

private void addPath(final List<int[]> path, final int x, final int y) {
}``````

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

Old good Dijkstra

``````import java.util.*;

class RobotPaths {

final int[][] heights;
final int M;
final int N;

RobotPaths(int[][] heights) {
this.heights = heights;
N = heights.length - 1;
M = heights[0].length - 1;
END = new Node(N, M);
}

final Node ORIGIN = new Node(0, 0);
final Node END;

class Node {
final int x;
final int y;

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

int height() {
return heights[x][y];
}

List<Node> neighbours() {
List<Node> n = new ArrayList<>();
if (x < N) {
}
if (y < M) {
}
if (x > 0) {
}
if (y > 0) {
}
return n;
}

public boolean equals(Object that) {
Node p2 = (Node)that;
return x == p2.x && y == p2.y;
}

public int hashCode() {
return x << 16 + y;
}

public String toString() {
return String.format("[%d, %d]", y, x);
}
}

int cost(Node from, Node to) {
return Math.max(to.height() - from.height(), 0);
}

class Solution {
List<Node> minPath;
int minCost;

Solution(List<Node> minPath, int minCost) {
this.minPath = minPath;
this.minCost = minCost;
}
}

Solution findShortest() {
Map<Node, Integer> costMap = new HashMap<>();
Map<Node, Node> prevMap = new HashMap<>();
Comparator<Node> comp = new Comparator<Node>() {
public int compare(Node n1, Node n2) {
int i1 = costMap.getOrDefault(n1, Integer.MAX_VALUE);
int i2 = costMap.getOrDefault(n2, Integer.MAX_VALUE);
return i1 - i2;
}
};
List<Node> todo = new ArrayList<>();
costMap.put(ORIGIN, 0);
while (!todo.isEmpty()) {
Node curr = todo.remove(0);
Integer currCost = costMap.get(curr);
for (Node n : curr.neighbours()) {
if (!costMap.containsKey(n)) {
}
Integer prevCost = costMap.getOrDefault(n, Integer.MAX_VALUE);
int newCost = cost(curr, n) + currCost;
if (newCost < prevCost) {
costMap.put(n, newCost);
prevMap.put(n, curr);
}
}
Collections.sort(todo, comp);
}
Node curr = END;
while (curr != ORIGIN) {
curr = prevMap.get(curr);
}
return new Solution(res, costMap.get(END));
}

static final int[][] heights1 = {
{ 0, 1, 2, 3, 4 },
{ 1, 0, 3, 4, 5 },
{ 2, 1, 0, 5, 6 },
{ 3, 4, 1, 0, 7 },
{ 4, 5, 6, 1, 0 }
};

static final int[][] heights2 = {
{ 0, 1, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0 }
};

static final int[][] heights3 = {
{ 0, 1, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 1, 0, 1, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 1, 0 }
};

public static void main(String[] args) {
assertEquals(new RobotPaths(heights1).findShortest().minCost, 4);
assertEquals(new RobotPaths(heights2).findShortest().minCost, 0);
assertEquals(new RobotPaths(heights3).findShortest().minCost, 0);
}

static void assertEquals(int n1, int n2) {
if (n1 != n2) {
throw new AssertionError("found " + n1 + " expected " + n2);
}
}
}``````

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

Isn't this just min-path in a weighted graph? Use Dijkstra's algorithm.

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.