一亩三分地论坛

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

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

[找工就业] Airbnb Skype 新题

[复制链接] |试试Instant~ |关注本帖
jinger8910 发表于 2016-11-9 04:42:52 | 显示全部楼层 |阅读模式

2017(10-12月)-[15]CS硕士+<3个月短暂实习/全职 - 内推| 码农类全职@Airbnbfresh grad应届毕业生

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

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

x
Skype两轮,第一轮word search,要求output最多的词并且词与词之间在board上不重合。第二轮新题,也可能是老题,但我翻近期的面经贴没看到过:. visit 1point3acres.com for more.
Given a very large array, which you could only do sequencial access, not random access. Find out the medium of the array.
. 1point 3acres 璁哄潧
我面试经验不足,花了很久理解什么叫“could only do sequencial access, not random access”,说白了就是只能遍历array,不能access array by given index. 后来面试官给了思路:遍历len/2次array,每次找到max,然后下次找剩余element的max. 第len/2次得到的max就是medium。接着面试官说可以log n解,方法是pick up a number by random (我面试时理解的是pick up an index by random, 后来想想因为不能random access所以估计是直接生成一个random number),过一遍array,count number of elements smaller than our guess. 如果count结果大于len/2,说明guess number大了,因此next round guess = (min of array + guess) / 2. 于是变成binary search。

据说这道题是uber的常考题,但先前也没有看过uber面经。花了将近一周把airbnb每道面经题都写了两遍,可惜都没用上。面试以来诸多不顺,有时看地里的帖子会觉得每个人都难免有起有落,心里稍微好受点。希望与大家共勉吧。

评分

1

查看全部评分

oldfish 发表于 2016-11-9 05:03:09 | 显示全部楼层
找 median 我第一反应是用俩 heap,不过空间复杂度太高了。还是 binary search 靠谱。

另外,时间复杂度应该是 nlogn 吧
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-12 05:04:26 | 显示全部楼层
楼主加油,总会守得云开见明月。共勉
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 08:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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