Amazon Online Assessment

上周四刚做完
虽然开始测试时候有个保密协议，我点了agree。。。。但是为了大家，还是拿出来分享下。求祝福~

跟之前的形式有很大变化。

1，两道编程题（1hr30min）
第一题是设计一个函数可以返回树的每条路径的波幅。所谓波幅就是路径上所有节点的值的最大差值。要求复杂度为O（N）。我用了recursion，遍历左右两边子树，把每次的结果存在static vector里，最后找出答案。可以自己键入test case，我用了两个case 测试了下，都显示正确。

第二题是shu

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

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

完了，可以做一下评价。可能是Amazon刚换了测试环境，需要feedback。我写了测试时间太长，希望缩短测试时间。。。。。

PS：每个部分之间可以停顿，去洗手间啥的都行，但是一旦开始某个部分的测试则不能暂停。

还没收到结果，求on site~~~

我觉得你第二题打错了吧 是取最大值不是最小值

第一题路径的起点可以不是root吧 但是function的输入是什么？不太明白 不过感觉解法应该跟Leetcode Binary Tree Maximum Path Sum很像
第二题 O(1) 难道是因为N是4的缘故？ 能举个例子吗 谢谢

lhn9021 发表于 2014-4-15 08:02
第一题路径的起点可以不是root吧 但是function的输入是什么？不太明白 不过感觉解法应该跟Leetcode Binary  ...

路径可以不是起点，参数是root。

O（1）我个人认为应该是只有4个数的缘故。参数就是abcd四个数

补充内容 (2014-4-15 09:09):
打错了，路径起点可以不是root

shuffle 你是什么思路，  O(1) 怎么理解？

第二题 shuffle， 每次取最大最小值， 然后按序放到vector里，貌似会忽略一些情况吧。

比如 3， 15， 7， 12 -> 15, 3, 12, 7
       3， 15 ， 7， 9 ->  3, 15, 7, 9
最后那个vector的顺序是不一样的。

学长我也打算去WUSTL的EE，请问一下你们这一届的就业情况怎么样？去了转CS好转么？跪谢！！！！！

感觉大家对第二题理解很混乱呀。 一共就4个数， 怎么可能不是O(1) 时间复杂度呢？
我看完他的题，在纸上画了一下 ， 一条线 ，4个点， 求距离之和的最小值。 很明显就是每个interval 之间没有overlap的即为最小。所以就是把四个点排序，
abs(s[i] - s[i + 1]) 就是结果。 LZ 不知道我理解错没？

请问第二题是求最大还是最小啊，如果是最小当然是ab,bc,cd（a<b<c<d)之和最小
如果是最大应该是|d-a|+|a-c|+|c-b|和|a-d|+|d-b|+|b-c|之中选取一个，那就要比较ac和bd两段长
不知我说的对不对