一亩三分地论坛

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

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

AmazonOA2 DL:11/13

[复制链接] |试试Instant~ |关注本帖
cnsudo 发表于 2015-11-8 15:31:15 | 显示全部楼层 |阅读模式

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

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

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

x
第一部分是给一个模拟工作环境和一系列项目问题, 对所给的应对办法打分从ineffective到very effective5个档。你是选择deadline呢还是选择customer requirement呢这种问题会逼死天秤座。. 鍥磋鎴戜滑@1point 3 acres


主要是第二部分coding。
第一题:一个处理器要处理一堆request,一次只能处理一条,如果它有几个积压着的requests,它会先执行持续时间短的那个;对于持续时间相等的requests,先执行最早到达处理器的request。问平均每个request要等多久才能被处理。input:requestTimes[],每个request到达处理器的时间; durations[] 每个request要处理的持续时间。 两个数组是一一对应的,并已按requestTimes[] 从小到大排序过. 1point 3acres 璁哄潧

public double CalWaitingTime(int requestTimes[], int[] durations[]){}

第二题:一维版的Leetcode 289 Game of life
一条线上有八个点,1代表它或者,0代表它死了。如果一个点左右两边的点都或者或死了,它在下一回合会死去;否则它在下一回合会复活。求k回合后的状态. 1point 3acres 璁哄潧
. visit 1point3acres.com for more.
public int[] gameOfLife(int[] input, int k){}
//第-1个点和第input.length个点算作一直是死亡的。

. 1point3acres.com/bbs
补充内容 (2015-11-8 15:42):
第一题用一个PriorityQueue
第二题用递归有一个case没跑出来,改用while循环就全跑出来了,应该是k特别大的case stackoverflow了。

补充内容 (2015-11-24 08:51):.鐣欏璁哄潧-涓浜-涓夊垎鍦
过了15天,今天收到onsite邀请

评分

2

查看全部评分

thewave 发表于 2015-11-12 03:34:53 | 显示全部楼层
  1. vector<int> daysChange(vector<int>data, int k){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  2.         if(data.size()==0)return data;
  3.         data.push_back(0);
  4.         int pre;
  5.         for(int n=1;n<=k;n++){
  6.             pre = data[0];
  7.             data[0] = data[1];. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.             for(int i=1;i<data.size()-1;i++){
  9.                 int temp = data[i];. 1point 3acres 璁哄潧
  10.                 data[i] = pre ^ data[i + 1];
  11.                 pre = temp;. From 1point 3acres bbs
  12.             }
  13.         }
  14.         data.pop_back();
  15.         return data;
  16.     }
复制代码


我觉得用pre就好了。
也请大家帮忙看看有什么可以优化的? -google 1point3acres
谢谢了。
回复 支持 1 反对 0

使用道具 举报

hpplayer 发表于 2015-11-10 14:22:58 | 显示全部楼层
夏末微凉 发表于 2015-11-10 14:03
多谢!!! 主要我大概算了算,觉得循环K次太多了,尤其K很大的情况,而且就我举的这个例子,每14次一循 ...
. 1point3acres.com/bbs
没必要用额外的ARRAY,因为题目给出的数值只用了0和1,他们只用了2进制的最后一位,我们可以用2进制的倒数第二位来储存下一轮的状态,用&1来取当前状态 然后用>>1来更新下一轮状态
回复 支持 1 反对 0

使用道具 举报

wildchild 发表于 2015-11-8 22:27:42 | 显示全部楼层
看起来都是新题?
回复 支持 反对

使用道具 举报

 楼主| cnsudo 发表于 2015-11-8 22:43:30 | 显示全部楼层
wildchild 发表于 2015-11-8 22:27
看起来都是新题?

第一题http://www.1point3acres.com/bbs/ ... &fromuid=107048有提到过,有点意思
第二题是leetcode简单变形,不难


补充内容 (2015-11-8 22:45):
第一题跟链接那不一样的地方是少一个输入q
回复 支持 反对

使用道具 举报

wildchild 发表于 2015-11-8 23:09:56 | 显示全部楼层
cnsudo 发表于 2015-11-8 22:43
第一题http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=142143&fromuid=107048有提到过, ...

谢谢回复~~ 还想问下lz是写c++的么?c++的接口是怎么样的?
回复 支持 反对

使用道具 举报

 楼主| cnsudo 发表于 2015-11-8 23:17:23 | 显示全部楼层
wildchild 发表于 2015-11-8 23:09
谢谢回复~~ 还想问下lz是写c++的么?c++的接口是怎么样的?

我用的是Java呢,不会c++
回复 支持 反对

使用道具 举报

