一亩三分地论坛

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

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

Amazon OnSite

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

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

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

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

x
Amazon 面经
.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. Online Coding Challenge 来自hackrank
.鏈枃鍘熷垱鑷1point3acres璁哄潧
90分钟 一道题, 具体. from: 1point3acres.com/bbs

public class Log {
        public String name;
        public String pageType;. 1point3acres.com/bbs
        public Date   date;
}

给你很多的用户浏览amazon页面的记录, 让你找出最popular的用户浏览的前三个页面的序列.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
abc, page1, xxxxx
ddd, page2, xxxxx
abc, page2, xxxxx
ddd, page4, xxxxx.1point3acres缃
ccc, page1, xxxxx.鏈枃鍘熷垱鑷1point3acres璁哄潧
ccc, page2, xxxxx
abc, page5, xxxxx
ccc, page5, xxxxx
ddd, page6, xxxxx

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

2 On site, 每轮都是45分钟, 上来15分钟问些behavior的问题, 然后简单介绍下他们, 然后25分钟coding, 然后5分钟提问. 都要white board coding.

round 1. 印度女
问了个anagram的题目, leetcode原题, 然后问了大量的behavior问题.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鍥磋鎴戜滑@1point 3 acres
round 2. 国人女
问了个买卖股票一次获取最大profit的问题 leetcode原题, 然后问了大量的behavior的问题和一些设计
. Waral 鍗氬鏈夋洿澶氭枃绔,
round 3. 白男带个女shadow
问了个matrix的问题
0 0 0 0 0
1 1 0 0 0
1 0 0 0 1. Waral 鍗氬鏈夋洿澶氭枃绔,
0 0 0 0 0
0表示空的block, 1表示train station, 让你输出一个matrix, 每个点的value是这点到离它最近的train station的距离.(上下左右都可以走)
这个输出如下
1 1 2 3 4
0 0 1 2 1. Waral 鍗氬鏈夋洿澶氭枃绔,
0 1 2 1 0
1 2 3 2 1
开始想dp,发现行不通,因为上下左右都要考虑, 没想出dp怎么弄
用的暴力迭代, 先把train station的距离设为0,其他-1, 然后再把train station周边置为1, 然后在依次迭代, 每次距离+1, 所有的坑都填上.


round 4. hiring manager, 白男带个老白男shadow
问了个如何设计twitter的design 完全不会
完全要靠自己去问来确认需求

round 5. 印度人?
opentable, design. 完全自己设计数据结构 和 接口
需求, 用户输入 restaurant, timeslot, 人数, 返回是否可以预订
一个restaurant 可能有多个桌子, 每个桌子可能可以坐多个人
如果预订的时候,人数大于一个桌子, 可以把相邻的桌子 combine-google 1point3acres
timeslot 30分钟算一个, 一天就可以算24*2个, 编号从0到47, 用户的输入只能有一个timeslot
需求都是自己问出来的, 那个人惜字如金, 你不问,啥也不说.. Waral 鍗氬鏈夋洿澶氭枃绔,

总结, 英语太烂, 虽然都听得懂, 表达太差. 另外design比较多, 没啥经验确实不会弄. 白板coding要大量练习, 跟电脑上写不是一回事.
.1point3acres缃
积分 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
求各种内推. visit 1point3acres.com for more.




. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

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

使用道具 举报

suonan 发表于 2014-12-9 03:44:31 | 显示全部楼层
还有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。。。多谢!
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2014-12-9 04:46:11 | 显示全部楼层
鱼吃鱼翅 发表于 2014-12-9 04:44
.1point3acres缃请问对于每个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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.                                 } . more info on 1point3acres.com
  12.                         }
  13.                 }
  14.                
  15.                 for(int i=0;i<m;i++){
  16.                         for(int j=0;j<n;j++){
  17.                                 if(board[i][j] == 0){
  18.                                         BFS(board,i,j,new boolean[m][n]);
  19.                                 }
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  30.                 queue.add(i*n + j);
  31.                 level.add(0);. From 1point 3acres bbs
  32.                 while(!queue.isEmpty() && !level.isEmpty()) {
  33.                         int tmp = queue.poll();. from: 1point3acres.com/bbs
  34.                         int cur_i = tmp / n;
  35.                         int cur_j = tmp % n;
  36.                         int depth = level.poll();
  37.                         if(depth < board[cur_i][cur_j]) board[cur_i][cur_j] = depth;
  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]){
  45.                                 queue.add((cur_i-1)*n+cur_j);
  46.                                 level.add(depth+1);
  47.                         }
  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.                         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  58.                 }
  59.         }
复制代码
回复 支持 反对

使用道具 举报

鱼吃鱼翅 发表于 2014-12-9 06:50:21 | 显示全部楼层
zq13667243992 发表于 2014-12-9 06:19. from: 1point3acres.com/bbs
第三题,我写了一个代码,用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

不需要每个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 | 显示全部楼层
peter8996 发表于 2014-12-9 10:13. 鍥磋鎴戜滑@1point 3 acres
大神,求链接
. From 1point 3acres bbs
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就好了。
可以看出一个虚拟 ...

不太明白这个“虚拟的station”什么意思,怎么同时出发bfs的, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
可以贴个pseudocode看一下么
谢谢~
回复 支持 反对

使用道具 举报

dreamhit 发表于 2015-1-12 11:10:55 | 显示全部楼层
输出应该是
1 1 2 3 2
0 0 1 2 1 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
0 1 2 1 0
1 2 3 2 1
回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-1-12 11:16:58 | 显示全部楼层
dreamhit 发表于 2015-1-12 11:09
不太明白这个“虚拟的station”什么意思,怎么同时出发bfs的,
可以贴个pseudocode看一下么
谢谢~
. visit 1point3acres.com for more.
就是把所有的station放在queue里
然后按正常的步骤继续bfs
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 18:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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