一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1416|回复: 17
收起左侧

Amazon OnSite

[复制链接] |试试Instant~ |关注本帖
dimengmale 发表于 2014-12-9 03:22:41 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Amazon - Other - Onsite 在线笔试 |Fail

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

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

x
Amazon 面经

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴1. Online Coding Challenge 来自hackrank
. Waral 鍗氬鏈夋洿澶氭枃绔,
90分钟 一道题, 具体

public class Log {
        public String name;
        public String pageType;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        public Date   date;
}. Waral 鍗氬鏈夋洿澶氭枃绔,

给你很多的用户浏览amazon页面的记录, 让你找出最popular的用户浏览的前三个页面的序列.

abc, page1, xxxxx
ddd, page2, xxxxx.鏈枃鍘熷垱鑷1point3acres璁哄潧
abc, page2, xxxxx
ddd, page4, xxxxx
ccc, page1, xxxxx. visit 1point3acres.com for more.
ccc, page2, xxxxx
abc, page5, xxxxx
ccc, page5, xxxxx. visit 1point3acres.com for more.
ddd, page6, xxxxx. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

这里结果就是放回[page1, page2, page5]  因为abc 和ccc都是这个序列, 出现了两次 ddd的[page2, page4, page6]只有一次
因为给你的时候就是按时间排好序的 所以不用管顺序,不然排序一次就好

2 On site, 每轮都是45分钟, 上来15分钟问些behavior的问题, 然后简单介绍下他们, 然后25分钟coding, 然后5分钟提问. 都要white board coding.
. From 1point 3acres bbs
round 1. 印度女
问了个anagram的题目, leetcode原题, 然后问了大量的behavior问题

round 2. 国人女
问了个买卖股票一次获取最大profit的问题 leetcode原题, 然后问了大量的behavior的问题和一些设计. from: 1point3acres.com/bbs

round 3. 白男带个女shadow
问了个matrix的问题
0 0 0 0 0.鐣欏璁哄潧-涓浜-涓夊垎鍦
1 1 0 0 0
. 鍥磋鎴戜滑@1point 3 acres1 0 0 0 1.鏈枃鍘熷垱鑷1point3acres璁哄潧
0 0 0 0 0
0表示空的block, 1表示train station, 让你输出一个matrix, 每个点的value是这点到离它最近的train station的距离.(上下左右都可以走)
这个输出如下
1 1 2 3 4
0 0 1 2 1
0 1 2 1 0
1 2 3 2 1
开始想dp,发现行不通,因为上下左右都要考虑, 没想出dp怎么弄
用的暴力迭代, 先把train station的距离设为0,其他-1, 然后再把train station周边置为1, 然后在依次迭代, 每次距离+1, 所有的坑都填上.
. 鍥磋鎴戜滑@1point 3 acres

round 4. hiring manager, 白男带个老白男shadow
问了个如何设计twitter的design 完全不会. Waral 鍗氬鏈夋洿澶氭枃绔,
完全要靠自己去问来确认需求
. 1point 3acres 璁哄潧
round 5. 印度人?
opentable, design. 完全自己设计数据结构 和 接口. more info on 1point3acres.com
需求, 用户输入 restaurant, timeslot, 人数, 返回是否可以预订
一个restaurant 可能有多个桌子, 每个桌子可能可以坐多个人
如果预订的时候,人数大于一个桌子, 可以把相邻的桌子 combine. 1point3acres.com/bbs
timeslot 30分钟算一个, 一天就可以算24*2个, 编号从0到47, 用户的输入只能有一个timeslot
需求都是自己问出来的, 那个人惜字如金, 你不问,啥也不说.. more info on 1point3acres.com
.鐣欏璁哄潧-涓浜-涓夊垎鍦
总结, 英语太烂, 虽然都听得懂, 表达太差. 另外design比较多, 没啥经验确实不会弄. 白板coding要大量练习, 跟电脑上写不是一回事.

积分
求各种内推


. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. From 1point 3acres bbs

. 1point3acres.com/bbs


评分

1

查看全部评分

