一亩三分地论坛

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

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

Airbnb Skype一轮

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

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

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

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

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| 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 | 显示全部楼层
之前写了好多都没发出来,不知道怎么回事。. 1point 3acres 璁哄潧

题目:. 鍥磋鎴戜滑@1point 3 acres
   A   B   C  D. visit 1point3acres.com for more.
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

那么倒数第二层就只可能是  D A B 和 C A B 两种,因为A B -> CD
回复 支持 反对

使用道具 举报

 楼主| wilsonli 发表于 2016-11-29 07:49:19 | 显示全部楼层
然后给一个rule string 比如 CD,问你所有可能的顶端字母中又没有任何一个出现在这个rule string里面。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

三大爷给的思路是,先generate next level, 然后再判断有没有。
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-29 10:36:35 | 显示全部楼层
就是brute force的做法吗?
回复 支持 反对

使用道具 举报

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

是的。有没有什么更好的方法?
回复 支持 反对

使用道具 举报

梦醒的我 发表于 2016-11-29 10:57:00 | 显示全部楼层
wilsonli 发表于 2016-11-29 10:37
是的。有没有什么更好的方法?

不知道呢,可能可以memoization一下?不过感觉bnb更注重把题做出来,对complexity要求不是很高
回复 支持 反对

使用道具 举报

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的时候,父亲结点的可能值

然后给定最低层的叶子结点 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。以此类推。

DCD or CCD 之后 DC或者CC不再组合了吗?而是直接跳过去了???. 1point3acres.com/bbs

补充内容 (2016-11-28 22:32):
忽略我的提问,我懂了。。。。。。
回复 支持 反对

使用道具 举报

gy21 发表于 2016-11-29 14:40:06 | 显示全部楼层
wilsonli 发表于 2016-11-28 22:32
这是一个一层一层generate的过程。最下面一层是input:ABCD。那么倒数第二层就是CAB,或者DAB。那么再上 ...
-google 1point3acres
这个表输入的时候是个二维数组吗?自己要遍历坐标去得到相应的字符?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 | 显示全部楼层
哈  题是啥呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 12:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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