传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 2544|回复: 5
收起左侧

airbnb电面

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

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

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

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

x
题目是这样的,数据库里有一堆数据  string[] 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
host_id  listing_id score ..... more info on 1point3acres.com
"10,             1,        1000.0"
"10,               3          999.5"
"9               2         999.0". 1point 3acres 璁哄潧
"15           999           858".鐣欏璁哄潧-涓浜-涓夊垎鍦
"10             5           747.0". from: 1point3acres.com/bbs
...
有n条record, 然后是按score排好序的.每个记录都是一个string. 然后要生成我们的page, 比如有个参数max_item_per_page,如果是10,就表示每页最多10个. 要求是每页不能有重复的host_id, 然后优先按score取.. 1point3acres.com/bbs
比如参数是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


补充内容 (2016-9-1 10:33):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二页是第2条
. From 1point 3acres bbs
补充内容 (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. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主怎么找的内推啊?
. visit 1point3acres.com for more.
Google Intern群里认识个人就帮忙推了
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| abcd1992719g 发表于 2016-9-1 13:28:30 | 显示全部楼层
小A要当码农 发表于 2016-9-1 13:20 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主是都写出来了吗? 我觉得面得挺好的呀, 为啥会跪?
. visit 1point3acres.com for more.
不知道 hr也没说理由 就是模板拒
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-22 05:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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