amazon intern 1.19 (offer get)

刚面的amazon 后来查他linkedin 哥大cs的印度小哥 data什么组的。。。口音挺重的。。。
自我介绍 我说我data structure/algorithms自学的 转专业来的（装弱大法好。。。没装。。。本来就弱。。。然后他就没问我projects 让我讲我知道的data structure越多越好
然后他问我学没学过操作系统= = 说了no不知道他会不会介意。。。
then coding
第一题：
follow up: in-place
第二题：口述 没写代码 BST retrieve的时间复杂度 好吧O(lgN) then worst-case？我觉着这不还是O(lgN)吗 听他语气有点质疑。。。我又猜O(n)？然后他让我举个例子 卧槽。。。蒙圈儿了 后来他一步一步引导 1(root) 2 3 4 形成一个bst咋弄。。。然后worst case是啥 蠢如我终于懂。。。好吧O(n) 然后他问我如何改进 卧槽这不sorted array to bst吗 然后就blablabla 问要不要写代码 他说不用
第三题：
我用dfs一层一层写的 他没看懂让我

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

通过OA
02/10/2016 约电面邮件get 没有HR
02/16/2016 2:00PM PST final round 电面
催了两次
03/10/2016 EST 凌晨十二点左右offer get


很庆幸OA和约电面这两个环节A没有任何拖延 等offer期间我比他还急= = anyway 赶上了A今年招实习的末班车
事实证明 跟Amazon一定不要拖 因为只可能它比你更拖 然后时机就很容易错过了

william_gong 发表于 2016-1-19 22:19
能说下dfs的思路吗？

需要一个void helper(result, node, depth)
if depth == result.size() - 1 创建一个新的list存入这个node.val 并把这个list append到result里
else result.get(depth - 1).add(node.val) //result里上一层的末端插入这个元素
然后再recurse左右node
在主函数(不是main)里面就用helper(result, root, 1)来改变result 然后返回result
注意corner cases

我觉着这种做法挺有意思的 不想拘泥于常规 zigzag那题也可以这样解 当然bfs也都行

恭喜楼主终于面完了呀～

你遇到的这个三哥感觉已经算好的了，只出了这么简单的三道题给你答。

第二题我觉得他应该想让你答Red-Black Tree那种balanced的方法，每插一个节点都立刻平衡一下整个树。当然你那样也可以，直接解释到他能理解意思就行。

第三题他可能想让你用queue来写标准的BFS，如果他没见过你那种解法，他的确有可能误以为你DFS，BFS不分。不过你能解释清楚就行。

最后祝咱俩都好运啦，希望都能拿到offer~

victorsterling 发表于 2016-1-26 09:47
话说第一题inplace怎么写的呢？我用s.split()是不是就算in place了？还是说只要space complexity是constant ...

split当然不是inplace啊 用了一个新的list。。。
Reverse the whole sentence, then reverse each word. Use the spaces as the separation to indicate start/end index of word. Pay attention to the final word.

第2题，如果tree是单向的。。应该是o(n)。。
比如长这样的。搜5是worst case。。
1
2
  3
   4
     5

xiaozhuxiaozhu 发表于 2016-1-19 18:39
第2题，如果tree是单向的。。应该是o(n)。。
比如长这样的。搜5是worst case。。
1

没错。。。

candy_shmily 发表于 2016-1-20 07:41
没错。。。

offer在路上了。。
我要是能提前看到你的帖子，我可能还有戏。

xiaozhuxiaozhu 发表于 2016-1-19 18:43
offer在路上了。。
我要是能提前看到你的帖子，我可能还有戏。

why
咱俩题一样吗 我两点面的 也没法早点发

candy_shmily 发表于 2016-1-20 07:44
why
咱俩题一样吗 我两点面的 也没法早点发

哎，稳了。求沾点喜气

candy_shmily 发表于 2016-1-20 07:44
why
咱俩题一样吗 我两点面的 也没法早点发

不一样，我周5面的。
感觉你态度比较好。。我后来觉得，我面试时候的态度是，“面试官，你是傻x么。。”。。

好吧O(n) 然后他问我如何改进 卧槽这不sorted array to bst吗

LZ能详细说吗 谢谢啦

letsdoit666 发表于 2016-1-19 18:59
哎，稳了。求沾点喜气

没。。。我解释成了一坨shit。。。而且不是说印度小哥会坑中国人吗。。。怕怕的
顾神妥妥的！

xiaozhuxiaozhu 发表于 2016-1-19 19:00
不一样，我周5面的。
感觉你态度比较好。。我后来觉得，我面试时候的态度是，“面试官，你是傻x么。。” ...

你水平高呀！每次看到你写的代码我就酱紫
我要是水平能有你一半儿我就骄傲了= =