一亩三分地论坛

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

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

11.18 Airbnb Onsite

[复制链接] |试试Instant~ |关注本帖
bearcat001 发表于 2016-11-20 16:10:19 | 显示全部楼层 |阅读模式

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

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

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

x
最后一个面试,终于可以停止刷题去好好做点别的事情了 0 - 0 虽然是在SF面试,但是我面的职位在西雅图
第一轮技术面,又是遇到没准备的题 - = - 似乎面经有人提过一次,就是那个随机生成树的题。给一个满二叉树的所有叶子,比如 A B C D E F, 然后给一个map,记录了左右孩子分别给了的时候,父亲节点可能的值。例如 左 A 右 B =》 AC,意味着倒数第二层第一个节点可以是A或者是C。然后要求是给几个字母,问这个树的root节点是否可能是这几个字母之一。用最brute force的方式写的,一层递归一层BFS,感觉面试官不是很满意,讨论了一会儿记忆化搜索。感觉这个题应该有更好的解法,因为毕竟不需要构造树

第二轮和第三轮都是behavior,就是常见的一些问题,往Airbnb上面靠就好,尤其是讲讲自己以前用Airbnb的经历面试官看起来比较开心

Airbnb感觉氛围确实不错,办公室也漂亮。我见过的面试官都很开心,看来他们都很满意自己的工作。
. more info on 1point3acres.com

-google 1point3acres


补充内容 (2016-12-6 10:51):
今天收到通知说过了,不可思议啊,最后加面那么烂 T_T  然后HR也同意帮忙转到湾区了~

评分

5

查看全部评分

alphard 发表于 2016-11-22 01:32:16 | 显示全部楼层
梦醒的我 发表于 2016-11-22 00:23. more info on 1point3acres.com
请问如何把AB->A|C变成chomsky normal form呢,不是很懂A->AB,C->AB怎么来的。。比如原来是AB的可以变成C ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
是倒过来的,A->AB, C->AB表示AB这个串可以规约为A或者C,所以dp循环就应该长这样
for 长度. From 1point 3acres bbs
    for 起点
        // 原算法,这里似乎不需要这重循环 for 中点. 鍥磋鎴戜滑@1point 3 acres
            for 每个产生式 P: X->YZ. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                如果dp(起点到长度-1,Y)和dp(起点+1到长度,Z)
                    dp(起点到长度,X) = true

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

 楼主| bearcat001 发表于 2016-11-21 05:34:09 | 显示全部楼层
详细说一下题目:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
给的map是这个样子的
   A   B   C  D
A AC CD D  B
B B   C   A  CD
C A   C   D  B
D BC D   A  C

i,j 以为着左孩子是i,右孩子是j的时候,父亲结点的可能值

然后给定最低层的叶子结点 A B C D
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
那么倒数第二层就只可能是  D A B 和 C A B 两种,因为A B -> CD

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

zyoppy008 发表于 2016-11-20 16:36:19 | 显示全部楼层
并没看懂第一题的map
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-21 01:14:22 | 显示全部楼层
请问楼主, 第一题的具体规则是, 比如ABCD是输入, 那第一层是AB map到一个字符连上接下来的CD继续呢, 还是AB, BC, CD各Map一次, 拼在一起继续呢? 多谢
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-21 01:51:29 | 显示全部楼层
感谢分享,关注下这道题的解法。。。
回复 支持 反对

使用道具 举报

 楼主| bearcat001 发表于 2016-11-21 05:34:39 | 显示全部楼层
zyoppy008 发表于 2016-11-20 16:36
并没看懂第一题的map

详细的我放在回复里面了
回复 支持 反对

使用道具 举报

 楼主| bearcat001 发表于 2016-11-21 05:34:46 | 显示全部楼层
小A要当码农 发表于 2016-11-21 01:14
请问楼主, 第一题的具体规则是, 比如ABCD是输入, 那第一层是AB map到一个字符连上接下来的CD继续呢, 还 ...
. 1point3acres.com/bbs
详细的我放在回复里面了
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-11-21 05:35:36 | 显示全部楼层
bearcat001 发表于 2016-11-21 05:34
详细的我放在回复里面了

好的 了解了。。 多谢~
回复 支持 反对

使用道具 举报

alphard 发表于 2016-11-21 11:25:05 | 显示全部楼层
dp. CYK algorithm
输入的map可以转换成生成式,比如左A右B对应AC,则有对应产生式A->AB, C->AB,接下来就是普通dp了,参见cyk算法
回复 支持 反对

使用道具 举报

mwang29 发表于 2016-11-21 11:43:20 | 显示全部楼层
楼主只有一道coding题么?
回复 支持 反对

使用道具 举报

 楼主| bearcat001 发表于 2016-11-21 13:09:26 | 显示全部楼层
alphard 发表于 2016-11-21 11:25
dp. CYK algorithm
输入的map可以转换成生成式,比如左A右B对应AC,则有对应产生式A->AB, C->AB,接下来就 ...

赞,多谢分享!
回复 支持 反对

使用道具 举报

 楼主| bearcat001 发表于 2016-11-21 13:09:35 | 显示全部楼层
mwang29 发表于 2016-11-21 11:43. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主只有一道coding题么?

是的,就一题
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-22 00:23:39 | 显示全部楼层
alphard 发表于 2016-11-21 11:25 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
dp. CYK algorithm. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
输入的map可以转换成生成式,比如左A右B对应AC,则有对应产生式A->AB, C->AB,接下来就 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
请问如何把AB->A|C变成chomsky normal form呢,不是很懂A->AB,C->AB怎么来的。。比如原来是AB的可以变成C但用新的grammar只能变成AAAA...B啊?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-22 00:38:44 | 显示全部楼层
airbnb onsite就3轮么?只有1轮coding?
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-22 02:51:22 | 显示全部楼层
alphard 发表于 2016-11-22 01:32
是倒过来的,A->AB, C->AB表示AB这个串可以规约为A或者C,所以dp循环就应该长这样
for 长度
    for 起 ...

啊!有道理!谢谢!
回复 支持 反对

使用道具 举报

 楼主| bearcat001 发表于 2016-11-22 14:33:41 | 显示全部楼层
收到behavior的加面 :) 看来这家公司真是很要求culture match
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-23 06:11:10 | 显示全部楼层
bearcat001 发表于 2016-11-22 14:33
收到behavior的加面 :) 看来这家公司真是很要求culture match

楼主还记得behavior具体问了哪些题吗?谢谢!祝offer!
回复 支持 反对

使用道具 举报

 楼主| bearcat001 发表于 2016-11-23 06:23:02 | 显示全部楼层
梦醒的我 发表于 2016-11-23 06:11
楼主还记得behavior具体问了哪些题吗?谢谢!祝offer!

为啥选Airbnb,说说之前的Airbnb经历,有啥哪些人的善举让你记忆深刻,给你教员工的机会你会教什么内容,有什么人生的挫折之后你缓过来了的。还有些记不起来了... 30分钟问不了几个
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-23 06:29:53 | 显示全部楼层
bearcat001 发表于 2016-11-23 06:23
为啥选Airbnb,说说之前的Airbnb经历,有啥哪些人的善举让你记忆深刻,给你教员工的机会你会教什么内容, ...

谢谢lz!lz好人!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 23:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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