聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 6686|回复: 39
收起左侧

Airbnb Skype一轮

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

2016(10-12月) 码农类General 硕士 全职@Airbnb - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
刚刚面完,赶快发个面经压压惊。面试官是个三哥大爷,上来就做题,是这道题。
给一个map,涗汉浜戦泦,

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| wilsonli 发表于 2016-11-29 14:32:45 | 显示全部楼层
gy21 发表于 2016-11-29 14:26
DCD or CCD 之后 DC或者CC不再组合了吗?而是直接跳过去了???

这是一个一层一层generate的过程。最下面一层是input:ABCD。那么倒数第二层就是CAB,或者DAB。那么再上一层就是AC/AD/BC/BD/CC/DD。最顶端就是D/B/A/C。每一层的每两个相邻的字母会generate出来什么字母去表里查。
回复 支持 1 反对 0

使用道具 举报

gy21 发表于 2016-11-29 07:43:04 | 显示全部楼层
lz题目在哪里。。。。。。。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-29 07:46:54 | 显示全部楼层
楼主能补充下吗?谢谢了
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 07:47:08 | 显示全部楼层
之前写了好多都没发出来,不知道怎么回事。.留学论坛-一亩-三分地

题目:
   A   B   C  D
A AC CD D  B
B B   C   A  CD
C A   C   D  B
D BC D   A  C.鐣欏?璁哄潧-涓
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 07:47:24 | 显示全部楼层

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

然后给定最低层的叶子结点 A B C D
.1point3acres网
那么倒数第二层就只可能是  D A B 和 C A B 两种,因为A B -> CD
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 07:49:19 | 显示全部楼层
然后给一个rule string 比如 CD,问你所有可能的顶端字母中又没有任何一个出现在这个rule string里面。
. 一亩-三分-地,独家发布
三大爷给的思路是,先generate next level, 然后再判断有没有。
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 10:37:56 | 显示全部楼层
梦醒的我 发表于 2016-11-29 10:36
就是brute force的做法吗?

是的。有没有什么更好的方法?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-29 11:11:37 | 显示全部楼层
wilsonli 发表于 2016-11-29 07:47
i,j 以为着左孩子是i,右孩子是j的时候,父亲结点的可能值

然后给定最低层的叶子结点 A B C D

再问下楼主,A B C D这种格式是意味着 A B 是一个节点的左右孩子, C D 是一个节点的左右孩子吗? 谢谢
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 11:13:25 | 显示全部楼层
梦醒的我 发表于 2016-11-29 10:57
不知道呢,可能可以memoization一下?不过感觉bnb更注重把题做出来,对complexity要求不是很高

最后确实做出来了,内心虽然是崩溃的,但是希望能过吧。
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 11:15:47 | 显示全部楼层
jy_121 发表于 2016-11-29 11:11
再问下楼主,A B C D这种格式是意味着 A B 是一个节点的左右孩子, C D 是一个节点的左右孩子吗? 谢谢
来源一亩.三分地论坛.
其实是这样,比如给你一个string “AABB”。 那每个字母这个就是最下面一行的节点,也就是说最下面一行的节点是 A, A, B, B. 所以A,A这一对在表里对应着一个string,比如是AC,那么由A,A这一对子节点所能产生的父节点就是C或者是A。
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-29 13:53:44 | 显示全部楼层
wilsonli 发表于 2016-11-28 15:47
i,j 以为着左孩子是i,右孩子是j的时候,父亲结点的可能值. Waral 博客有更多文章,

然后给定最低层的叶子结点 A B C D

AB可以形成CD的话 那不就应该是CCD or DCD吗?
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 13:56:37 | 显示全部楼层
gy21 发表于 2016-11-29 13:53
AB可以形成CD的话 那不就应该是CCD or DCD吗?

AB形成CD,然后BC形成A,CD形成B,所以第三层应该是CAB,或者DAB。以此类推。
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-29 14:26:55 | 显示全部楼层
wilsonli 发表于 2016-11-28 21:56
AB形成CD,然后BC形成A,CD形成B,所以第三层应该是CAB,或者DAB。以此类推。
. Waral 博客有更多文章,
DCD or CCD 之后 DC或者CC不再组合了吗?而是直接跳过去了???
. From 1point 3acres bbs
补充内容 (2016-11-28 22:32):-google 1point3acres
忽略我的提问,我懂了。。。。。。
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-29 14:40:06 | 显示全部楼层
wilsonli 发表于 2016-11-28 22:32
这是一个一层一层generate的过程。最下面一层是input:ABCD。那么倒数第二层就是CAB,或者DAB。那么再上 ...

这个表输入的时候是个二维数组吗?自己要遍历坐标去得到相应的字符?lz好人!!有什么followup吗???
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 14:44:05 | 显示全部楼层
gy21 发表于 2016-11-29 14:40
这个表输入的时候是个二维数组吗?自己要遍历坐标去得到相应的字符?lz好人!!有什么followup吗???

所有输入都得自己写,我就用一个2dvector写了,坐标就是’A'代表0, 所以你要是查‘AA’对应是什么,就是matrix里的[0][0]。很简单。我做完以后都差不多到时间了,没有followup了,你要是秒了那可能会问你怎么优化吧。good luck!
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-11-30 02:01:49 | 显示全部楼层
wilsonli 发表于 2016-11-29 11:15
其实是这样,比如给你一个string “AABB”。 那每个字母这个就是最下面一行的节点,也就是说最下面一行的 ...

明白了,多谢!
回复 支持 反对

使用道具 举报

jizhoutong 发表于 2016-11-30 02:17:32 | 显示全部楼层
哈  题是啥呢
回复 支持 反对

使用道具 举报

goodluck888 发表于 2016-12-2 14:03:41 | 显示全部楼层
wilsonli 发表于 2016-11-29 07:49
然后给一个rule string 比如 CD,问你所有可能的顶端字母中又没有任何一个出现在这个rule string里面。. 1point3acres

...

lz,请问是说从叶结点向上推,最后看root在不在cd里吗?还是说有没有一层的substring是cd?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-12-3 07:46:00 | 显示全部楼层
问下楼主有消息了吗?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-22 16:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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