Amazon 12.7 实习电面面经

感觉地里Amazon的面经好少，贡献一个刚刚电面完的。
电话是个三哥打来的，电话那边声音很吵，他口音又很难懂，基本他说一句我得问三四遍才能懂。。
好吧，吐槽结束，下面是干货

Q1. Given BST, convert it in such a way every element now contains the sum of elements >= itself
题目是要算所有比它大的数的和，覆盖自己的value field。
我一开始是递归做，找到最右边的点，然后把算好的值返回上去，上面的点只要加上这个值就行了。
然后他说不错，但递归space复杂度大，换个做法。
我说用iterative的方法，然后刚写完stack，他说这个还是太大，把我代码删了。。
然后我就蒙了，心想是不是morris traverse之类的方法，然而并不会。。就说没什么想法，他就下一题了。

Q2. You are given a Single linked list, with every node having a character as a value. You need to check if it is palindrome.
这个好像leetcode上面有，就是先reverse linked list，然后比一下

BST是有序的.应该是inorder traversal但是从高到低这样走, 然后存累加和吧.

补充内容 (2015-12-8 07:50):
面试考Morris的概率不大.表示也不知道面试官在期待什么....

补充内容 (2015-12-8 07:50):
面试考Morris的概率不大.表示也不知道面试官在期待什么....

应该是postorder，然后只要存一个temp variable，一直累加就可以了吧。。

lz oa还是那7道改错题么？
实习是只有1轮电面么。

第一题啥意思啊？

补充内容 (2015-12-8 08:00):
http://www.geeksforgeeks.org/convert-bst-to-a-binary-tree/   ？？？？

hohojoy 发表于 2015-12-8 07:55
应该是postorder，然后只要存一个temp variable，一直累加就可以了吧。。

对啊，postorder最好做。

补充内容 (2015-12-8 08:20):
别听我的。

第2题，其实如果没刷题，一般人的做法就是先读一变linked list，然后把每个char放道一个array里面，然后查是不是palindrome.
但是刷题以后，知道的做法是，用2个pointer，fast比慢的走快2倍，然后用慢的找到中点，然后同时比较head到中点，和中点到终点的每一个val是不是相等。
第2中做法比第一个剩空间。

补充内容 (2015-12-8 08:12):
只reverse中点到终点那一部分。

第2题，leetcode标的是easy，但是如果按照要求，Could you do it in O(n) time and O(1) space?
这题基本是medium的。

xiaozhuxiaozhu 发表于 2015-12-8 07:57
lz oa还是那7道改错题么？
实习是只有1轮电面么。

对的，7道改错，实习是1轮电面，邮件里面说了这是最后的面试

xiaozhuxiaozhu 发表于 2015-12-8 07:59
第一题啥意思啊？

补充内容 (2015-12-8 08:00):

就是这道题

excellent5 发表于 2015-12-8 08:16
对的，7道改错，实习是1轮电面，邮件里面说了这是最后的面试

. Waral 博客有更多文章,lz肯定有offer,感觉amazon题很简单。
希望自己也能遇到这样的题。

leonidas1573 发表于 2015-12-8 07:49
BST是有序的.应该是inorder traversal但是从高到低这样走, 然后存累加和吧.

补充内容 (2015-12-8 07:50):

嗯，我做法也是inorder traversal，从最右边最大的开始找，这样的话相当于按数字顺序从大到小找。

excellent5 发表于 2015-12-8 08:19
嗯，我做法也是inorder traversal，从最右边最大的开始找，这样的话相当于按数字顺序从大到小找。

这个叫postorder..或者reverse inorder ＝ ＝

补充内容 (2015-12-8 08:20):
是reverse inorder.不是postorder.

hohojoy 发表于 2015-12-8 07:55
应该是postorder，然后只要存一个temp variable，一直累加就可以了吧。。

为何是postorder。。如果是按照数字大小遍历不应该是inorder吗

excellent5 发表于 2015-12-8 08:20
为何是postorder。。如果是按照数字大小遍历不应该是inorder吗

我想打reverse inorder.脑袋短路。写成post了

excellent5 发表于 2015-12-8 08:20
.留学论坛-一亩-三分地为何是postorder。。如果是按照数字大小遍历不应该是inorder吗

sorry。。。。想说先右再左～结果就顺口说成postorder了。。 这样是O（h）。。 能有更好的解法？

xiaozhuxiaozhu 发表于 2015-12-8 08:20
这个叫postorder..或者reverse inorder ＝ ＝

补充内容 (2015-12-8 08:20):

这两个确实不一样，以前都没注意过。

祝楼主好运拿offer!

excellent5 发表于 2015-12-8 08:16
对的，7道改错，实习是1轮电面，邮件里面说了这是最后的面试

求问楼主面试是phone还是skype呀？谢谢

小A要当码农 发表于 2015-12-8 11:38
求问楼主面试是phone还是skype呀？谢谢

phone interview