谷歌云柯克兰面经

iq136man 发表于 2019-2-11 07:31
感谢楼主分享，顺便沾沾楼主的喜气！！！还有，弱弱的问一下第一轮第三题，骰子的正反面？楼主意思是硬币吗 ...

对 sorry 硬币

zhangzitong001 发表于 2019-2-11 09:26
insertion吧.  因为很大概率你比较前面一个数字 就会发现你比他大 然后就继续下一个数字了

嗯 insertion sort 能做到O(n*k), k是每个数当前位置离它排好序位置的距离

ziwei1992 发表于 2019-2-11 07:54
第一轮第二题感觉heap复杂度会更好一些？另外dp那个可不可以麻烦你说下更详细的思路？感觉这个题没看懂题 ...

嗯 用heap能做到O(n*log(k)), k是每个数当前位置离它排好序位置的距离

xliu34 发表于 2019-2-11 09:26
新年恭喜上进！
Q3能否说个例子？  我照您题目，p1 = root, game over

假设你选某个节点 你的对手可以有三种对策：

选左子树的根节点 （这样左子树你就不能走了）
选右子树的根节点 （这样右子树你就不能走了）
选当前节点的父节点 （这样整棵树除去当前节点为根节点的子树你就不能走了）

从这三种对策里选最优的

ziwei1992 发表于 2019-2-11 07:51
之前看有人面狗考过这个
https://www.geeksforgeeks.org/nearly-sorted-algorithm/
用heap做，不知道楼 ...

嗯 就是这个

anson_627 发表于 2019-2-11 09:50
假设你选某个节点 你的对手可以有三种对策：

选左子树的根节点 （这样左子树你就不能走了）

多谢!
如果是4层complete BT, 假如Round1 我下layer1－1， 对手可以layer2－1，
Round2 我可以下任何未堵的路，比如 layer 2-2, layer 3-2, 但对手还可以占据我的子树的一半啊，所以我的空间会不断被切半，对手占据的空间却全是她的啊
好像我领导的风格啊 ：（

杨超越 发表于 2019-2-11 07:36
第一轮第二题是insert sort？
第三轮是需要算具体指还是数学方法估值？

第三轮感觉和dp关系不大吧，感觉是要找到一个节点作为二叉树的root，满足其所有的子树size的最大值为最小，那么第一个人占领了这个root，另一个人就只能占领一个子树。算法应该是递归的bottom up计算子树的size，然后再遍历一遍所有node，找到满足上面条件的那个root。时间复杂度O(N)，N是节点数量。

Tazdingo 发表于 2019-2-11 10:27
第三轮感觉和dp关系不大吧，感觉是要找到一个节点作为二叉树的root，满足其所有的子树size的最大值为最小 ...

哈哈哈我说错了 是第一轮的第三题哈哈哈 那个第三题就是找子树节点数目

mewx 发表于 2019-2-11 07:34
中国程序员一定要团结！无比赞同，希望各位好运不要像我一样一个中国人面试官都没遇到

me too. 题不难，但是黑泥是有技巧的，面的很不舒服。

杨超越 发表于 2019-2-11 10:28
哈哈哈我说错了 是第一轮的第三题哈哈哈 那个第三题就是找子树节点数目

第三题不是C(50, 100)/2^100吗。。。

补充内容 (2019-2-11 10:37):
抱歉 是A(50, 100)/2^100