热乎的Google MTV onsite面经

mwsak47 发表于 2016-4-5 02:27
谢谢。第二轮第二题是要划分从1到N的N个数，所以是没有重复的，所以其实应该是leetcode 78。找到和是总和 ...

感谢楼主.

对于第二轮第二题还是不太懂,S1于S2的并集是不是需要包括S里面所有元素?如果S是[1,2,3,4], 那[1,2]和[3], [1,3]和[4]算是valid的分法吗?还是说必须是[2,3]和[1,4]这样才算?

第四轮第一题,不让用除法还要求O(n),这个...怎么搞?

GUIXIANG 发表于 2016-4-5 12:36
感谢楼主.

对于第二轮第二题还是不太懂,S1于S2的并集是不是需要包括S里面所有元素?如果S是[1,2,3,4],  ...

第四轮第一题：

1. def solve(A):
   
2.         # return B for B[i] is A[0] * ... * A[n-1] / A[i]
   
3.         B = [1 for i in xrange(len(A))]
   
4.         prev, post, l = 1, 1, len(A)
   
5.         for i in xrange(l):
   
6.                 B[i] *= prev
   
7.                 B[l - 1 - i] *= post
   
8.                 prev *= A[i]
   
9.                 post *= A[l - 1 - i]
   
10.         return B

复制代码

zatarratw 发表于 2016-4-5 10:46
比如說，這個是n = 7的dp table，因為要partition成兩組一樣和的set，所以只要算到summation(n)的一半就好 ...

嗯，这个思路屌。我面的时候三哥也迟到了15分钟，写这个题的时候只有10分钟了，我也只想到了最简单的遍历所有subset的方法。dp确实好很多。

GUIXIANG 发表于 2016-4-5 12:36
感谢楼主.

对于第二轮第二题还是不太懂,S1于S2的并集是不是需要包括S里面所有元素?如果S是[1,2,3,4],  ...

需要包括S里的所有元素，如果S是[1,2,3,4], 那[1,2]和[3], [1,3]和[4]不是合法的划分；[2,3]和[1,4]才是。

第四轮第一题参见你楼下，他的解法是对的。

mwsak47 发表于 2016-4-5 13:55
嗯，这个思路屌。我面的时候三哥也迟到了15分钟，写这个题的时候只有10分钟了，我也只想到了最简单的遍历 ...

誒，這個人好故意喔，都遲到個15分鐘是怎樣

zatarratw 发表于 2016-4-5 23:17
誒，這個人好故意喔，都遲到個15分鐘是怎樣

哈哈，可能是故意的。不过除了迟到，感觉这三哥人还可以。只希望不会写报告时不会故意坑我。

GUIXIANG 发表于 2016-4-5 12:36
感谢楼主.

对于第二轮第二题还是不太懂,S1于S2的并集是不是需要包括S里面所有元素?如果S是[1,2,3,4],  ...

第四轮第一题
https://leetcode.com/problems/product-of-array-except-self/

难道现在google都是一轮2题?

yshanstar 发表于 2016-4-13 00:41
难道现在google都是一轮2题?

not really. Depends on how you perform

zatarratw 发表于 2016-4-5 10:46
比如說，這個是n = 7的dp table，因為要partition成兩組一樣和的set，所以只要算到summation(n)的一半就好 ...

又被前輩驚艷到了 XD

想請教第四輪第二題，前輩有什麽想法嗎？我覺的好像衹要先對所有points以x軸進行排序，然後就取中間兩個點就好了。因爲題主有説不用考慮共綫問題。。我好像考慮的太過簡單了