一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2429|回复: 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分钟,题目是这样的:
每个电影都有个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) {
    . 1point3acres.com/bbs
  2.         Queue<Moive> q = new LinkedList<Moive>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.         PriorityQueue<Integer> minHeap = new PriorityQueue<>();. more info on 1point3acres.com
  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.             for (Moive neighbor : cur.neighbors) {
  12.                 if (visited.add(neighbor.id)) {
  13.                     minHeap.offer(neighbor.id);
  14. . 1point 3acres 璁哄潧
  15.                     if (minHeap.size() > k) {
  16.                         minHeap.poll();
  17.                     }

  18.                     q.offer(neighbor);
  19.                 }
  20.             }
  21.         }

  22.         while (!minHeap.isEmpty()) {
  23.             res.add(minHeap.poll());. From 1point 3acres bbs
  24.         }

  25.         return res;
  26.     }

  27.     class Moive {
  28.         int id;
  29.         int rate;
  30.         List<Moive> neighbors;
  31. .1point3acres缃
  32.         public Moive(int id, int rate, List<Moive> neighbors) {
  33.             this.id = id;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  34.             this.rate = rate; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  35.             this.neighbors = neighbors;
  36.         }
  37.     }

复制代码
回复 支持 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面试官居然这么直接。。
. 鍥磋鎴戜滑@1point 3 acres
哎,说到后面我都没心情说什么了,一面的国人大哥超级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):
额,还没写完就发出去了。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问lz题目的排名按什么排的?
回复 支持 反对

使用道具 举报

 楼主| pinkdatura 发表于 2016-8-12 12:38:50 | 显示全部楼层
todayand 发表于 2016-8-12 11:20-google 1point3acres
"就比如电影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. Waral 鍗氬鏈夋洿澶氭枃绔,
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和我一样运气不好。
我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, 2017-1-19 12:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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