f*****e
发帖数: 210 | 1 周末做了amazon online test 的题。我是非CS专业，所以很怕碰到没接触过的概念。
online test 应该是最简单的了。
1.怎么知道single linked list 有circle
2.两个sorted linked list merge 成一个，
比如 1->3->5->7 和1->2->6->8 合并成1->1->2->3->5->6->7->8
3.有一个数组，每个元素都是point,求这个数组中离原点最近的k个点
我是非cs专业的，每次看版上好多概念我都不懂，尤其是design 什么东东的，听都没
听过。各位大侠给给建议，应该怎样复习？我目前就上过datastructure的课。
上面三个题我都做出来了，第一题犯了个错：就是判断循环结束的时候我是
while(fast!=NULL) 但是我后来看网上的是while(fast&&fast->next)
第三题我用了个std::map（是sorted的），key储存distance,value储存这个点在原来
数组中的下标。我想问的是map在面试题中常用么？因为我看大家用hashtable比较多，
因为runtime的关系。
我想再问个问题，一般做完online test多久，他们会回信？如果做得不好，他们不给
interview也会回信么？ |
s*******m
发帖数: 52 | 2 这题目你应该拿着cracking直接抄才对哈哈。我就是这么干的。
第三题我用size为K的heap就好了。java直接用priorityqueue |
f*****e
发帖数: 210 | 3 cracking开始做。用map是runtime为nlogn+k,那heap的runtime也是这个吧？返回的是
个Point的指针。大家用map么？
在面试里面用得比较多的是什么结构啊？
【在 s*******m 的大作中提到】
: 这题目你应该拿着cracking直接抄才对哈哈。我就是这么干的。
: 第三题我用size为K的heap就好了。java直接用priorityqueue
|
s*******m
发帖数: 52 | 4 前两题都cracking原题。
如果把priorityqueue的操作当做 1, 那么就是总共就是 n，走一遍就有了。如果把当
做logn，最坏情况就nlogn
amazon onsite实在太好拿了。
【在 f*****e 的大作中提到】
: cracking开始做。用map是runtime为nlogn+k,那heap的runtime也是这个吧？返回的是
: 个Point的指针。大家用map么？
: 在面试里面用得比较多的是什么结构啊？
|
h****y
发帖数: 137 | 5 第三题是EPI原题
【在 s*******m 的大作中提到】
: 前两题都cracking原题。
: 如果把priorityqueue的操作当做 1, 那么就是总共就是 n，走一遍就有了。如果把当
: 做logn，最坏情况就nlogn
: amazon onsite实在太好拿了。
|
f*****e
发帖数: 210 | 6 哥，这个不是onsite,这个online test....额连phone interview 都还木有呢。。。
priority queue insert 是logn 吧？为什么可能是1？ 还有返回值必须是个Point的指
针，是不是要把前k个元素copy到一个数组里，再return这个数组。。。额是菜鸟，请
不要介意。。。
【在 s*******m 的大作中提到】
: 前两题都cracking原题。
: 如果把priorityqueue的操作当做 1, 那么就是总共就是 n，走一遍就有了。如果把当
: 做logn，最坏情况就nlogn
: amazon onsite实在太好拿了。
|
m**********r
发帖数: 27 | 7 这题是用order statistic顺序统计的方法做，时间是O(n)，要是nlogn的方法，随便用
个sort不就可以了吗，一点不虚心。
【在 s*******m 的大作中提到】
: 前两题都cracking原题。
: 如果把priorityqueue的操作当做 1, 那么就是总共就是 n，走一遍就有了。如果把当
: 做logn，最坏情况就nlogn
: amazon onsite实在太好拿了。
|
T******e
发帖数: 157 | 8 请教一下o（n）是怎么做的？
【在 m**********r 的大作中提到】
: 这题是用order statistic顺序统计的方法做，时间是O(n)，要是nlogn的方法，随便用
: 个sort不就可以了吗，一点不虚心。
|
j*********6
发帖数: 407 | 9 用priority queue的话， running time 是 k+nlogk 吧， 其实就是O(nlogk) 因为你
就是top k 的问题 然后 override一下comparator的compare 函数 只比较 绝对值就
行了
我觉得这个online test 分析 也是很重要的 因为题目不难 很多人都能做出来 所以
就看谁的分析更好 code 更clean
加油！！
【在 s*******m 的大作中提到】
: 前两题都cracking原题。
: 如果把priorityqueue的操作当做 1, 那么就是总共就是 n，走一遍就有了。如果把当
: 做logn，最坏情况就nlogn
: amazon onsite实在太好拿了。
|
f**********s
发帖数: 115 | 10 第3题 o(nlgk)不是最佳答案，但是online test够用了
用quick select的原理来做， average o(n) worst case o(n^2) |
