amazon oa求教

3周以内的第二次amazon oa，
第一次是vancouver什么event, 120分钟，和地里一模一样的 类似Wall & gate，还有一个social network之类的很简单的题目，很快做好也都过test cases了，然后recruiter就奇迹的消失了
第二次是前天的75分钟，题目是这

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

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

氛围不和，肯定不给过onsite，说什么也不给过，让我过就影响他的记录等等。所有在这里提醒大家，店面也要好好准备自前的projects，细节和如何改善都得弄清楚， 哎。

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. 
    

复制代码

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。

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

uber面试官居然这么直接。。

请问楼主第二次的OA只有一道题么？

hello2pig 发表于 2016-8-12 09:48
请问楼主第二次的OA只有一道题么？

嗯，就一道，75分钟

hello2pig 发表于 2016-8-12 09:45
uber面试官居然这么直接。。

哎，说到后面我都没心情说什么了，一面的国人大哥超级nice，没想到二面的国人mm就。。。

Wall & gate 那个是什么题

"就比如电影a有bcd和他类似，b还有ckl类似的，。。。然后这些类似的组成了一个network，给一个电影的号，让给出它network里排名前k的电影 list<integer>find( int id, int k)"

补充内容 (2016-8-12 11:22):
额，还没写完就发出去了。。。

请问lz题目的排名按什么排的？

todayand 发表于 2016-8-12 11:20
"就比如电影a有bcd和他类似，b还有ckl类似的，。。。然后这些类似的组成了一个network，给一个电影的号，让 ...

按电影的rating排列的，比如电影a 3.2 它相似的电影b 1.5 c 2.0 然后b相似的电影6.7.。。

mermanwq 发表于 2016-8-12 11:09
Wall & gate 那个是什么题

leetcode有，就是那个bfs/dfs最近距离的那个

mermanwq 发表于 2016-8-12 11:09
Wall & gate 那个是什么题

leetcode有，就是那个bfs/dfs最近距离的那个