11.18 Airbnb Onsite

最后一个面试，终于可以停止刷题去好好做点别的事情了 0 - 0 虽然是在SF面试，但是我面的职位在西雅图
第一轮技术面，又是遇到没准备的题 - = - 似乎面经有人提过一次，就是那个随机生成树的题。给一个满二叉树的所有叶子，比如 A B C D E F， 然后给一个map，记录了左右孩子分别给了的时候，父亲节

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

梦醒的我 发表于 2016-11-22 00:23
请问如何把AB->A|C变成chomsky normal form呢，不是很懂A->AB,C->AB怎么来的。。比如原来是AB的可以变成C ...

是倒过来的，A->AB, C->AB表示AB这个串可以规约为A或者C,所以dp循环就应该长这样
for 长度
    for 起点
        // 原算法，这里似乎不需要这重循环 for 中点
            for 每个产生式 P: X->YZ
                如果dp(起点到长度－1，Y)和dp(起点+1到长度，Z)
                    dp(起点到长度,X) = true

详细说一下题目：
给的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

并没看懂第一题的map

请问楼主， 第一题的具体规则是， 比如ABCD是输入， 那第一层是AB map到一个字符连上接下来的CD继续呢， 还是AB， BC， CD各Map一次， 拼在一起继续呢？ 多谢

感谢分享，关注下这道题的解法。。。

zyoppy008 发表于 2016-11-20 16:36
并没看懂第一题的map

详细的我放在回复里面了

小A要当码农 发表于 2016-11-21 01:14
请问楼主， 第一题的具体规则是， 比如ABCD是输入， 那第一层是AB map到一个字符连上接下来的CD继续呢， 还 ...

详细的我放在回复里面了

bearcat001 发表于 2016-11-21 05:34
详细的我放在回复里面了

好的 了解了。。 多谢～

dp. CYK algorithm
输入的map可以转换成生成式，比如左A右B对应AC，则有对应产生式A->AB, C->AB，接下来就是普通dp了，参见cyk算法

楼主只有一道coding题么？