热乎的Google MTV onsite面经

那个数学题你是肿么证明的？ 可以给他举例说最坏情况吗？ 还说说要严格的数学证明？

夜辉冥 发表于 2016-4-1 13:41
那个数学题你是肿么证明的？ 可以给他举例说最坏情况吗？ 还说说要严格的数学证明？

反证法。设两个点为（x1,y1）和（x2,y2）。只有x1和x2奇偶性相同且y1和y2奇偶性想同时，这两点连线的中点才会on grid。所以点一共有（奇，奇）（奇，偶）（偶，奇）（偶，偶）四种情况。而一共有五个点。所以必然会有两个点的x和y的奇偶性都相同，这样必有连线中点on grid。

感谢楼主分享,祝楼主早日拿到offer. 弱问第二轮第二题,S1和S2里的元素是必须包括1到N的所有数吗?如果不是,类似leetcode 90题,是不是要先找出所有的subset, 然后在所有的subset里找sum相等的?还有第四轮第一题,为什么要用到除法?遍历数组,元素相乘,碰到index是i就跳过不可以了吗?

和Amazon HR赶紧约一个Offer Call，就明说你有Pending Onsite，一般延长两周没问题的。

partition sets那題，應該要用DP解，把問題簡化之後，會變成0/1 knapsack problem

GUIXIANG 发表于 2016-4-4 23:30
感谢楼主分享,祝楼主早日拿到offer. 弱问第二轮第二题,S1和S2里的元素是必须包括1到N的所有数吗?如果不是, ...

谢谢。第二轮第二题是要划分从1到N的N个数，所以是没有重复的，所以其实应该是leetcode 78。找到和是总和一半的子集数再除以2就行了。第四轮第一题是要在O（n）的时间内求所有的f（i）。

yucheyang2 发表于 2016-4-4 23:35
和Amazon HR赶紧约一个Offer Call，就明说你有Pending Onsite，一般延长两周没问题的。

OK，多谢。Amazon效率挺慢的，约到了今天下午，不知道还来不来得及。

zatarratw 发表于 2016-4-5 00:13
partition sets那題，應該要用DP解，把問題簡化之後，會變成0/1 knapsack problem

不明觉厉啊

mwsak47 发表于 2016-4-5 02:33
不明觉厉啊

就是0/1背包問題。你寫個dp的table，其中一軸是n的數字，另外一軸是sum(1 to n) / 2，cell value是count，用手寫一下從1 - 5 or 7左右，應該就會很清楚了。我當初就是卡在再給我五分鐘就可以把這個dp table寫出來，然後這題就可以解出來，但是三哥給我遲到15min....

比如說，這個是n = 7的dp table，因為要partition成兩組一樣和的set，所以只要算到summation(n)的一半就好了。然後因為兩兩一組，所以最後的值要除以2。