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,然后比一下