wildchild 发表于 2015-11-8 23:19:09 | 显示全部楼层
cnsudo 发表于 2015-11-8 23:17
我用的是Java呢,不会c++

谢谢lz了!祝offer多多~
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-9 03:20:07 | 显示全部楼层
lz请问这两个部分分别给了你多少时间做呢?还有game of life为啥要用递归呀?
回复 支持 反对

使用道具 举报

 楼主| cnsudo 发表于 2015-11-9 03:28:45 | 显示全部楼层
CSBrogrammer 发表于 2015-11-9 03:20. more info on 1point3acres.com
lz请问这两个部分分别给了你多少时间做呢?还有game of life为啥要用递归呀?

第一部分实景模拟给90分钟,第二部分代码给60分钟。game of life 我当时想每递归一层 k-1啊,最后到k=0时一层层return出来。这种同一动作重复k次的题我第一反应都是递归,想法比较直白。
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-9 03:58:16 | 显示全部楼层
cnsudo 发表于 2015-11-9 03:28
第一部分实景模拟给90分钟,第二部分代码给60分钟。game of life 我当时想每递归一层 k-1啊,最后到k=0 ...

原来如此,十分感谢!
回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-10 13:15:21 | 显示全部楼层
你好,楼主,我想请教一下Game of life这题, 比如input  arr 是 00111001, 如果k=1,变一次,则为 01101110,是这样吧?

我目前的想法就是 大while k次, 每次都用一个新数组存放 改变后的值,再update arr,直到k=0
corner case: 1. arr== null || arr.length ==0||k<=0, 直接返回 arr, 2. arr.length==1,返回 new int[0];

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 这样做,复杂度大概O(kn), 而且space O(N), 有没有别的好的方法的。。求指点. more info on 1point3acres.com

回复 支持 反对

使用道具 举报

 楼主| cnsudo 发表于 2015-11-10 13:25:45 | 显示全部楼层
夏末微凉 发表于 2015-11-10 13:15.1point3acres缃
你好,楼主,我想请教一下Game of life这题, 比如input  arr 是 00111001, 如果k=1,变一次,则为 0110111 ...

差不多是这个意思,再优化的话我想就是用bit运算实现SpaceO(1)了,没什么必要。case都能跑过就行了吧。

补充内容 (2015-11-10 13:27):
还有就是题目给定k=8, 所以Corne case就不用考虑那么多拉
回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-10 14:03:31 | 显示全部楼层
cnsudo 发表于 2015-11-10 13:25
差不多是这个意思,再优化的话我想就是用bit运算实现SpaceO(1)了,没什么必要。case都能跑过就行了吧。

...

多谢!!! 主要我大概算了算,觉得循环K次太多了,尤其K很大的情况,而且就我举的这个例子,每14次一循环,k=1和k=15结果一样,k=14就是变回初始值,就想着说不定会有其他比如位运算方法,不用循环那么多次
回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-10 14:04:32 | 显示全部楼层
夏末微凉 发表于 2015-11-10 14:03
多谢!!! 主要我大概算了算,觉得循环K次太多了,尤其K很大的情况,而且就我举的这个例子,每14次一循 ...

看来我想太多了,啊哈哈,给定k=8实在太好了
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-11-10 14:27:45 | 显示全部楼层
hpplayer 发表于 2015-11-10 14:22
没必要用额外的ARRAY,因为题目给出的数值只用了0和1,他们只用了2进制的最后一位,我们可以用2进制的倒 ...

可不可以就用xor?

补充内容 (2015-11-10 14:30):
用个pre variable存之前的变量然后xor with下个element?这样就O(1) space了。似乎有人在其他地方提到过
回复 支持 反对

使用道具 举报

夏末微凉 发表于 2015-11-11 02:55:49 | 显示全部楼层
hpplayer 发表于 2015-11-10 14:22
没必要用额外的ARRAY,因为题目给出的数值只用了0和1,他们只用了2进制的最后一位,我们可以用2进制的倒 ...

我不是很懂位运算,能不能麻烦你再讲讲?为什么是只用了2进制最后一位啊,还有倒数第二位来存储下一轮是怎么实现的? 求指点
回复 支持 反对

使用道具 举报

thewave 发表于 2015-11-12 03:25:16 | 显示全部楼层
对于持续时间相等的requests,先执行最早到达处理器的request。=>大家觉得 这个对于wait time有影响吗?我理解是不影响的,还额外加判断就多了2句话。
回复 支持 反对

使用道具 举报

Jocelyn000 发表于 2015-11-16 08:38:08 | 显示全部楼层
lz能不能求一份sjf用pq做的代码?谢谢啦!168346938@qq.com
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 12:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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