一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2116|回复: 30
收起左侧

amazon oa求教

[复制链接] |试试Instant~ |关注本帖
pinkdatura 发表于 2016-8-12 06:44:47 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Amazon - 猎头 - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
3周以内的第二次amazon oa,
第一次是vancouver什么event, 120分钟,和地里一模一样的 类似Wall & gate,还有一个social network之类的很简单的题目,很快做好也都过test cases了,然后recruiter就奇迹的消失了
第二次是前天的75分钟,题目是这样的:.1point3acres缃
每个电影都有个rate,然后还有一个list是和这个电影类似的电影
就比如电影a有bcd和他类似,b还有ckl类似的,。。。然后这些类似的组成了一个network,给一个电影的号,让给出它network里排名前k的电影. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
list<integer>find( int id, int k)
我用的dfs把所有和这个movie的network存下来,然后放到一个priorityqueue里,拿出前k个,9/11还有2个test case还没过,也看不见是啥,求问更好的解法。
uber店面二面,给了coderpad完全没让写程序,就说之前做的project(很久以前做的), 国人面试官说我对cs无热情,不懂scale之类的和u家的氛围不和,肯定不给过onsite,说什么也不给过,让我过就影响他的记录等等。所有在这里提醒大家,店面也要好好准备自前的projects,细节和如何改善都得弄清楚, 哎。

评分

1

查看全部评分

会踢球的哈士奇 发表于 2016-8-14 14:14:45 | 显示全部楼层
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.         q.offer(moive);

  7.         while (!q.isEmpty()) {
  8.             Moive cur = q.poll();

  9.             for (Moive neighbor : cur.neighbors) {
  10.                 if (visited.add(neighbor.id)) {. 鍥磋鎴戜滑@1point 3 acres
  11.                     minHeap.offer(neighbor.id);

  12.                     if (minHeap.size() > k) {
  13.                         minHeap.poll();
  14.                     }

  15.                     q.offer(neighbor);. From 1point 3acres bbs
  16.                 }
  17.             }. 1point 3acres 璁哄潧
  18.         }

  19.         while (!minHeap.isEmpty()) {
  20.             res.add(minHeap.poll());
  21.         }

  22.         return res;
  23.     }

  24.     class Moive {
  25.         int id;
  26.         int rate;
  27.         List<Moive> neighbors;
  28. . visit 1point3acres.com for more.
  29.         public Moive(int id, int rate, List<Moive> neighbors) {
  30.             this.id = id;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.             this.rate = rate;
  32.             this.neighbors = neighbors;
  33.         }. 1point3acres.com/bbs
  34.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35. . 1point 3acres 璁哄潧
复制代码
回复 支持 1 反对 0

使用道具 举报

hello2pig 发表于 2016-8-12 09:45:42 | 显示全部楼层
uber面试官居然这么直接。。
回复 支持 反对

使用道具 举报

hello2pig 发表于 2016-8-12 09:48:13 | 显示全部楼层
请问楼主第二次的OA只有一道题么?
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-12 10:10:52 | 显示全部楼层
hello2pig 发表于 2016-8-12 09:48
请问楼主第二次的OA只有一道题么?

嗯,就一道,75分钟
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-12 10:14:28 | 显示全部楼层
hello2pig 发表于 2016-8-12 09:45. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
uber面试官居然这么直接。。

哎,说到后面我都没心情说什么了,一面的国人大哥超级nice,没想到二面的国人mm就。。。
回复 支持 反对

使用道具 举报

mermanwq 发表于 2016-8-12 11:09:31 | 显示全部楼层
Wall & gate 那个是什么题
回复 支持 反对

使用道具 举报

todayand 发表于 2016-8-12 11:20:59 | 显示全部楼层
"就比如电影a有bcd和他类似,b还有ckl类似的,。。。然后这些类似的组成了一个network,给一个电影的号,让给出它network里排名前k的电影 list<integer>find( int id, int k)"

补充内容 (2016-8-12 11:22):-google 1point3acres
额,还没写完就发出去了。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
请问lz题目的排名按什么排的?
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-12 12:38:50 | 显示全部楼层
todayand 发表于 2016-8-12 11:20. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
"就比如电影a有bcd和他类似,b还有ckl类似的,。。。然后这些类似的组成了一个network,给一个电影的号,让 ...

按电影的rating排列的,比如电影a 3.2 它相似的电影b 1.5 c 2.0 然后b相似的电影6.7.。。
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-12 12:39:15 | 显示全部楼层
mermanwq 发表于 2016-8-12 11:09
Wall & gate 那个是什么题

leetcode有,就是那个bfs/dfs最近距离的那个
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-12 12:39:25 | 显示全部楼层
mermanwq 发表于 2016-8-12 11:09. more info on 1point3acres.com
Wall & gate 那个是什么题

leetcode有,就是那个bfs/dfs最近距离的那个
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-15 02:48:24 | 显示全部楼层
会踢球的哈士奇 发表于 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比较大的时候不太好。
最近刚开始研究时间复杂度,答的不对的话,请指正,
回复 支持 反对

使用道具 举报

stephaniede 发表于 2016-8-15 04:17:24 | 显示全部楼层
我来鼓励LZ,uber面试官说的都不算什么。 说白了就是对面试者下手狠而已,LZ和我一样运气不好。-google 1point3acres
我snapchat一面很顺利白人妹子面的,第二面国人小哥一看我github刷了leetcode就故意出非leetcode的题目。。 你说这不是下手狠这是啥。。 不想猜测他们的动机为何,只能理解和该公司气场不合了
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-15 08:24:21 | 显示全部楼层
stephaniede 发表于 2016-8-15 04:17
我来鼓励LZ,uber面试官说的都不算什么。 说白了就是对面试者下手狠而已,LZ和我一样运气不好。
我snapcha ...

真的太感激staphanie啦,说到心坎里了,我们都加油,一定会有最棒的结果和未来等着我们的!
回复 支持 反对

使用道具 举报

stephaniede 发表于 2016-8-15 09:52:02 | 显示全部楼层
pinkdatura 发表于 2016-8-14 17:24
真的太感激staphanie啦,说到心坎里了,我们都加油,一定会有最棒的结果和未来等着我们的!

嗯好的~~ 没问题互相鼓励哈哈
回复 支持 反对

使用道具 举报

会踢球的哈士奇 发表于 2016-8-16 09:57:27 | 显示全部楼层
pinkdatura 发表于 2016-8-15 02:48
赞~感觉时间复杂度不会有太大的改变,无论bfs, dfs,都需要遍历所有的network以内的movie才能求出top k  ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
同意 BFS 和DFS 都一样的  因为一定把 所有的相关的遍历完
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-8-17 02:26:27 | 显示全部楼层
楼主,movie那题给的输入接口是什么?
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-17 02:52:26 | 显示全部楼层
就是movie id,movie这个class可以call getSimilarMovies()
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-17 02:55:17 | 显示全部楼层
题目让设计成api的样式,可以反复call这个function,大家有什么想法吗?我的想法就是每次call一次,就更新一次这个movie的similar movies,把不是directly相联系的也加到network里。
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-8-17 05:08:33 | 显示全部楼层
pinkdatura 发表于 2016-8-17 02:52
就是movie id,movie这个class可以call getSimilarMovies()

2楼写的那个API怎么样?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 19:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表