圆梦梦剧场 发表于 2014-12-9 03:34:21 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
round 3那题就是对于每个station做一次BFS遍历矩阵吧
回复 支持 反对

使用道具 举报

suonan 发表于 2014-12-9 03:44:31 | 显示全部楼层
关注一亩三分地微博:
Warald
还有hackerank的oa?所以说OA不同的就是会去onsite?
回复 支持 反对

使用道具 举报

 楼主| dimengmale 发表于 2014-12-9 03:46:21 | 显示全部楼层
圆梦梦剧场 发表于 2014-12-9 03:34
round 3那题就是对于每个station做一次BFS遍历矩阵吧

恩, 当时想岔了, 其实应该就是用个队列存当前要visit的 和 hashmap存已经visited, 复杂度应该是O(MN)
回复 支持 反对

使用道具 举报

鱼吃鱼翅 发表于 2014-12-9 04:44:29 | 显示全部楼层
dimengmale 发表于 2014-12-9 03:46
恩, 当时想岔了, 其实应该就是用个队列存当前要visit的 和 hashmap存已经visited, 复杂度应该是O(MN)

请问对于每个station都做bfs遍历的话,复杂度应该是m*m*n*n吧?希望帮忙解释一下如何是m*n。。。多谢!
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-12-9 04:46:11 | 显示全部楼层
鱼吃鱼翅 发表于 2014-12-9 04:44
请问对于每个station都做bfs遍历的话,复杂度应该是m*m*n*n吧?希望帮忙解释一下如何是m*n。。。多谢!

不是对每个station都做BFS
是从所有的station同时出发,总的一起做一遍BFS
回复 支持 反对

使用道具 举报

 楼主| dimengmale 发表于 2014-12-9 05:08:46 | 显示全部楼层
鱼吃鱼翅 发表于 2014-12-9 04:44.鐣欏璁哄潧-涓浜-涓夊垎鍦
请问对于每个station都做bfs遍历的话,复杂度应该是m*m*n*n吧?希望帮忙解释一下如何是m*n。。。多谢!

相当于做树的层次遍历, train station就是根, 它的四周就是孩子, 用个queue 保存当前要visit的, 用hashmap保存已经visited的, 所有的节点(就是矩阵里所有的节点)都只进入queue和出queue一次, 所以是O(MN)的
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2014-12-9 06:19:14 | 显示全部楼层
第三题,我写了一个代码,用BFS实现。感觉是O(MN*K),K是train station 的数目。
  1.         public static void f(int[][] board) {
  2.                 if(board.length == 0) return;
  3.                 int m = board.length;
  4.                 int n = board[0].length;
  5.                 for(int i=0;i<m;i++){
  6.                         for(int j=0;j<n;j++){
  7.                                 if(board[i][j] == 1){
  8.                                         board[i][j] = 0;
  9.                                 }else if(board[i][j] == 0){
  10.                                         board[i][j] = Integer.MAX_VALUE;
  11.                                 }
  12.                         }
  13.                 }. 1point3acres.com/bbs
  14.                
  15.                 for(int i=0;i<m;i++){. from: 1point3acres.com/bbs
  16.                         for(int j=0;j<n;j++){
  17.                                 if(board[i][j] == 0){
    . 1point 3acres 璁哄潧
  18.                                         BFS(board,i,j,new boolean[m][n]);
  19.                                 }. more info on 1point3acres.com
  20.                         }
  21.                 }
  22.                
  23.         }
  24.        
  25.         public static void BFS(int[][] board, int i, int j, boolean[][] visited) {
  26.                 Queue<Integer> queue = new LinkedList<Integer>();
  27.                 Queue<Integer> level = new LinkedList<Integer>();
  28.                 int m = board.length;
  29.                 int n = board[0].length;
  30.                 queue.add(i*n + j);
  31.                 level.add(0);
  32.                 while(!queue.isEmpty() && !level.isEmpty()) {
  33.                         int tmp = queue.poll();
    . From 1point 3acres bbs
  34.                         int cur_i = tmp / n;
  35.                         int cur_j = tmp % n;. more info on 1point3acres.com
  36.                         int depth = level.poll();
  37.                         if(depth < board[cur_i][cur_j]) board[cur_i][cur_j] = depth;. Waral 鍗氬鏈夋洿澶氭枃绔,
  38.                         visited[cur_i][cur_j] = true;
  39.                         if(cur_i+1 <m && !visited[cur_i+1][cur_j]){
  40.                                 queue.add((cur_i+1)*n+cur_j);
  41.                                 level.add(depth+1);
  42.                         }
  43.                        
  44.                         if(cur_i-1 >=0 && !visited[cur_i-1][cur_j]){. From 1point 3acres bbs
  45.                                 queue.add((cur_i-1)*n+cur_j);
  46.                                 level.add(depth+1);
  47.                         }. 1point3acres.com/bbs
  48.                        
  49.                         if(cur_j+1 <n && !visited[cur_i][cur_j+1]){
  50.                                 queue.add(cur_i*n+cur_j+1);
  51.                                 level.add(depth+1);
  52.                         }
  53.                        
  54.                         if(cur_j-1 >=0 && !visited[cur_i][cur_j-1]){
  55.                                 queue.add(cur_i*n+cur_j-1);
  56.                                 level.add(depth+1);
  57.                         }
  58.                 }
  59.         }
