G加面2轮，新鲜面经

javaMonsterr 发表于 2018-10-17 12:37
我打错，是logn平方，这题两个做法，第一个是楼下有人说的，看最左和最有深度差，然后recursion，第二种 ...

应该不是最左和最右的深度差吧，应该是左子树最左和右子树最左的深度差，光知道最右枝的深度，倘若不一样，并不能舍弃一半。

同问lz 第一题为什么不用离口那道valid parentheses 用stack 来做呢？ 是有什么不同或者限制条件吗？ 谢谢

hongtunbaobao 发表于 2018-10-17 13:12
他可以有 a->c c->d 这种组合吗？ 如果没有的话为什么不用stack直接pop?

可以有这种，所以不能stack

DylanZhang 发表于 2018-10-17 13:29
应该不是最左和最右的深度差吧，应该是左子树最左和右子树最左的深度差，光知道最右枝的深度，倘若不一样 ...

最左和最有的差，是用来判断是否是每行都被fill的binary tree。https://stackoverflow.com/questi ... omplete-binary-tree

问下楼主 第一轮第二问 recursion 是当做两种case嘛，第一个当(,然后dfs, backtrack之后没有结果的话 再把它当)看，优化的话就用map存下当前string的 true / false；
如果用dp的话是 奇数值就寸是false，偶数的话 就看看前一个字母配不配？ 然后是n3的运行时间？

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

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

shady42 发表于 2018-10-18 03:46
第二题我在onsite的时候遇到过，楼主的做法是对的。写一个helper function判断一个leaf存不存在(logn)。通 ...

有点羡慕你，我写的时候，面试官啥都不说，体验很差。。。还好最后是写出来了。。。

javaMonsterr 发表于 2018-10-17 16:16
有点羡慕你，我写的时候，面试官啥都不说，体验很差。。。还好最后是写出来了。。。

如果提醒的话是会扣分的听说。所以不一定是好事

楼主能具体讲一下第一题第二问recursion和dp的思路吗？谢谢