Amazon SDE Interview Opportunity (Software Development Engineer)

Q2是不是只要in order traversal的结果是sorted就说明是binary search tree了？

周一收到。 谢谢LZ

这三个题都跟divide and conquer有关！
无一例外！
第一题先sort，然后用merge sort里面merge的思想做。
第二题有好几种方法，中序遍历，打印出来应该是从小到大。或者用递归的方法做：如果是BST，那么左右都是BST。同事root大于左边最大值，右边最小值。
第三题，典型的divide and conquer，google一下closest pairs。

imwmwm 发表于 2012-9-24 12:33
貌似amazon经典题了 建一个长度为K的最大堆 当插满了以后 只要值小于堆顶 则替换堆顶 然后执行shiftdown
...

我也觉得可以用heap，不过应该是min-heap吧，bacause we are looking for closest points, not farthest points.

中序遍历和递归做法的时间和空间复杂度都是树的大小吧？但是递归貌似要两倍大小

我面了a家onsite也就是这几题。第一题用hashmap找重复就可以，第二题老题，最好办法是min max 范围，只要O(n), 第三题，只要用maxheap做就行，建立heap不要指定大小，为空就可以。然后是O(nlg(k)) 其实就是 O(n)

请问面试的code需要compile通过么？
heap，list，tree这种structure需要自己现写一个还是会提供lib啊？

Same question with 17th Floor

这几道破题，翻来覆去考了n次。不用自己实现数据结构，用就行了。最难也就是深度优先写递归。但是其他问题，比如设计就有些项目经验要求了。