Google onsite 面经

Aprilyn 发表于 2016-2-10 12:36
第二轮第一题，就是，平面上给定一系列的点，可以定义为vector of pairs, 然后找出一条线垂直于x轴，能使 ...

感谢LZ，可是那个只用一个矩阵那个是怎么弄的？后面的点计算左边和上面的花个数，还是需要前面的点的左边和上面花个数，这个事先加起来的话，后面就不好弄了。

Iancss 发表于 2016-2-10 13:13
感谢LZ，可是那个只用一个矩阵那个是怎么弄的？后面的点计算左边和上面的花个数，还是需要前面的点的左边 ...

假设有四个点：
A B
C D 的值为：

l1+t1 l1+t2
l2+t1
那么D的值就是C+B-A，当然如果有花之类的再细节考虑。
当时只是说了思路，也不知对不对= =

Aprilyn 发表于 2016-2-10 13:21
假设有四个点：
A B
C D 的值为：

多谢多谢！这个和那个求整个矩阵的和 很像！LZ太厉害了！感谢！

一个含有interger 的matrix， 找出一个点使得到左上角的submatrix 和 到右下角的matrix的和相等

楼主这题是怎么做的？

duduhaha 发表于 2016-2-10 13:49
一个含有interger 的matrix， 找出一个点使得到左上角的submatrix 和 到右下角的matrix的和相等

楼主这 ...

应该就是https://leetcode.com/problems/range-sum-query-2d-immutable/这个的变形~

Aprilyn 发表于 2016-2-10 14:35
应该就是https://leetcode.com/problems/range-sum-query-2d-immutable/这个的变形~

楼主 还有一个疑问 求硬币组合数那道题，DP是怎么解的？
我这边只想到用数学方法解，就是处理有 重复数 的情况。

Aprilyn 发表于 2016-2-10 12:42
嗯呐，那个lz很赞，我也尝试问我hr了。hr说google每天这样被拒的人很多。。feedback他自己也没有，说他的 ...

我觉得很奇怪啊，hr怎么会没有feedback?不是应该feedback差可能就直接拒了，好的话进hc么？怎么也得有feedback啊？要说没收全也能理解，但没有太奇怪了。lz应该去问问。

补充内容 (2016-2-10 17:07):
而且lz面得这么好，即使有一个feedback差一点应该也有机会啊。

Iancss 发表于 2016-2-10 01:57
楼主 还有一个疑问 求硬币组合数那道题，DP是怎么解的？
我这边只想到用数学方法解，就是处理有 重复数  ...

数学方法怎么解？ 我也没想到dp的方法，求lz讲一下

Iancss 发表于 2016-2-10 14:57
楼主 还有一个疑问 求硬币组合数那道题，DP是怎么解的？
我这边只想到用数学方法解，就是处理有 重复数  ...

囧，本来都在打字的，发现自己原来的想法不是那么对，面试官还说没更好的解了。。突然坦然了，估计面试官回去思考了下，觉得我说的不对。。

我当时dp的思路是顺着dfs的来的，把硬币sort一遍，然后当前点记录的是当前硬币必须被取的个数，其实就是前面所有的和。但是我忽略了这种方法可能带来的重复问题，可以用set来解决，这样就完全是dfs方法了。

忽略上面的，= =
好一点的方法是，把所有硬币都加起来，得出总和，然后从1-sum，所有可能都分别dp看这个点是否能被取到。



补充内容 (2016-2-11 02:57):
不过这个dp查某点是否能取到，因为有硬币个数限制，好像也得维护其他的来判断某种硬币是否能解。空间消耗略大。
所以我暂时也没想到一个好的最优解

comicrudy 发表于 2016-2-10 17:04
我觉得很奇怪啊，hr怎么会没有feedback?不是应该feedback差可能就直接拒了，好的话进hc么？怎么也得有fee ...

好像只是自我感觉良好。。现在发现我自己有个地方不太对，面试官却说好，略囧