《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,你要不要来?
把贵司招聘信息放这里
查看: 8532|回复: 23
收起左侧

A9电面面经

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

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

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

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

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
For example. 鍥磋鎴戜滑@1point 3 acres
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]
.1point3acres缃
follow up:  protect your function against malicious inputs
. visit 1point3acres.com for more.
2.Given 3 array of Strings. .鐣欏璁哄潧-涓浜-涓夊垎鍦

Array one = {Red, Green, Blue}
Array two = {Large, Medium, Small}
Array three={giant, monster}. 鍥磋鎴戜滑@1point 3 acres
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Print out combinations of all three array.

public void combination(String[][] arrays) {}

3.
Given an array of 1,000,000 integers where each integer is between 0 and 2^20 - 1
Find one integer that is between 0 and 2^20 -1 that is not in the array. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
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`;
不过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+年……

投了四五个职位的样子

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

-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
投了四五个职位的样子
. 1point3acres.com/bbs
给我回应的 好像是一个大数据分析的职位吧

感谢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个职位,简历是同一份?还是都要改一下?谢谢

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

使用道具 举报

 楼主| jaly50 发表于 2015-8-24 13:03:39 | 显示全部楼层
Augustus 发表于 2015-8-24 10:30
小弟愚见,第三题自己建一个hash table,时间复杂度n,空间复杂度n,但是感觉应该还能优化,求楼主告知。。。
. visit 1point3acres.com for more.
1百万个数
分1000个bucket装,每个bucket装1000个数. from: 1point3acres.com/bbs
用一个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

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

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

使用道具 举报

wenqiang88 发表于 2015-8-24 21:27:55 | 显示全部楼层
jaly50 发表于 2015-8-24 13:06
一个数在这一百万个数里的概率是: 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.鏈枃鍘熷垱鑷1point3acres璁哄潧
0001. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
0010
0011
0100. more info on 1point3acres.com
0101
0110
0111. 1point3acres.com/bbs

. 1point3acres.com/bbs
假设我缺了 0101 和 0010两个数

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

使用道具 举报

AndyLiu0429 发表于 2015-8-25 22:57:07 | 显示全部楼层
jaly50 发表于 2015-8-25 10:40
我刚刚试了一下, 0到7
0000
0001

对。是错了。。。

补充内容 (2015-8-25 22:58):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
而且还不如直接排序,nlogn和n*(位数)是一样的。
回复 支持 反对

使用道具 举报

D_路费 发表于 2015-9-11 03:35:59 | 显示全部楼层
jaly50 发表于 2015-8-24 13:06
一个数在这一百万个数里的概率是: p=1百万/1百万4千多

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

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

使用道具 举报

水逼一枚 发表于 2015-9-11 08:40:34 | 显示全部楼层
D_路费 发表于 2015-9-11 03:35
这题是问有多少数字不在array里面吗?
-google 1point3acres
不是的,这个题只要找到一个一定范围内的且不在数组array中的数字就好了。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

谢谢楼主!但是不太明白你说的方法怎么能够找出某一个值。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-18 02:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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