Google onsite 面经

1. there are m piles of coins, each pile is consisted of coins with different values. you are allowed to take n coins home. However, you can only take coins from the top of each pile. What's the maximum value you can obtain.
2. output all same sub-tree pairs.

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

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

5. find longest consecutive path in tree, not necessary binary tree
6. given a list, the query will be a range, return the maximum number within this range, what if there are 1000 queries per second.
7. detect cycle in a graph.

lots of follow up questions. They do care about space complexity.

求大米，求祝福！！攒人品！！

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

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

edcent 发表于 2016-5-6 12:55
第二题subtree pairs楼主怎么做的？

后序遍历树， 这个过程跟踪每个结点的后序 serialized string， string相同说明子树相同

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

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

For #1, sort each pile of coin first ?

感谢楼主分享面经，请问一下5. find longest consecutive path in tree, not necessary binary tree，这一题，consecutive path一定可以是从根节点到子节点吗？ 还是说也可以从子节点到根节点再到子节点（就是先上后下）。

题目都挺常规的，祝LZ早日拿到offer！

能请问一下第一题怎么做吗

Lz能讲一下第一题怎么做的吗？

第一个应该是最大堆吧，priority_queue<pair<coins_val, pair<piles_index, index_inPiles>>，直到res size == n,或者queue空为止。

mingzhou1987 发表于 2016-5-6 12:12
第一个应该是最大堆吧，priority_queue

应该不是， 比如一个很大的pile， 最后有个很大的值（大于其余的和），前面的都很小， 那么按一般的最大堆很可能取不到这个值

CrossTheWall 发表于 2016-5-6 12:34
应该不是， 比如一个很大的pile， 最后有个很大的值（大于其余的和），前面的都很小， 那么按一般的最大 ...

同意。 我的想法是backtracking。

第二题subtree pairs楼主怎么做的？