Google Onsite 12/8/2015

1. a) 给了个board，每个entry有一个颜色，给定一个entry和一种颜色A，把所有和该entry颜色相同的connected board涂上颜色A。follow up: DFS 和 BFS有什么优缺点，时间空间复杂度
    b) 给很多学生

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

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

情况下，把array里的0都移到最后，leetcode原题
    b)  计算二叉树两个节点的最短距离。先找LCA，再分别求高度。

最后祝大家好运吧！

tigercode 发表于 2016-9-19 13:59
2，有点难度    2a是模拟手动除法，然后用set存余数么？看到循环则停

1 11 111 1111 11111 111111这样循环除一个数一定能得到有余数循环么？我在想余数会不会没有规律，比如前面一直是1， 1， 2,2， 3,4,5,2,3,4，然后突然就到0了这种

comicrudy 发表于 2016-2-13 12:49
第二轮好难，数学不好不行啊。。

补充内容 (2016-2-13 12:56):

对，大概是这样的，code太难写，来不及写就结束了。第一题实在回忆不起来方法了，但是他问了很多overflow的问题，应该比较triky的解法吧，没想出来

comicrudy 发表于 2016-2-13 12:49
第二轮好难，数学不好不行啊。。

补充内容 (2016-2-13 12:56):

大体思想应该是这样， 但有些特殊的case要处理，比如下面这个， A-C必须取
   A
  /  \
B   C
/ \
D E

lz, 第二轮可以给些例子吗？

谢谢

guixi107 发表于 2016-2-13 02:32
lz, 第二轮可以给些例子吗？

谢谢

你是说第二题吧。你去看一下图论里maching的概念应该就明白了。画图不大好画

第二轮好难，数学不好不行啊。。

补充内容 (2016-2-13 12:56):
recursion应该是max(W(左边) + (DP(右子树) + DP(左孩子的左右子树))，W(右边) + (DP(左子树) + DP(右孩子的左右子树))）这样吧？能问一下2-a)的思路么？

楼主我们同一天onsite啊

请问“给很多学生，纸笔，统计单词数”具体是什么呢？

"一个二叉树，每条edge有weight（想象成graph），matching代表了一组两两没有公共节点的edges。现在让找一个matching，满足两个条件，一是cover所有节点"这题是图上的最小set题？是个NP问题

bobzhang2004 发表于 2016-3-7 00:05
"一个二叉树，每条edge有weight（想象成graph），matching代表了一组两两没有公共节点的edges。现在让找一 ...

现在是树，把问题简化了，感觉像dp题

lz我想问下 二×树不是一定有perfect matching的吧。。 如果是不是要先判断能不能找到这样一个matching