在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 11498|回复: 16
收起左侧

完败的Airbnb 电面

[复制链接] |试试Instant~ |关注本帖
butterwang 发表于 2015-12-2 06:08:54 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类General 博士 全职@Airbnb - 网上海投 - 技术电面  | Fail | fresh grad应届毕业生

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

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

x
一直以为airbnb 电面以面经为主,花了整整一个礼拜看以前的面经,结果出了一个新题。。光搞清楚题就花了好久。。。小哥冷冷的,一点提示都没有,最后代码都没写完。
不说废话,直接上题。

游客,本帖隐藏的内容需要积分高于 133 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


我一开始给了一个brute force, 就是穷据,复杂度2^n. 但是小哥说有更快的解法。。试了好几个都没做出来。看看大家能不能想出来。

最后说说教训吧,上周一直在看A家面经,看到的一共就10来道,一个论坛有很不错的总结。http://buttercola.blogspot.com/search/label/Airbnb
其实做他家面经的时候就感觉比较吃力了,像LC里的text justification, regular expression matching在他家都算是热身题,感觉大部分题自己都不能独立做出来,比如csv parser, 之类。
Anyway, 牢骚了一堆,其实还是自己能力达不到A家的要求。后天还有Z家onsite,继续看书去了。。。

评分

3

查看全部评分

本帖被以下淘专辑推荐:

  • · 2016 Airbnb|主题: 65, 订阅: 41
  • · AB|主题: 9, 订阅: 0
hyliu0000 发表于 2015-12-2 06:43:39 | 显示全部楼层
butterwang 发表于 2015-12-2 06:36
应该不行。我试过DP 但状态转移方程退不下去。。其实这题不太难。我还是等大家想了以后再说吧。。方法有 ...

这样对吗?
1. 先将所有的x取floor, 然后T - sum(floor(x)) 得到多少个x需要ceil
2. 按照小数部分将数组排序,从大到小ceil,其他的floor。 最后就是想要的结果。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

victor2100 发表于 2015-12-2 06:43:04 | 显示全部楼层
这题贪心应该就可以解决
来源一亩.三分地论坛.
先对每个element进行round(向最小的那边进行round   ceil或者floor)
然后把值加起来  如果和T有个差值  比T大或者小X
. visit 1point3acres for more.
如果比T大(小同理),我们可以对那些取ceil 的element,
按照这个element和它floor的差值从小到大排个序
从小到大取X个elements 取 floor就可以得到T。


回复 支持 2 反对 0

使用道具 举报

coolidgelyt 发表于 2015-12-2 06:49:50 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

neal1st 发表于 2015-12-2 06:29:43 | 显示全部楼层
不知道DP是不是可以解?因为对于每个yi,只有两种选择。
回复 支持 反对

使用道具 举报

 楼主| butterwang 发表于 2015-12-2 06:36:26 | 显示全部楼层
neal1st 发表于 2015-12-2 06:29
不知道DP是不是可以解?因为对于每个yi,只有两种选择。

应该不行。我试过DP 但状态转移方程退不下去。。其实这题不太难。我还是等大家想了以后再说吧。。方法有点tricky 如果面试小哥肯提示就做出来了
回复 支持 反对

使用道具 举报

 楼主| butterwang 发表于 2015-12-2 06:47:22 | 显示全部楼层
hyliu0000 发表于 2015-12-2 06:43
这样对吗?
1. 先将所有的x取floor, 然后T - sum(floor(x)) 得到多少个x需要ceil
2. 按照小数部分 ...

差不多啊。厉害啊,大牛!!当时真的就想不到。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-2 06:49:20 | 显示全部楼层
butterwang 发表于 2015-12-2 06:47-google 1point3acres
差不多啊。厉害啊,大牛!!当时真的就想不到。

面试的时候都紧张啊。 我这是没压力的情况下。。
回复 支持 反对

使用道具 举报

不要说话 发表于 2015-12-2 09:31:55 | 显示全部楼层
这是面经原题 我也面的这道题 贪心算法可以 把数组以小数点后的数从大到小排序 greedy做就可以
回复 支持 反对

使用道具 举报

 楼主| butterwang 发表于 2015-12-2 10:30:17 | 显示全部楼层
coolidgelyt 发表于 2015-12-2 06:49
这道题面经里有呀楼主。http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=146539&extra=page ...

哎 这就是缘分未到啊。。我看了地里所有的面镜 每题还仔细做了一下 居然这题没看出来
回复 支持 反对

使用道具 举报

Rudy 发表于 2015-12-9 09:51:10 | 显示全部楼层
电面第一面也是这道题,用的O(2^n)的方法……就给过了,真是看运气啊。
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-25 07:24:18 | 显示全部楼层
如果用selection sort的方法 可以达到O(n) 结合 victor2100 的方法
回复 支持 反对

使用道具 举报

罗大宝 发表于 2016-2-27 05:37:50 | 显示全部楼层
hyliu0000 发表于 2015-12-2 06:43. 留学申请论坛-一亩三分地
这样对吗?
1. 先将所有的x取floor, 然后T - sum(floor(x)) 得到多少个x需要ceil-google 1point3acres
2. 按照小数部分 ...
. 1point3acres
对对 我也面到了这道题 就是这么解的
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-27 07:30:00 | 显示全部楼层
LifeGoesOn 发表于 2015-12-25 07:24
如果用selection sort的方法 可以达到O(n) 结合 victor2100 的方法

好解法。
回复 支持 反对

使用道具 举报

hwy 发表于 2016-10-25 06:06:26 | 显示全部楼层
刚面完这题,之前没看过这一题,面试的思路都对了,写得磕磕绊绊的,缘分未到T T
回复 支持 反对

使用道具 举报

王饱饱 发表于 2017-1-19 13:24:00 | 显示全部楼层
感谢楼主。最近开始准备刷A家的题了
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-23 15:43

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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