传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 16045|回复: 53
收起左侧

Amazon OA2 due 11/16

  [复制链接] |试试Instant~ |关注本帖
hzyslddm 发表于 2015-11-16 04:01:53 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Amazon - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
第一部分work simulation,大家多看看地里的面经就好了,需要注意的是,有些让你评价efficiency的选项顺序会有变动,还是要自己仔细看题,一般都是纠结deadline和requirement,也没有什么正确答案,大家自己估摸着选一下就好了,不要过于纠结。
第二部分code,把地里能找到的12道题都写了一遍,结果上来code的第一题居然是
游客,本帖隐藏的内容需要积分高于 155 才可浏览,您当前积分为 0。 查看如何攒积分

.鏈枃鍘熷垱鑷1point3acres璁哄潧
地里目前能找到OA2 coding题:
1.Round Robin
一个处理器要处理一堆request,一次只能处理一条,每次执行一个任务最多执行时间q,接着执行等待着的下一个任务。若前一个任务没执行完则放到队尾,等待下一次执行
假设只要有任务开始以后cpu是不会空闲的,也就是说cpu开始后如果空闲了就说明没有任务了,另外Robin Round最后返回值是float
    public static float waitingTimeRobin(int[] arrival,int[] run, int q)

2.Rotate Matrix (
    把一个m*n的矩阵旋转90度,给一个flag规定是向左转还是向右转

3.Binary search tree minimum sum from root to leaf
    跟BST没啥关系,不要看到BST就以为是最左边的路径之和(左边路径可以很长,右边路径可以很短),用递归做很简单
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分

7.Valid Parenthesis
    给你一个str,里面只有 '('和‘)’,让你数valid pairs一共有多少,如果不是valid就返回-1. (判断是不是valid的parenthesis string,不是的话返回-1,是的话返回valid pair个数,即String.length() / 2 )

8.LRU Cache count miss
    实现以下LRU Cache再判断啥时候miss就好了,返回miss数。建议看看用LinkedHashMap实现lru cache, 代码很简洁。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
9.Day chang(cell growth)
    int[] dayChange(int[] cells, int days), cells 数组,有8个元素,每天的变化情况是 当前位置 cell == (cell[i - 1] == cell[i + 1]) ? 0 : 1, 左右相等,当前位置为0, 不等为1, 默认 cells[0]左边 和 cells[cells.length - 1]右边的位置元素都是0, 求days天后的变化.
. From 1point 3acres bbs
10.Maze
    给个array,其中只有一格是9,其他格子是0或1,0表示此路不通,1表示可以走,判断从(0,0) 点开始上下左右移动能否找到这个是9的格子

11.subtree
. visit 1point3acres.com for more.
12.sametree
    判断两棵树是否相同(结构和值)

另外,1. 若是用Java,用到queue, list啥的记得前面手动import java.util.*   2.所有函数都是static的,所以自己写其他helper函数的时候记得加上static



补充内容 (2015-11-16 04:05):
攒攒RP,求video~~

补充内容 (2015-11-21 10:34):. 1point 3acres 璁哄潧
11/20收到video~

评分

11

查看全部评分

本帖被以下淘专辑推荐:

 楼主| hzyslddm 发表于 2015-11-16 04:04:09 | 显示全部楼层
另外,邮件里写的两部分时间是90min+60min,实际上是120min和70min
回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-16 06:18:27 | 显示全部楼层
楼主我想问下,你reverse list 怎么做的啊? 比如1->2的话,是不是也要变成2 ->1呢
祝楼主拿video!!!
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-16 06:30:47 | 显示全部楼层
夏末微凉 发表于 2015-11-16 06:18
楼主我想问下,你reverse list 怎么做的啊? 比如1->2的话,是不是也要变成2 ->1呢
祝楼主拿video!!!

不是的,是后半段(包括中点在内)reverse,如果是1->2这样的话,后半段只有一个数,reverse完也是1->2,不变的
回复 支持 反对

使用道具 举报

Jocelyn000 发表于 2015-11-16 06:50:05 | 显示全部楼层
现在OA2的题都变成oa1里的题了吗。。。。subtree应该也是上个月的oa1的题吧?
另外能不能麻烦LZ再说说work simulation的题呢?特别是最后几题,看了很多面经还是没有什么概念,谢谢啦!
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-16 07:13:31 | 显示全部楼层
Jocelyn000 发表于 2015-11-16 06:50
现在OA2的题都变成oa1里的题了吗。。。。subtree应该也是上个月的oa1的题吧?. 1point 3acres 璁哄潧
另外能不能麻烦LZ再说说work ...
. From 1point 3acres bbs
http://www.1point3acres.com/bbs/thread-147661-1-1.html
看这个帖子吧.鏈枃鍘熷垱鑷1point3acres璁哄潧
simulation的题感觉打分挺多主观性的,我也不确定我的答案是不是好的,就说一点,看视频的时候可以点右下角的cc按钮,会有字幕
回复 支持 反对

