Google new grad onsite 面经

匿名者 发表于 2021-11-8 00:37
1.hashtable肯定是可以做的
2.brute force是先找所有的subset

请问楼主第二题那个coins subset，有什么优化的方法呢？

匿名者 发表于 2021-11-7 21:37
1.hashtable肯定是可以做的
2.brute force是先找所有的subset

2.时间复杂度应该是O(N!)吧

simonsayshi 发表于 2021-11-10 16:16
2.时间复杂度应该是O(N!)吧

不是啊，最坏的情况是所有的subset都是unique sum（2 ^ n)

匿名者 发表于 2021-11-7 21:37
1.hashtable肯定是可以做的
2.brute force是先找所有的subset

想问下第二题如果不是找所有subset的话 可以怎么优化呢

想问下第二题如果不是找所有subset的话 可以怎么优化呢

wfuymu 发表于 2021-11-18 19:27
想问下第二题如果不是找所有subset的话 可以怎么优化呢

用dp来做，维持一个hashset记录从0-i能构成的unique sum. 最坏的情况是n * 2 ^ n。但是一般应该不会这么差

楼主能不能再讲一下第5题follow up？ “followup是如果移除一个leaf他的parent变成leaf必须紧接着移除parent”
那这样就不是按层返回Leaf了吗

jhdyss 发表于 2022-1-30 10:48
楼主能不能再讲一下第5题follow up？ “followup是如果移除一个leaf他的parent变成leaf必须紧接着移除paren ...

不是很理解你的意思，如果在level n移除了一个节点，父节点变成leaf那么即使level n仍然有其他的leaf node也回去优先移除level n - 1的父节点。这怎么会是按level返回leaf呢