一亩三分地论坛

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

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

完败的Airbnb 电面

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

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

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

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

x
一直以为Airbnb 电面以面经为主,花了整整一个礼拜看以前的面经,结果出了一个新题。。光搞清楚题就花了好久。。。小哥冷冷的,一点提示都没有,最后代码都没写完。. 鍥磋鎴戜滑@1point 3 acres
不说废话,直接上题。

Given an array of numbers A = [x1, x2, ..., xn] and T = Round(x1+x2+... +xn).
We want to find a way to round each element in A such that after rounding we get a new array B = [y1, y2, ...., yn] such that y1+y2+...+yn = T where  yi = Floor(xi) or Ceil(xi), ceiling or floor of xi.
We also want to minimize sum |x_i-y_i|


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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

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

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

victor2100 发表于 2015-12-2 06:43:04 | 显示全部楼层
这题贪心应该就可以解决

先对每个element进行round(向最小的那边进行round   ceil或者floor)
然后把值加起来  如果和T有个差值  比T大或者小X

如果比T大(小同理),我们可以对那些取ceil 的element,
按照这个element和它floor的差值从小到大排个序
从小到大取X个elements 取 floor就可以得到T。


回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| butterwang 发表于 2015-12-2 06:36:26 | 显示全部楼层
neal1st 发表于 2015-12-2 06:29-google 1point3acres
不知道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. 按照小数部分 ...
-google 1point3acres
差不多啊。厉害啊,大牛!!当时真的就想不到。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

不要说话 发表于 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
2. 按照小数部分 ...

对对 我也面到了这道题 就是这么解的
回复 支持 反对

使用道具 举报

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
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 17:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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