Start up的面试有点累，题目也都没有很简单的，自我感觉。
4 rounds
第一轮 印度小哥
先问了proj，因为很熟悉，所以从头到尾讲了一遍，小哥做cloud computing,所以对我做的Deep learning项目还是很感兴趣的
Coding: Valid BST（easy）
class Solution {
public boolean isValidBST(TreeNode root) {
Stack<TreeNode> stack = new Stack();
double inorder = - Double.MAX_VALUE;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// If next element in inorder traversal
// is smaller than the previous one
// that's not BST.
if (root.val <= inorder) return false;
inorder = root.val;
root = root.right;
}
return true;
}
}
System Design: 设计一个Gaming System, 要求有不同的游戏，包含其游戏规则，Scoring Interface, Player Interface.
第二轮 白人manager
聊了二十分钟的简历，说了说芝加哥的天气，还有自己想做的岗位，然后面了一道LC 233，数学方法很难想，一步步跟他推导了过程，后来简化成了int < 100, 没有写code, 很快就结束了。
第三轮 之前电面过的中国 Principal AI lead， 一开始自我介绍，后来发现他面过我之后，问了一下之前面试的题目，估计是他自己有一个小题库，不准备出一样的题目了。
Coding 1: Most Trapping Water 1D
class Solution {
public int trap(int[] height) {
if (height.length == 0) return 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int ans = 0;
while (left < right) {
if (height[left] > leftMax) leftMax = height[left];
if (height[right] > rightMax) rightMax = height[right];
if (leftMax < rightMax) {
ans += Math.max(0, leftMax - height[left]);
left++;
} else {
ans += Math.max(0, rightMax - height[right]);
right--;
}
}
return ans;
}
}
Coding 2: Most Trapping Water 2D
public class Solution {
public class Cell {
int row;
int col;
int height;
public Cell(int row, int col, int height) {
this.row = row;
this.col = col;
this.height = height;
}
}
public int trapRainWater(int[][] heights) {
if (heights == null || heights.length == 0 || heights[0].length == 0)
return 0;
PriorityQueue<Cell> queue = new PriorityQueue<>(1, new Comparator<Cell>(){
public int compare(Cell a, Cell b) {
return a.height - b.height;
}
});
int m = heights.length;
int n = heights[0].length;
boolean[][] visited = new boolean[m][n];
// Initially, add all the Cells which are on borders to the queue.
for (int i = 0; i < m; i++) {
visited[i][0] = true;
visited[i][n - 1] = true;
queue.offer(new Cell(i, 0, heights[i][0]));
queue.offer(new Cell(i, n - 1, heights[i][n - 1]));
}
for (int i = 0; i < n; i++) {
visited[0][i] = true;
visited[m - 1][i] = true;
queue.offer(new Cell(0, i, heights[0][i]));
queue.offer(new Cell(m - 1, i, heights[m - 1][i]));
}
// from the borders, pick the shortest cell visited and check its neighbors:
// if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped
// add all its neighbors to the queue.
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int res = 0;
while (!queue.isEmpty()) {
Cell cell = queue.poll();
for (int[] dir : dirs) {
int row = cell.row + dir[0];
int col = cell.col + dir[1];
if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col]) {
visited[row][col] = true;
res += Math.max(0, cell.height - heights[row][col]);
queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height)));
}
}
}
return res;
}
}
中间一直没有休息，所以我让第三轮的面试官给了我十分钟的Break, 去喝了一点水
第四轮：
一个白人manager,一个中国工程师shadow
问了非常多的BQ，包括我在实习期间，是怎么解决问题，自我解决问题，跟manager怎么相处的。
Coding: 2D array, validate 是否里面有长方形， 有的返回 左上，右下坐标，和width&height
一开始我是准备找到leftMost， rightMost, 然后walking alongside the border去validate 长方形， 中间跟面试官validate了input是否有hole，就是以下这种输入
1 1 1
1 0 1
1 1 1
后来面试官简化了问题，说就是有一个valid的长方形，返回，x,y,r,c和w，h就可以了