一亩三分地论坛

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

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

airbnb电面

[复制链接] |试试Instant~ |关注本帖
abcd1992719g 发表于 2016-9-1 10:33:08 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Airbnb - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
题目是这样的,数据库里有一堆数据  string[]
host_id  listing_id score ..... 1point 3acres 璁哄潧
"10,             1,        1000.0"
"10,               3          999.5"
"9               2         999.0"
"15           999           858"
"10             5           747.0"
...
有n条record, 然后是按score排好序的.每个记录都是一个string. 然后要生成我们的page, 比如有个参数max_item_per_page,如果是10,就表示每页最多10个. 要求是每页不能有重复的host_id, 然后优先按score取.
. more info on 1point3acres.com比如参数是3, 有上面5条记录. 那么第一页是第1,3, 4条数据, 第二页是第3条, 第3页是最后一条.

我首先说用naive算法实现, 每生成一个page从头到尾遍历, 用hash去分别记录哪些item被用过以及用一个local hash记录当前page有哪些host_id. 然后bugfree就出结果了.

面试官说这样太慢了, 怎么改进. 我说把record_id {1...n} 存到set中, 每次用掉就剔除, set是排序的所以score也是没问题的. 然后也写了代码.

然后他又说, 你发现没有,按上面的例子, 第二页跟第三页是不完整的, 页面没有填满. 你觉得这样好吗. 我说当然不好, 应该尽量填满, airbnb网站肯定都是尽量填满. 然后他修改了requirement, 一开始每页不能有重复的host_id,但是如果一页没有满,那么这个规则取消. 所以我稍微修改了以前的代码, 当一个page生成后不满时, 从set中取begin()直到取满, 然后该页面内的record再按score排个序. 也写了代码...

他又说放到set中还要排序,有没有什么办法不排序. 我说那就放到vector中.....也写了代码....但是每次删的代价大概是O(n)......
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
收到拒信妥妥的跪了.....LOL
. more info on 1point3acres.com

补充内容 (2016-9-1 10:33):
第二页是第2条. more info on 1point3acres.com

补充内容 (2016-9-2 13:12):
求star 求follow  https://github.com/gzc/CLRS
wtcupup 发表于 2016-9-1 10:55:22 | 显示全部楼层
楼主怎么找的内推啊?
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-9-1 10:58:21 | 显示全部楼层
wtcupup 发表于 2016-9-1 10:55
楼主怎么找的内推啊?
.1point3acres缃
Google Intern群里认识个人就帮忙推了
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-1 13:20:28 | 显示全部楼层
楼主是都写出来了吗? 我觉得面得挺好的呀, 为啥会跪?
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-9-1 13:28:30 | 显示全部楼层
小A要当码农 发表于 2016-9-1 13:20
楼主是都写出来了吗? 我觉得面得挺好的呀, 为啥会跪?

不知道 hr也没说理由 就是模板拒
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-9-2 14:19:01 | 显示全部楼层
abcd1992719g 发表于 2016-9-1 13:28
不知道 hr也没说理由 就是模板拒

摸摸, 感觉这个面试官不是很nice
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 18:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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