一亩三分地论坛

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

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

Amazon OA2 due 11/16

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

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

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

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

x
第一部分work simulation,大家多看看地里的面经就好了,需要注意的是,有些让你评价efficiency的选项顺序会有变动,还是要自己仔细看题,一般都是纠结deadline和requirement,也没有什么正确答案,大家自己估摸着选一下就好了,不要过于纠结。
第二部分code,把地里能找到的12道题都写了一遍,结果上来code的第一题居然是reverse half of the linked list,感觉本来应该是在oa1里出现的题目- -,稍微慌乱了下,题目要求reverse后半段链表,如果链表长度是奇数,连中间节点也要reverse,(如1->2->3,结果应该是1->3>2)。第二题是判断tree2是否为tree1的subtree,注意返回值为1(是subtree)和-1(不是subtree)。

地里目前能找到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就以为是最左边的路径之和(左边路径可以很长,右边路径可以很短),用递归做很简单

4.insert into cycle linked list
    插入一个新的节点到一个sorted cycle linkedlist,返回新的节点。给的list节点不一定是最小节点

5.Greatest Common Divisor
    就是给一个数组找这些数的最大公约数
.1point3acres缃
6.Shorted job first
    一个处理器要处理一堆request,一次只能处理一条,如果它有几个积压着的requests,它会先执行持续时间短的那个;对于持续时间相等的requests,先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input:requestTimes[],每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的,并已按requestTimes[] 从小到大排序过
    public double CalWaitingTime(int requestTimes[], int[] durations[]){}
    用priorityqueue做,地里有一个两层循环的答案,没仔细看,做完round robin以后发现思路很相似。注意用priorityqueue写comparator的时候,要先判断两者的execute time,如果execute time相同,则返回arrival time之差,即先按执行时间排序,若执行时间相同则按到达的时间排。

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天后的变化.

10.Maze
    给个array,其中只有一格是9,其他格子是0或1,0表示此路不通,1表示可以走,判断从(0,0) 点开始上下左右移动能否找到这个是9的格子

11.subtree

12.sametree
    判断两棵树是否相同(结构和值)

另外,1. 若是用Java,用到queue, list啥的记得前面手动import java.util.*   2.所有函数都是static的,所以自己写其他helper函数的时候记得加上static
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-11-16 04:05):
攒攒RP,求video~~
.1point3acres缃
补充内容 (2015-11-21 10:34):
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. from: 1point3acres.com/bbs
现在OA2的题都变成oa1里的题了吗。。。。subtree应该也是上个月的oa1的题吧?
另外能不能麻烦LZ再说说work ...

http://www.1point3acres.com/bbs/thread-147661-1-1.html
看这个帖子吧
simulation的题感觉打分挺多主观性的,我也不确定我的答案是不是好的,就说一点,看视频的时候可以点右下角的cc按钮,会有字幕
回复 支持 反对

使用道具 举报

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

回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-16 09:54:45 | 显示全部楼层
hzyslddm 发表于 2015-11-16 06:30
不是的,是后半段(包括中点在内)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
LZ请问reverse second half of linked list奇数情况你是怎么解决的啊?…….鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (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. more info on 1point3acres.com
单项链表,slow = head, fast = head.next, while(fast.next != null && fast.next.next != null),这样 ...

LZ这样写好像就奇数偶数都试用了~~~
我本来还想着要不要分开讨论,太渣渣了……
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啥的,面试官好像也没多问,反而问别的题比较多。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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