一亩三分地论坛

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

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

A9电面面经

[复制链接] |试试Instant~ |关注本帖
jaly50 发表于 2015-8-23 23:49:54 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Amazon - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
没有签什么NDA,网上也没看到多少A9面经,发一记分享给大家~


1. Given an array of integers and a number N, write a function to rotate the array to the right by N positions. Waral 鍗氬鏈夋洿澶氭枃绔,
For example
Given an array = [A,B,C,D,E,F,G,H] with N=3, the result will be [F,G,H,A,B,C,D,E]
-google 1point3acres
follow up:  protect your function against malicious inputs

2.Given 3 array of Strings.

Array one = {Red, Green, Blue}
Array two = {Large, Medium, Small}
Array three={giant, monster}

Print out combinations of all three array.
. 1point3acres.com/bbs
public void combination(String[][] arrays) {}

3.
Given an array of 1,000,000 integers where each integer is between 0 and 2^20 - 1.1point3acres缃
Find one integer that is between 0 and 2^20 -1 that is not in the array.. Waral 鍗氬鏈夋洿澶氭枃绔,
Hint: 2^20 = 1,048,576 > 1,000,000. That means there are at least 48,576 integers that are not in the array
要求 尽量优化时空复杂度


最近看到amazon在new york times的报道有点被吓到ヽ(′o`;. from: 1point3acres.com/bbs
不过A9的职位好喜欢=)
希望能给onsite

评分

3

查看全部评分

arjiang 发表于 2015-11-4 15:13:25 | 显示全部楼层
jaly50 发表于 2015-8-24 13:03
1百万个数
分1000个bucket装,每个bucket装1000个数
用一个array就好了。a[0]表示(0-999) 的数有几个 ...

时间复杂度应该是2n把
先像你说的一样弄个size=1024的array, 用来count 每个bucket(0~1023, 1024~2047,)里的个数
一边下来至少会有一个ct不够1024
找到它,比如是 1024~2047
reuse 开始那个array 用来数1024~2047出现次数,遍历一遍即可
回复 支持 1 反对 0

使用道具 举报

clockwise9 发表于 2015-8-24 00:47:30 | 显示全部楼层
话说LZ投的是什么职位啊?我看A9的很多职位都需要5+年工作经验的,senior的要7+年……
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-24 00:49:50 | 显示全部楼层
clockwise9 发表于 2015-8-24 00:47
话说LZ投的是什么职位啊?我看A9的很多职位都需要5+年工作经验的,senior的要7+年……

投了四五个职位的样子. visit 1point3acres.com for more.

给我回应的 好像是一个大数据分析的职位吧
-google 1point3acres

蛮投咯
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-24 02:05:03 | 显示全部楼层
请问第三题有比O(n log n)更好的解法吗?
回复 支持 反对

使用道具 举报

clockwise9 发表于 2015-8-24 03:56:38 | 显示全部楼层
jaly50 发表于 2015-8-24 00:49. visit 1point3acres.com for more.
投了四五个职位的样子

给我回应的 好像是一个大数据分析的职位吧
. 鍥磋鎴戜滑@1point 3 acres
感谢LZ,原来还可以投多个啊
回复 支持 反对

使用道具 举报

Augustus 发表于 2015-8-24 10:30:26 | 显示全部楼层
小弟愚见,第三题自己建一个hash table,时间复杂度n,空间复杂度n,但是感觉应该还能优化,求楼主告知。。。
回复 支持 反对

使用道具 举报

annawuyi 发表于 2015-8-24 11:49:02 | 显示全部楼层
jaly50 发表于 2015-8-24 00:49
投了四五个职位的样子

给我回应的 好像是一个大数据分析的职位吧

请问楼主投了4-5个职位,简历是同一份?还是都要改一下?谢谢
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-24 13:00:55 | 显示全部楼层
annawuyi 发表于 2015-8-24 11:49 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
请问楼主投了4-5个职位,简历是同一份?还是都要改一下?谢谢

我自己是同一份啊. visit 1point3acres.com for more.
不过5月份就投了 也没理我
最近又投了两三个 才理我一个
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-24 13:03:39 | 显示全部楼层
Augustus 发表于 2015-8-24 10:30
小弟愚见,第三题自己建一个hash table,时间复杂度n,空间复杂度n,但是感觉应该还能优化,求楼主告知。。。

1百万个数
分1000个bucket装,每个bucket装1000个数
用一个array就好了。a[0]表示(0-999) 的数有几个。

扫一遍后。就可以知道a[几]不满1000了。
这样时间复杂度就降到 1000*n了。空间则是1000
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-24 13:06:58 | 显示全部楼层
wenqiang88 发表于 2015-8-24 02:05
请问第三题有比O(n log n)更好的解法吗?

一个数在这一百万个数里的概率是: p=1百万/1百万4千多

那么1个数不在这一百万个数里的概率就是:1-p. from: 1point3acres.com/bbs

随机生成100个数,这100个数都不在这一百万个数的概率就是 (1-p)^100   趋近于0

时间复杂度就是 100*n咯
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-24 21:27:55 | 显示全部楼层
jaly50 发表于 2015-8-24 13:06. from: 1point3acres.com/bbs
一个数在这一百万个数里的概率是: p=1百万/1百万4千多

那么1个数不在这一百万个数里的概率就是:1-p

但是100*n并不比n log n要好啊
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-24 21:29:40 | 显示全部楼层
jaly50 发表于 2015-8-24 13:06
一个数在这一百万个数里的概率是: p=1百万/1百万4千多

那么1个数不在这一百万个数里的概率就是:1-p

但是100*n并不比n log n要好啊
回复 支持 反对

使用道具 举报

AndyLiu0429 发表于 2015-8-25 00:54:50 | 显示全部楼层
第三题用位作为bucket咋样?20个bucket。每个bucket代表相应位上为1的数量,统计后再扫一遍20个bucket,如果小于2^10,那就用1,等于的话说明0少就用0,然后就拼出来了一个数了。。时间复杂度O(20 *n),空间O(20).

补充内容 (2015-8-25 22:57):
想错了。。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-25 02:08:52 | 显示全部楼层
AndyLiu0429 发表于 2015-8-25 00:54
第三题用位作为bucket咋样?20个bucket。每个bucket代表相应位上为1的数量,统计后再扫一遍20个bucket,如 ...

很好的解法,赞!
回复 支持 反对

使用道具 举报

 楼主| jaly50 发表于 2015-8-25 10:40:49 | 显示全部楼层
AndyLiu0429 发表于 2015-8-25 00:54
第三题用位作为bucket咋样?20个bucket。每个bucket代表相应位上为1的数量,统计后再扫一遍20个bucket,如 ...

我刚刚试了一下, 0到7
0000. From 1point 3acres bbs
0001
0010.鏈枃鍘熷垱鑷1point3acres璁哄潧
0011
0100
0101
0110. 1point3acres.com/bbs
0111
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point 3acres 璁哄潧
假设我缺了 0101 和 0010两个数

按你的方法,找到的 却是0111,就不对了
回复 支持 反对

使用道具 举报

AndyLiu0429 发表于 2015-8-25 22:57:07 | 显示全部楼层
jaly50 发表于 2015-8-25 10:40 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我刚刚试了一下, 0到7
0000
0001
. 1point3acres.com/bbs
对。是错了。。。

补充内容 (2015-8-25 22:58):
而且还不如直接排序,nlogn和n*(位数)是一样的。
回复 支持 反对

使用道具 举报

D_路费 发表于 2015-9-11 03:35:59 | 显示全部楼层
jaly50 发表于 2015-8-24 13:06
一个数在这一百万个数里的概率是: p=1百万/1百万4千多
. Waral 鍗氬鏈夋洿澶氭枃绔,
那么1个数不在这一百万个数里的概率就是:1-p

这题是问有多少数字不在array里面吗?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-9-11 08:40:34 | 显示全部楼层
D_路费 发表于 2015-9-11 03:35-google 1point3acres
这题是问有多少数字不在array里面吗?

不是的,这个题只要找到一个一定范围内的且不在数组array中的数字就好了。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-9-11 09:44:55 | 显示全部楼层
楼主这个题是不是也可以考虑用类似first missing positive那个题目的方法来做呢?
回复 支持 反对

使用道具 举报

D_路费 发表于 2015-9-11 09:47:10 | 显示全部楼层
水逼一枚 发表于 2015-9-11 08:40. From 1point 3acres bbs
不是的,这个题只要找到一个一定范围内的且不在数组array中的数字就好了。

谢谢楼主!但是不太明白你说的方法怎么能够找出某一个值。。。

我能够找到比如A[0] 也就是0-999中缺少一个数。。。但我怎么知道缺少的是哪个?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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