Amazon on site 01/15/2015加油

啊，人生第一次处女面就献给amazon了，周四面的，周日晚上12：00来的拒信。不过拒信来的意料之中，确实自己准备的有问题，有些数据结构没有准备到，又坑爹的遇到三哥，三姐就给跪了。

第一面，一个工作八年的印度大叔，上来就迟到了，让我等了15min，真大牌！第一题，就是给array，找后面最近的比他大的那个数，如果没有找到输出本身。比如说[1,5,3,6,9]，那么output是[5,6,6,9,9]. 因为看过面经，所以很快就给出stack解法，从后往前扫，我在白板给烙印演示，然后烙印看我会，就没叫我写代码。直接问了时间复杂度，我没过脑子，就直接说了 O(n)。然后居然还设个陷阱为难我，说他觉得worst case是O(n方)，因为有可能数组当前那个很大，那么stack就要一直pop到最末尾，比如说[9,1,2,3,4,5,6,7,8]. 陷阱啊，我当时太紧张了，就没多想，被他带沟沟里了。救命啊！

第二面，三姐，然后问的the largest repeating substring。比如banana, 输出ana，然后我不会怎么优化，就只好一个一个substring从大到小得扫，碰到有重复就直接输出，O(n方)。但当时真心想不到了，后来在图书馆才想到可以用binary search扫那个substring长度，这样复杂度能继续降一点。感觉貌似要用到suffix tree来做，以前面经没看到这题和这种数据结构啊！就给三姐跪了。

第三面，图。有user, 每个user有friends，有喜欢的书。就是把某一个user当成root，往下扫，输出它朋友和朋友的朋友...一堆人的书（不重复的），那就直接BFS+HashSet扫了。当场写完面试官比较满意。

第四面，OOP chess。这个就主要和面试官交流了，最后写完了，面试官说good good，照了个相，就带我出去了。
（OOP大家还是多准备几个吧，啥chess,elevator,parking, twitter, hotel reservation, restaurant reservation, traffic signal, chess, furniture和cracking上面的，反正我是都写了一遍，最后幸运的考到了答出来也不慌，推荐一本书java的[size=14.5454540252686px]Cracking The Java Interviews (Java 8), 2nd Edition: Targeted for Investment ,谷歌上面有电子版的，书上有oop一些例子代码和讲解，感觉例子也是amazon常考的，大家可以参考) 。


最后出来的时候，看到那个三姐和一个国人最后出来，我就问他那个三姐出了啥题，他说不是我那道题，这。。面试前在宾馆的晚上还在看AWS的各种组的介绍和最近的新闻，跟面试官聊不会尴尬。感觉自己已经准备的比较充分了，面试的时候也尽力了。天有不测风云啊。已经move on了，相信后面肯定有更好的工作在等我！加油！大家加油!


补充内容 (2015-1-21 16:17):
对了，每轮开始都会问你10min左右的behavior questions，什么most challenging project, tight deadline，get blocked啊啥的，边说面试官都会把你的关键词都敲下来，准备好几个常用段子吧。

鱼吃鱼翅 发表于 2015-1-21 16:06
lz第二题能稍微详细解释一下不？按照你的意思应该输出anana啊？还是我理解的有问题？多谢多谢！

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem
anana只出现了一次，题目说要至少出现两次的longest substring。
Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS
Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG is: No repeated substring
Longest Repeated Substring in ABABABA is: ABABA
Longest Repeated Substring in ATCGATCGA is: ATCGA
Longest Repeated Substring in banana is: ana
Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)

第一题是O(n)吧，从前往后扫，stack存index，如果当前元素比stack[peek()]小，就push，否则，[pop()] = 当前元素值，然后一直pop()到当前元素比stack[peek()]小，再push当前元素。最后留在stack中index的元素没有比它大的。

Cracking The Java Interviews (Java 8), 2nd Edition: Targeted for Investment 这本书，楼主能发一份吗？zhaokai0213@gmail.com

shire1989 发表于 2015-1-21 07:24
lz有这本书的电子版吗?Cracking The Java Interviews (Java 8), 2nd Edition: Targeted for Investment

我也木有，因为每次都是看的在线版本。但是今天突然上去在线的发现后面部分也看不了。

lz有这本书的电子版吗?Cracking The Java Interviews (Java 8), 2nd Edition: Targeted for Investment

三姐问你的题跟去年问我的一模一样， 我当时用 hashmap  做的。她说最好用 suffix tree ， 最后跪了

擦，我觉得自己上，也是挂...
第一题时间复杂度是O(n)吧？
每个元素只会被更改一次。

第一题复杂度究竟是多少呀

第一题用DP可以吗，从后往前扫

浅浅 发表于 2015-1-21 10:24
第一题复杂度究竟是多少呀

记得当时烙印最后说是O(nk)。就是数组所有元素最多只能被pop一次。

cgdong2012 发表于 2015-1-21 08:58
三姐问你的题跟去年问我的一模一样， 我当时用 hashmap  做的。她说最好用 suffix tree ， 最后跪了

握爪握爪，没见过就真心不会啊~~

要求楼主当场建suffix tree??

补充内容 (2015-1-21 11:32):
从build tree开始写code？

补充内容 (2015-1-21 11:32):
从build tree开始写code？

我真心觉得第二题挺难的。