amazon oa求教

谎言之躯 发表于 2016-8-17 05:08
2楼写的那个API怎么样？

挺好的，我写的dfs

会踢球的哈士奇 发表于 2016-8-14 14:14
movie rate 的那道题我用的是BFS + minheap 做的 因为不知道具体的题是什么样子我自己写了一个Movie的类下 ...

你那个priority queue是按id排不是按rate排。。。

pinkdatura 发表于 2016-8-17 05:44
挺好的，我写的dfs

楼主可否粘一下你写的dfs的代码？ 我们分析下为什么会有两个test case没过

whisperty 发表于 2016-8-17 06:15
你那个priority queue是按id排不是按rate排。。。

额。。。 失误失误。。。。 感谢指正

uber 楼主申的是什么职位啊？我找内推结果说近期都不招new grade 了

18658109706 发表于 2016-8-19 11:28
uber 楼主申的是什么职位啊？我找内推结果说近期都不招new grade 了

全栈工程师， 结果就变全跪了，郁闷的消沉了好几天。

谎言之躯 发表于 2016-8-17 06:54
楼主可否粘一下你写的dfs的代码？ 我们分析下为什么会有两个test case没过

好的～明天面完脸家就贴～

如果返回的top K不要求排序，可以考虑拿到连通的movies之后，根据rating应用quick select （https://en.wikipedia.org/wiki/Quickselect）找到pivot index，然后直接返回一个subList。

abuja 发表于 2016-9-1 10:43
如果返回的top K不要求排序，可以考虑拿到连通的movies之后，根据rating应用quick select （https://en.wik ...

感觉如果用quick select的话，还是需要遍历所有的movie，而且quick select的worst case time complexity是o(n^2),对quick select不熟悉，求指教。

pinkdatura 发表于 2016-8-15 02:48
赞～感觉时间复杂度不会有太大的改变，无论bfs, dfs，都需要遍历所有的network以内的movie才能求出top k  ...

楼主，我想意译一下这道题，看看是不是理解对的。

题目是给了一个movie和一个List, List存的是和它类似的电影(类似是指rating相近)，求top K个和这个movie相似的电影？

如果是这样，那遍历所有的movie是没有必要的，因为严格来说，你在以当前movie做BFS的时候，你的minHeap pop了k次就能得到你要的答案，不需要存所有movie。

如果我题目理解有误，还请纠正。