复制代码
回复 支持 反对

使用道具 举报

鱼吃鱼翅 发表于 2014-12-9 06:50:21 | 显示全部楼层
zq13667243992 发表于 2014-12-9 06:19
第三题,我写了一个代码,用BFS实现。感觉是O(MN*K),K是train station 的数目。

请问你这个算法的复杂度就是m2n2吧?
回复 支持 反对

使用道具 举报

22691482 发表于 2014-12-9 07:20:28 | 显示全部楼层
twitter 设计某新浪博客有具体分析。。
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2014-12-9 07:53:13 | 显示全部楼层
鱼吃鱼翅 发表于 2014-12-9 06:50
请问你这个算法的复杂度就是m2n2吧?

那个BFS只会执行K次,每次都是M*N,所以是M*N*K. 不是M2N2
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-12-9 07:56:38 | 显示全部楼层
zq13667243992 发表于 2014-12-9 07:53
那个BFS只会执行K次,每次都是M*N,所以是M*N*K. 不是M2N2

. more info on 1point3acres.com不需要每个station都做一次BFS
只需要同时从所有statsion出发总的做一次BFS就好了。
可以看出一个虚拟的source点,它与所有station相连。然后从这个虚拟的SOURCE做一次BFS
回复 支持 反对

使用道具 举报

peter8996 发表于 2014-12-9 10:13:53 | 显示全部楼层
22691482 发表于 2014-12-9 07:20
twitter 设计某新浪博客有具体分析。。

大神,求链接
回复 支持 反对

使用道具 举报

22691482 发表于 2014-12-9 11:37:21 | 显示全部楼层

http://blog.sina.com.cn/s/blog_46d0a3930100f0vr.html

这是这个系列第一篇链接。去目录里面可以找到更多。
回复 支持 反对

使用道具 举报

dreamhit 发表于 2015-1-12 11:09:36 | 显示全部楼层
圆梦梦剧场 发表于 2014-12-9 07:56
不需要每个station都做一次BFS
只需要同时从所有statsion出发总的做一次BFS就好了。. more info on 1point3acres.com
可以看出一个虚拟 ...
. From 1point 3acres bbs
不太明白这个“虚拟的station”什么意思,怎么同时出发bfs的,
可以贴个pseudocode看一下么
谢谢~
回复 支持 反对

使用道具 举报

dreamhit 发表于 2015-1-12 11:10:55 | 显示全部楼层
输出应该是
1 1 2 3 2
0 0 1 2 1. 1point3acres.com/bbs
0 1 2 1 0
1 2 3 2 1.1point3acres缃
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-12 11:16:58 | 显示全部楼层
dreamhit 发表于 2015-1-12 11:09
不太明白这个“虚拟的station”什么意思,怎么同时出发bfs的,
可以贴个pseudocode看一下么
谢谢~

就是把所有的station放在queue里
然后按正常的步骤继续bfs
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 20:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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