使用道具 举报

xiaoyucool 发表于 2015-11-16 08:52:20 | 显示全部楼层
楼主总结的很好,人品满满,放心肯定offer。

回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-16 09:54:45 | 显示全部楼层
hzyslddm 发表于 2015-11-16 06:30. 1point 3acres 璁哄潧
不是的,是后半段(包括中点在内)reverse,如果是1->2这样的话,后半段只有一个数,reverse完也是1->2, ...

我自己犯傻了。。。谢谢楼主, 之前都不知道中间节点也要reverse,得改改code了,十分感谢楼主提醒!
回复 支持 反对

使用道具 举报

chuxidemeng 发表于 2015-11-18 15:45:19 | 显示全部楼层
LZ请问reverse second half of linked list奇数情况你是怎么解决的啊?……

补充内容 (2015-11-18 16:04):
然后再请问一下list是单向列表还是双向?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-18 16:22:44 | 显示全部楼层
chuxidemeng 发表于 2015-11-18 15:45. From 1point 3acres bbs
LZ请问reverse second half of linked list奇数情况你是怎么解决的啊?……. visit 1point3acres.com for more.

补充内容 (2015-11-18 16:04): ...

单项链表,slow = head, fast = head.next, while(fast.next != null && fast.next.next != null),这样出循环的时候slow.next是中点。corner case前面先处理掉。

补充内容 (2015-11-18 16:23):
单向。。打错了
回复 支持 反对

使用道具 举报

chuxidemeng 发表于 2015-11-19 02:07:42 | 显示全部楼层
hzyslddm 发表于 2015-11-18 16:22
单项链表,slow = head, fast = head.next, while(fast.next != null && fast.next.next != null),这样 ...

LZ这样写好像就奇数偶数都试用了~~~
我本来还想着要不要分开讨论,太渣渣了…….1point3acres缃
LZ说的Corner case是最开始要考虑的head == null || head.next == null的情况吗?
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-19 04:05:56 | 显示全部楼层
chuxidemeng 发表于 2015-11-19 02:07
LZ这样写好像就奇数偶数都试用了~~~
我本来还想着要不要分开讨论,太渣渣了…… 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ说的Corner case是最 ...

对的~字数字数
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2015-11-20 08:48:43 | 显示全部楼层
请问楼主  short job first 题目有假设 cpu没有 idle 的可能吗 ? 类似RoundRobin
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-20 09:06:09 | 显示全部楼层
aiwojiujiu 发表于 2015-11-20 08:48
请问楼主  short job first 题目有假设 cpu没有 idle 的可能吗 ? 类似RoundRobin

没有看到题目,不确定的说。RoundRobin肯定是有这个假设
回复 支持 反对

使用道具 举报

qianq1229 发表于 2015-11-21 08:17:36 | 显示全部楼层
谢谢楼主!原来一直以为reverseSecondHalf那题奇数的中间点不用动呢,另外可以求份LZ的code吗?祝LZvideo顺利,早拿offer!
qianqiao1229@gmail.com
回复 支持 反对

使用道具 举报

xuhang57 发表于 2015-11-23 02:13:29 | 显示全部楼层
恭喜楼主。 看到有人说考到了minPath和 circular list. 请问楼主知道这些题的一些细节么?

回复 支持 反对

使用道具 举报

liranxixi 发表于 2015-11-23 02:25:32 | 显示全部楼层
恭喜楼主!收到video好快啊~是哪天做的呢?我17号due16号做完的但现在还没有消息呢~
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-23 02:30:15 | 显示全部楼层
liranxixi 发表于 2015-11-23 02:25
恭喜楼主!收到video好快啊~是哪天做的呢?我17号due16号做完的但现在还没有消息呢~

我是15号周日上午做的,跟我同天收到video的小伙伴我看14号做的比较多,可能周一是一个分界线吧
回复 支持 反对

使用道具 举报

zZ-IT 发表于 2015-11-23 03:28:57 | 显示全部楼层
楼主,本人也拿到了video 想请教一下,不过遇到的是SJF这题,但做法和Round Robin类似, 用priorityQueue时间复杂度为  O(nlogn) 楼主觉得还有任何优化的可能嘛? 谢谢啦~~
回复 支持 反对

使用道具 举报

 楼主| hzyslddm 发表于 2015-11-23 04:07:33 | 显示全部楼层
zZ-IT 发表于 2015-11-23 03:28
楼主,本人也拿到了video 想请教一下,不过遇到的是SJF这题,但做法和Round Robin类似, 用priorityQueue时 ...

我觉得这样就是最优的了,顶多cpu开始运作之后会不会有空闲这里,一个判断语句可以加上或省略。应该没有别的更优的方法了。我看别人面Round Robin啥的,面试官好像也没多问,反而问别的题比较多。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-24 18:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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