amazon oa求教

movie rate 的那道题我用的是BFS + minheap 做的 因为不知道具体的题是什么样子我自己写了一个Movie的类下面是代码 求讨论

1. public List<Integer> find(int id, int k, Moive moive) {
   
2.         Queue<Moive> q = new LinkedList<Moive>();
   
3.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();
   
4.         List<Integer> res = new ArrayList<Integer>();
   
5.         Set<Integer> visited = new HashSet<Integer>();
   
6. 
   
7.         q.offer(moive);
   
8. 
   
9.         while (!q.isEmpty()) {
   
10.             Moive cur = q.poll();
    
11. 
    
12.             for (Moive neighbor : cur.neighbors) {
    
13.                 if (visited.add(neighbor.id)) {
    
14.                     minHeap.offer(neighbor.id);
    
15. 
    
16.                     if (minHeap.size() > k) {
    
17.                         minHeap.poll();
    
18.                     }
    
19. 
    
20.                     q.offer(neighbor);
    
21.                 }
    
22.             }
    
23.         }
    
24. 
    
25.         while (!minHeap.isEmpty()) {
    
26.             res.add(minHeap.poll());
    
27.         }
    
28. 
    
29.         return res;
    
30.     }
    
31. 
    
32.     class Moive {
    
33.         int id;
    
34.         int rate;
    
35.         List<Moive> neighbors;
    
36. 
    
37.         public Moive(int id, int rate, List<Moive> neighbors) {
    
38.             this.id = id;
    
39.             this.rate = rate;
    
40.             this.neighbors = neighbors;
    
41.         }
    
42.     }
    
43. 
    

复制代码

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

赞～感觉时间复杂度不会有太大的改变，无论bfs, dfs，都需要遍历所有的network以内的movie才能求出top k rating, 如果n是network里所有的电影数，就像largest k element in streaming里那种，minheap的话是o((n-k)logk + k)呢，而我用的priority queue的复杂度是o(klogn + n) 在n比较大的时候不太好。
最近刚开始研究时间复杂度，答的不对的话，请指正，

我来鼓励LZ，uber面试官说的都不算什么。 说白了就是对面试者下手狠而已，LZ和我一样运气不好。
我snapchat一面很顺利白人妹子面的，第二面国人小哥一看我github刷了leetcode就故意出非leetcode的题目。。 你说这不是下手狠这是啥。。 不想猜测他们的动机为何，只能理解和该公司气场不合了

stephaniede 发表于 2016-8-15 04:17
我来鼓励LZ，uber面试官说的都不算什么。 说白了就是对面试者下手狠而已，LZ和我一样运气不好。
我snapcha ...

真的太感激staphanie啦，说到心坎里了，我们都加油，一定会有最棒的结果和未来等着我们的！

pinkdatura 发表于 2016-8-14 17:24
真的太感激staphanie啦，说到心坎里了，我们都加油，一定会有最棒的结果和未来等着我们的！

嗯好的～～ 没问题互相鼓励哈哈

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

同意 BFS 和DFS 都一样的  因为一定把 所有的相关的遍历完

楼主，movie那题给的输入接口是什么？

就是movie id，movie这个class可以call getSimilarMovies()

题目让设计成api的样式，可以反复call这个function,大家有什么想法吗？我的想法就是每次call一次，就更新一次这个movie的similar movies,把不是directly相联系的也加到network里。

pinkdatura 发表于 2016-8-17 02:52
就是movie id，movie这个class可以call getSimilarMovies()

2楼写的那个API怎么样？