Amazon Interview Misc

https://discuss.leetcode.com/topic/94/binary-tree
Given a Binary Tree. Find a node whose children values' sum is 0.
Remove this sub tree from given binary tree.
http://www.1point3acres.com/bbs/thread-189396-1-1.html
第一轮：三姐，先上来一些behavior问题， 然后是设计一个netflix，跟她确认是OOD还是System design，说先从OO开始，于是就设计了几个class，User, Video, VideoManager 等等，里面有一些方法，然后扩展到DB，缓存优化性能等等。
第二轮， 三哥，先上来一些behavior问题，之后是一个code题目，给一个int数组判断是否有重复数字，心想这个太简单，跟他说了一下思路，准备写code，他说不着急，再加个条件，就是有个K大小的window，打印在每个window里面重复数字的个数，例如数组[1,2,3,2,1,4,5,6], window的大小是5，第一个window 是[1,2,3,2,1], 那么重复个数是2，第二个window是[2,3,2,1,4], 重复个数是1. 思路还是hashtable，右移的时候去掉一个数，再加上一个数，去掉一个数的时候，注意是否去掉了一个重复数字即可。写了code。

第三轮， hiring manager，lunch， 一堆behavior 问题。

第四轮， 白人 + 三哥 shadow, 先上来一些behavior问题，一个coding 题目，有一串DNA序列，就是字符串，比如QAXCDECATDDOG，有个message的单词数组，["CAT", "DOG"], 判断字符串中是否包含数组里面的单词，字符串是通过一个getGene()得到，每次调用这个方法得到一个字母。不停的调用这个方法得到序列。说了一下思路，先构建Trie树，然后开始不停的调用getGene(), 他说思路是对的，写了code，没用让写Trie的实现，有一个bug，经过提示改正。

第五轮， 三哥，这次没有behavior了，上来直接做题，先问了一个two sum， 心想太简单，就假装没见过，给个先排序，双指针的方法，结果小哥不清楚这个solution，解释了一下他才听懂，汗，然后问有没有更好的，正中下怀，抛出hashtable的solution，写了code。第二题，给一个单链表，例如 1,4,2,8,6,7，返回这样一个序列，奇数位是从大到小排列，偶数位从小到大，比如前面的例子要返回，8,1,7,2,6,4, 说了思路,链表从大到小排序, 然后reverse后半段，再用双指针来做，小哥觉得可行就让写了一个reverse 单链表的code。这个时候面试时间已经快到了，但是小哥好像没过瘾， 又出了一道system design的题目，还一个劲的问我后面有没有事情，心里虽然不爽，但是嘴里一直说没事，题目好像是他临时编的，给他现在做的东西有关系，说了十几分钟不知道他想问啥，后来经过讨论，说了下思路，说这个就是他想要的结果，汗。这个时候已经超出面试时间快半个小时了。
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156591&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
滑动窗口求最小  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156373
搜索杨氏表 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156577
矩阵路径最小值的最大值 http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156378
.1point3acres缃�
滑动窗口求最小:

阿色 : 给了一个ArrayList：4, 2, 12, 11, -5，窗口size为2，返回的ArrayList为：2, 2, 11, -5。这里窗口size是一个参数。

Leetcode是求最大.差不多.  https://leetcode.com/problems/sliding-window-maximum/

搜索杨氏表:

霸王祥云: code的确也是新题。但就是leetcode原题Search a 2D Matrix II，相信大家都会做的了，那我就不贴代码了。

Leetcode原题 https://leetcode.com/problems/search-a-2d-matrix-ii/

矩阵路径最小值的最大值:

ymqytw: 给一个int[][]的matirx，对于一条从左上到右下的path p_i，p_i中的最小值是m_i，求所有m_i中的最大值。只能往下或右

http://www.1point3acres.com/bbs/thread-156378-1-1.html
Maximum Minimum Path
给一个int[][]的matirx，对于一条从左上到右下的path p_i，p_i中的最小值是m_i，求所有m_i中的最大值。只能往下或右 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
比如：
[8, 4, 7]
[6, 5, 9]
有3条path：
8-4-7-9 min: 4
8-4-5-9 min: 4
8-6-5-9 min: 5
return: 5
DP:

