推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1230|回复: 3
收起左侧

[找工就业] Airbnb Skype 新题

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

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

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

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

x
Skype两轮,第一轮word search,要求output最多的词并且词与词之间在board上不重合。第二轮新题,也可能是老题,但我翻近期的面经贴没看到过:
Given a very large array, which you could only do sequencial access, not random access. Find out the medium of the array.

我面试经验不足,花了很久理解什么叫“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。. visit 1point3acres.com for more.

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

评分

1

查看全部评分

oldfish 发表于 2016-11-9 05:03:09 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
找 median 我第一反应是用俩 heap,不过空间复杂度太高了。还是 binary search 靠谱。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外,时间复杂度应该是 nlogn 吧
回复 支持 反对

使用道具 举报

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

使用道具 举报

一只小威 发表于 2016-12-15 10:53:07 | 显示全部楼层
谢面经!!!楼主onsite了嘛
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-25 14:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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