Amazon Online Assessment

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

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

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

第二题是shuffle问题。A B C D四个整数，怎样排列可以使得abs(s1-s2)+abs(s2-s3)+abs(s3-s4)的值最小。s1-s4是重新排列后的整数。要求O（1）复杂度。我用了vector存了abcd，然后sort（），每次取vector最大和最小值，按序存到新vector里面。用了两个case测试了下，提示结果正确。

2，20道  Reasoning题（45min）
全部是选择题，有找出数量关系的，有逻辑推导的，阅读量很大，自己感觉做得不是很好。踩着点提交了。

3，200道性格测试（15min）
没错，是200道，做得头都晕了，给你一个描述性句子：比如说“我喜欢攀岩。”，然后选择true/false.很多重复或相似的描述，做得累人。

4，对assessment评价
. visit 1point3acres.com for more.上面三个部分做完了，可以做一下评价。可能是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两段长
不知我说的对不对