狗家挂经

wb7 发表于 2018-3-30 07:23
对的，我一开始说的exponential 最后被否决掉了，和面试官讨论的这个brutal force最后的时间复杂度就是这 ...

这个解法就是on的复杂度吧……就是遍历一遍而已啊

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

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

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

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

wb7 发表于 2018-3-30 07:17
是对的，但是要求时间复杂度 O(1), 一个个查只有O(n)。
楼主做了preprocess然后用所有可能的value当key ...

我觉得这题想O(1)无论如何都要做一个值到最短interval的映射。
问题会不会出在建立映射表的过程上？

randrand1 发表于 2018-4-5 02:25
同感觉假设T(s, t)

可不可以理解成每次递归都让下层递归中节点访问次数乘以常数2，所以c一定存在？
比如root.left通常的遍历中只会访问一次，但是在这个访问中变成2次，它的孩子访问也是进一步乘2。

第五题，similar的定义是只允许发生一次swap么？还是允许多次？

flyPacific111 发表于 2018-4-4 14:30
第5题是不是可以这样：对两棵树分别traverse, 让所有Node.left

edge case很多，譬如很多duplicate的节点会出现你上一层没有换下一层需要换的情况。我的想法大体也是这样，不过需要自底向上swap

blactangeri 发表于 2018-4-5 01:00
请问lz是在kirkland面的吗

我在Fremont office面的。。然后发现确实bar比加州的高，如果约面试最好去加州面吧。。

alanlxl 发表于 2018-4-6 10:16
第五题，similar的定义是只允许发生一次swap么？还是允许多次？

每一个节点都允许swap

wb7 发表于 2018-4-6 11:37
我在Fremont office面的。。然后发现确实bar比加州的高，如果约面试最好去加州面吧。。

你说的这个bar高是指面试题难还是难match上？好像如果题太简单也不容易过HC啊