int helper(int[][] matrix){. visit 1point3acres.com for more.             int[] result = new int[matrix[0].length];             result[0] = matrix[0][0];             for(int i=1; i<matrix[0].length; i++){                     result[i] = Math.min(result[i-1], matrix[0][i]);             }. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷             for(int i=1; i<matrix.length; i++){                     result[0] = Math.min(matrix[i][0], result[0]);                     for(int j=1; j<matrix[0].length; j++){                             result[j] = (result[j]<matrix[i][j] && result[j-1]<matrix[i][j])?Math.max(result[j-1], result[j]):matrix[i][j];.1point3acres缃�                     }             }             return result[result.length-1];. 1point3acres.com/bbs     }

DFS:

1. public class MaximumMinimumPath {
2.         private int min, max, row, col;
3.         public int maxMinPath(int[][] matrix) {
4.                 row = matrix.length;
5.                 col = matrix[0].length;
6.                 min = Integer.MAX_VALUE;. From 1point 3acres bbs
7.                 max = Integer.MIN_VALUE;
8.                 dfsHelper(matrix, min, 0, 0);
9.                 return max;
10.         }
11. 
    
12.         public void dfsHelper(int[][] matrix, int min, int i, int j) {. visit 1point3acres.com for more.
13.                 if (i >= row || j >= col)-google 1point3acres
14.                         return;
15. 
    
16.                 if (i == row - 1 && j == col - 1) {.1point3acres缃�
17.                         min = Math.min(min, matrix[i][j]);
18.                         max = Math.max(max, min);
19.                         return;. visit 1point3acres.com for more.
20.                 }
21.                 min = Math.min(min, matrix[i][j]);.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
22.                 dfsHelper(matrix, min, i, j + 1);.1point3acres缃�
23.                 dfsHelper(matrix, min, i + 1, j);
24.         }
25. }

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=156577&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
  reason始终是我花时间最多的，在此忠告各位一定要把握好时间，我自己在一道题上卡了挺久，最后阅读题做得比较仓促。我卡住的题是{2，8，5，6，8  ？，11}，还是经验不足啊，把这个数组分奇偶来看，{2，5，8，11} {8，6，？}，自然很容易看出来应该填4。 
  另外阅读题考的是给一堆条件决定是否雇佣人那题，以及5男3女选出只是3男1女那题。这两道阅读理解分别有几个小题，建议大家仔细阅读题设，有的题设是要你4个选项找出1个符合要求的，有的题设则是4个选项找出一个invalid的（我自己就没读得太仔细）。而且每一小题答案确认提交后就不能修改了，有题我点的太快，后来又后悔没有仔细看清。

http://hongzheng.me/amazon-oa2/

1. Rectangle Overlap
   判断两个矩形是否重叠
   楼主overlap题研究了好久还是过不了全部的test case,网络上的解都有问题

输入就是两个rectangle，每个rectangle有左上和右下两个点，每个点有x和y两个值
边重合不算重合
return !(bottomRightA.x < topleftB.x || bottomRightB.x < topleftA.x || bottomRightA.y > topleftB.y || bottomRightB.y > topleftA.y);

1. Window Sum
   算k区间内的和
2. Longest Palindrome

第三题

1. Copy List with Random Pointer
   其中copy list里题目中结点描述写的是abritrary，实际上应该是arbitrary…欺负人英语不好？？？
2. Order Dependency
   千万记得要比较Order里的String。因为会有Order1存的是“A”, Order2存的也是“A”。Order 与 Ordername 不是一一对应的。所以单纯比较Order结果肯定是会有一堆重复的A啊B之类的。我15分钟写完，发现不对。5分钟找出来这个问题。然后八分钟改完了。最后交的时候还有两分钟。最后一会儿改bug时候紧张到炸。所以之前准备的时候一定要多考虑。
3. Minimum Spanning Tree
   不能联通返回null，输入不合法返回new 对象，反正这两个你来回调换一下就行

http://hongzheng.me/amazon-oa2-work-simulation/