Status: New grad, MS CS Top 30 CS school
Position: Software engineer intern at Dropbox
Location: San Franscisco, CA
Technical phone screen (1 hour):
- Behavioral questions : what was most chanllenging part in your project?
- Algorithm question
INPUT:
You’re given an elevation map for a rectangular area of land. The map is represented by 2-D array of numbers where each cell contains the elevation above sea level of the corresponding area of the map.
DEFINITION OF A VALID PATH:
Informal definition: Cat Davy is on the left edge of the map. He will like to move to the right edge of the map. He can only move in single cell steps east, southeast, or northeast. He is not allowed to move north or south within the same column. Any path that Cat Davy can take is called a valid path.
B
AC
D
Formal definition: A path is valid if and only if
(1) It contains exactly one cell in each column.
(2) Let cell A and cell B be cells belonging to the path in adjacent columns. Then cell A and cell B must share either a corner or an edge.
Example of valid paths
…X … X… …
.XX. … .X… .X…
X… XXXX …X. X.XX
… … …X …
Example of invalid paths
.XXXX .XXX … … .X…
.X… .X… XX.X .X… …
.XXX. .X… … …X. X.XX
…X. XX… … …X …
XXXX.
DEFINITION OF A BLOCKED PATH:
A path is blocked if and only if there exists a cell in the path such that its height is less or equal to the current sea level.
PROBLEM:
You need to find the minimum sea level rise required to block all valid paths. Write a function that takes in a 2-D array of numbers and returns that single number.
CONSTRAINTS:
Each cell’s elevation is an integer between 0 and 1000000000000000000 (10^18).
You are not given the runtime of the intended solution. Please find the best possible runtime.
TEST CASES:
For all sample test cases below, each cell’s elevation is an integer between 0 and 9.
Test case 1:
666
666
666
Correct answer: 6
Explanation: You are given a piece of land with 9 square cells in a 3 by 3 layout. Each cell has elevation of 6. The sea level must rise to 6 before it can block all paths.
Test case 2:
11999
91199
99119
99911
Correct answer: 1
Explanation: Once the sea level rises to 1, then all cells with a height of 1 are submerged. These submerged cells will block any valid path.
Test case 3:
19999
19111
19991
11191
99991
Correct answer: 1
Explanation: An S-shaped path is not a valid path.
Test case 4:
199
191
191
991
Correct answer: 1
Explanation: You cannot move vertically within the same column.
Test case 5:
3124
5718
3946
Correct answer: 4
Test case 6:
922
111
555
Correct answer: 5
Test case 7:
199
191
991
Correct answer: 9
Test case 8:
3199
5718
3846
Correct answer: 5
My answer:
class Solution {
public static int sealevel(int[][] grid) {
if (grid.length == 0) return 0; //empty
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n]; //dp array for size m, n
//simplest case : only one column, one line, one cell in total
dp[0][0] = grid[0][0];
int tmp = dp[0][0];
//when multiple lines, will be the maximal value
for (int i = 1; i < m; i++) {
if (tmp < grid[i][0]) {
tmp = grid[i][0];
dp[i][0] = tmp;
}
}
//then expand right-ward, second column to right bound
for (int j = 1; j < n; j++) {
for (int i = 0; i < m; i++) {
//get dp[i][j] from dp[i-1][j]: reachable cells
if (i == 0) {
if (grid[i][j] > dp[i][j-1]) dp[i][j] = dp[i][j-1]
else dp[i][j] = grid[i][j];
}
//find out the path with maximal minimal value
//first possiblility: it could be dp[i-1][j]
//second possibility: second last grid[i-1][j-1] -> last: grid[i][j]
//third: second last grid[i][j-1] -> last: grid[i][j]
//fourth: second last grid[i][j-1] -> last: grid[i-1][j]
//we only need to compare and find out the max
dp[i][j] = max(dp[i-1][j],
min(grid[i][j],dp[i-1][j-1]),
min(dp[i][j-1], grid[i][j]),
min(dp[i][j-1], grid[i-1][j])
);
}
}
return dp[m][n];
}