一亩三分地论坛

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

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

Airbnb Onsite

[复制链接] |试试Instant~ |关注本帖
wegnahz 发表于 2015-11-4 04:45:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Airbnb - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
上周面的Airbnb已挂,既然你不给我offer那我就把题说了……语文不好题难描述请见谅……

三个coding面两个core value面。

1. 见下图 。给你一个字符对的转换matrix,表示这个字符对会转化成一个字符(但是有的字符对可能有多个能够转化成的字符,原文是nondeterministic)。以及若干个合法的终点(最顶上那一个点)状态,多次询问,每次一个字符串如果有一个方法能够走到合法状态就算是YES,否则NO
解法:记忆化搜索,记录所有中间状态。因为转化矩阵和合法终点都是固定的,某个字符串要不永远是YES,要不永远是NO。最好写个类因为他后来说的……

2. N个员工,每个员工有若干个interval表示在这段时间是忙碌的。求所有员工都不忙的intervals
解法:这题最简单的方法就是把所有区间都拆成两个点,然后排序,然后扫描,每次碰到一个点如果是左端点就把busy_employees加1,否则减1,等到每次busy_employees为0时就是一个新的区间。这样复杂度O(MlogM),M是总共区间数。
但是我当时也不知道是脑抽了还是脑子太好用了,弄了个堆的,堆里N个元素,存每个员工的下一个端点,如果堆顶是某个员工的左端点就busy_employees加1,否则减1。这样好处是时间复杂度低了一点点,坏处是给面试官讲了半天而且代码不是太好写……不建议这么做.1point3acres缃


3. 见图,忘了这东西叫什么名字了。每次给你一个(x, y, iter),问你在iter这张图中在(x, y)坐标的点是第几个?
解法:从大往小左,逐渐细化。每次先算出当前点在当前iter是在第几象限,先加上前面那些跳过去的象限里的点。然后找到这个点在这个象限的相对坐标新(x,y),但是还不够!对于三四象限的点,因为方向变了,需要做镜面映射,把(x,y)映射成(y,x) (第三象限) 或 (M-y, M-x) (第四象限),M是象限的长宽。

core value面完全就是问些莫名其妙的东西,比如你想去哪旅游。当然有一点要注意,Airbnb的优点不少在于便宜!而是在于能够更好的了解local culture,不管你认不认同都要这么说……


IMG_20151103_154052.jpg



补充内容 (2015-11-4 04:46):. 鍥磋鎴戜滑@1point 3 acres
最后一句话打错了,是“不是在于便宜”

评分

10

查看全部评分

本帖被以下淘专辑推荐:

woaibai 发表于 2015-11-4 12:26:47 | 显示全部楼层
没有design?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-4 12:27:16 | 显示全部楼层

没有,简历都不怎么问
回复 支持 反对

使用道具 举报

mobileworld 发表于 2015-11-4 14:09:01 | 显示全部楼层
wegnahz 发表于 2015-11-4 12:27
没有,简历都不怎么问
. From 1point 3acres bbs
感觉楼主答得可以啊,air家这么挑剔?
回复 支持 反对

使用道具 举报

lijing2441 发表于 2015-11-4 15:52:00 | 显示全部楼层
第三题是hilbert curve吧。。。
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 01:12:51 | 显示全部楼层
mobileworld 发表于 2015-11-4 14:09
感觉楼主答得可以啊,air家这么挑剔?

代码写的不是很顺利,第三题我当时自己也没完全弄明白太绕了
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 01:13:04 | 显示全部楼层
lijing2441 发表于 2015-11-4 15:52
第三题是hilbert curve吧。。。

对我就想不起这个名字……
回复 支持 反对

使用道具 举报

mobileworld 发表于 2015-11-5 01:16:51 | 显示全部楼层
wegnahz 发表于 2015-11-5 01:12
代码写的不是很顺利,第三题我当时自己也没完全弄明白太绕了

