一亩三分地论坛

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

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

Airbnb Skype 两轮

[复制链接] |试试Instant~ |关注本帖
ohyline 发表于 2016-2-17 08:32:38 | 显示全部楼层 |阅读模式

2016(1-3月) 工程类 博士 实习@Airbnb - 内推 - 技术电面 |Fail其他

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

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

x
这个算是第2轮coding了。两个skype Back2Back。

第一个: 白人姐姐。声音甜美+标准美式英语--三生有幸啊
姐姐出了text justification。 瞬秒。小typo改掉。过关。
.1point3acres缃
第二个: 华人大哥。英语很清晰。人很和蔼。稍微一点push--两生有幸。。。
哥哥出了非面经以及LC题: find median from large file of integers。
看到题目有点懵。。。乍一看是Divide Conquer。可是merge的时候不太容易。
想一想LC的median from stream。还是需要heaps来储存。。。看来不行。-google 1point3acres
百般尝试之后,小哥开始push。说可以看看median的upper bound 和lower bound。
这两个词一出不就是binary search了么。。。讲出了自己的想法,聊了一下复杂度。。。. From 1point 3acres bbs
编了一会。。。编出了bug。。。找到的median不在数组里面。。。最后发现了问题。。。想解决已经来不及了。。。
就这样挂了。。。希望还有下一个面试吧

评分

3

查看全部评分

本帖被以下淘专辑推荐:

edcent 发表于 2016-2-17 12:21:18 | 显示全部楼层
lz 能再详细说一下找 median 的解法吗?谢谢!
回复 支持 反对

使用道具 举报

 楼主| ohyline 发表于 2016-2-17 13:06:20 | 显示全部楼层
edcent 发表于 2016-2-17 12:21
lz 能再详细说一下找 median 的解法吗?谢谢!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
其实有很多对大file的处理方法。 在interview当中,华人哥哥给出的hint是用binary search
首先, 我们知道对任何大的file median of any int will between INT_MIN and INT_MAX。所以我们知道了upper bound 和lower bound。我们猜一下median might be "guess = lower+(upper-lower)/2"。 之后我们可以验证对不对。就是扫一遍这个file,看看是不是有一半的element确实小于这个数字。如果是的话,这里注意一定要返回 smallest element in the file that is larger than the guess。如果有超过一半的数据小于这个guess,可想而知用binary search的方法,下一步就是移动上线到guess-1. 反之移动下线。对吧。那么这个算法最多需要scan 32次fille对不?这个数字当时我有点含糊。但是现在想想应该是对的。
回复 支持 反对

使用道具 举报

edcent 发表于 2016-2-17 13:27:00 | 显示全部楼层
ohyline 发表于 2016-2-17 13:06
其实有很多对大file的处理方法。 在interview当中,华人哥哥给出的hint是用binary search. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
首先, 我们知 ...

哦哦 原来是这样!谢谢楼主啦!
回复 支持 反对

使用道具 举报

truffer 发表于 2016-2-18 00:40:58 | 显示全部楼层
请问楼主多久出的结果?
回复 支持 反对

使用道具 举报

 楼主| ohyline 发表于 2016-2-18 04:20:32 | 显示全部楼层
truffer 发表于 2016-2-18 00:40
请问楼主多久出的结果?
.1point3acres缃
因为median那题答得太渣了 面后两小时 迅速要求加面
回复 支持 反对

使用道具 举报

truffer 发表于 2016-2-18 04:21:36 | 显示全部楼层
ohyline 发表于 2016-2-18 04:20
因为median那题答得太渣了 面后两小时 迅速要求加面

还可以加面啊~加油加油
回复 支持 反对

使用道具 举报

cytmike 发表于 2016-2-23 03:55:36 | 显示全部楼层
谢谢面经. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
lz加油加油
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-2-23 04:13:17 | 显示全部楼层
ohyline 发表于 2016-2-17 13:06.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实有很多对大file的处理方法。 在interview当中,华人哥哥给出的hint是用binary search
首先, 我们知 ...

楼主,这是典型的quick sort的思路吧。。。or selection algorithm
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-3 11:45:44 | 显示全部楼层
ohyline 发表于 2016-2-17 13:06-google 1point3acres
其实有很多对大file的处理方法。 在interview当中,华人哥哥给出的hint是用binary search
首先, 我们知 ...

这题很tricky,我写了一下,应该是扫31次就行,最后还要根据integer的个数是奇数还是偶数分情况,二分的题目总是这样,感觉面试写对太难了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-4-12 05:35:04 | 显示全部楼层
请问第二题写代码是写哪一部分呢?应该不要写读文件的部分吧
回复 支持 反对

使用道具 举报

jeremy_sea 发表于 2016-4-26 05:16:04 | 显示全部楼层
为什么不能用median of stream的方法做?
不是一个意思么?
回复 支持 反对

使用道具 举报

18658109706 发表于 2016-8-25 05:02:06 | 显示全部楼层
我也刚刚收到了skype interview..lz能介绍下什么情况吗?你也是第一轮codePad过了然后让面这个的?是不是第一轮有瑕疵什么的所以要加面啊...
回复 支持 反对

使用道具 举报

leyichm 发表于 2016-8-25 05:17:17 | 显示全部楼层
同收到第二轮skype,,请问一下这到时候是video call还是只是语音呀?
回复 支持 反对

使用道具 举报

18658109706 发表于 2016-8-25 06:23:55 | 显示全部楼层
是规定不允许用heap?
回复 支持 反对

使用道具 举报

huwenchang8 发表于 2016-8-28 01:20:16 | 显示全部楼层
heap应该是最简单的了,楼主说的方法感觉是quick select
回复 支持 反对

使用道具 举报

Jimmy123 发表于 2016-8-29 01:14:16 | 显示全部楼层
leyichm 发表于 2016-8-25 05:17
同收到第二轮skype,,请问一下这到时候是video call还是只是语音呀?

同问,有没有可否回答下呢
回复 支持 反对

使用道具 举报

huwenchang8 发表于 2016-8-29 13:11:40 | 显示全部楼层
请问楼主,是规定了不能用heap做吗?
回复 支持 反对

使用道具 举报

seekingJob320 发表于 2016-10-1 02:39:14 | 显示全部楼层
请问楼主 skype面试是share screen吗
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-1 03:46:22 | 显示全部楼层
ohyline 发表于 2016-2-17 13:06
其实有很多对大file的处理方法。 在interview当中,华人哥哥给出的hint是用binary search
首先, 我们知 ...

谢谢楼主分享。 想请问一下楼主,等不能这样想。 固定一个guess之后扫数组时,记录两个值,smaller是小于guess的数目,larger是大于guess的数目。 如果smaller等于larger, 那就直接返回guess, 如果smaller < larger, 那就start = guess, 如果smaller > larger,那就end = mid。 这两种轻卡ugndou不排除guess依旧是median的可能性。 最后结束条件是start + 1 < end. 然后再根据start的数目多还是end这个数的数目多进行判断。

补充内容 (2016-10-1 03:54):
最后的判断应该是如果小于等于start的数目和大于等于end的数目哪个多。 一样多的话返回他俩的平均值。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 12:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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