对,确实很绕!
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对了,我过了电面,要准备onsite. 看他们家的面经,似乎觉得onsite的题目一般比电面的要难一点。不知道你有没有这个感觉? 多谢!
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 04:39:19 | 显示全部楼层
mobileworld 发表于 2015-11-5 01:16
对,确实很绕!

对了,我过了电面,要准备onsite. 看他们家的面经,似乎觉得onsite的题目一般比电面的 ...

有,确实要难一点,而且一不小心写出bug就很囧。我个人觉得编译错误什么的无所谓, 但是bug就不大好。
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-5 04:39:32 | 显示全部楼层
mobileworld 发表于 2015-11-5 01:16
对,确实很绕!

对了,我过了电面,要准备onsite. 看他们家的面经,似乎觉得onsite的题目一般比电面的 ...

有,确实要难一点,而且一不小心写出bug就很囧。我个人觉得编译错误什么的无所谓, 但是bug就不大好。
回复 支持 反对

使用道具 举报

lijing2441 发表于 2015-11-5 17:40:09 | 显示全部楼层
wegnahz 发表于 2015-11-5 04:39. 鍥磋鎴戜滑@1point 3 acres
有,确实要难一点,而且一不小心写出bug就很囧。我个人觉得编译错误什么的无所谓, 但是bug就不大好。

个人感觉不是逻辑bug就还好,小bug倒是没关系,当场不用他提醒就自己改过来就ok。我三轮有一轮,index总是忘了加1或者忘了减1 ,不过最后也过了。
.1point3acres缃
当然,如果是逻辑bug就没什么好说的了。
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-11-6 00:18:54 | 显示全部楼层
第一题我有些没看明白,所谓合法的终点到底在你的图例中是否指的是A,B,C,D的上面那一排?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-6 01:47:58 | 显示全部楼层
zhouyoung1124 发表于 2015-11-6 00:18
第一题我有些没看明白,所谓合法的终点到底在你的图例中是否指的是A,B,C,D的上面那一排?

终点就是只剩下一个字符的时候。在图里如果这个字符是C或者D就算合法的
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-11-6 11:40:21 | 显示全部楼层
lz能不能细说一下第一题是什么意思. 完全没看懂...input,output分别是什么?为什么图中有个accept?那个是矩阵,是input吗?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-6 16:58:38 | 显示全部楼层
nothingtrouble 发表于 2015-11-6 11:40
lz能不能细说一下第一题是什么意思. 完全没看懂...input,output分别是什么?为什么图中有个accept?那个是 ...

可以想象成一个类,构造函数会把矩阵和accept传进去,然后每次的input是一个字符串。这个字符串经过若干次变换,每次变换长度减1,最后变成只有一个字符。Accept里面的任何一个字符都可以成为一个合法的最终状态
回复 支持 反对

使用道具 举报

hzding621 发表于 2015-11-6 17:40:04 | 显示全部楼层
第一题其实就是NFA to DFA transformation
回复 支持 反对

使用道具 举报

大傻杨 发表于 2015-11-8 19:14:43 | 显示全部楼层
同跪,同跪,同跪,
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-11-13 06:58:24 | 显示全部楼层
a家onsite说是现场编程必须一遍过?可以自己看bug 但是如果通过跑测试再调程序就基本没戏了?
回复 支持 反对

使用道具 举报

 楼主| wegnahz 发表于 2015-11-17 04:55:53 | 显示全部楼层
woaibai 发表于 2015-11-13 06:58
a家onsite说是现场编程必须一遍过?可以自己看bug 但是如果通过跑测试再调程序就基本没戏了?

基本上是这样的,但其实脸也很重要
回复 支持 反对

使用道具 举报

woaibai 发表于 2015-11-17 05:21:32 | 显示全部楼层
wegnahz 发表于 2015-11-16 15:55
基本上是这样的,但其实脸也很重要

意思是长得难看的可以不用试了吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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