Google 电面面经，一结束马上来发，求爆人品！

handsomecool 发表于 2015-7-8 09:08
第一题two pointers最简单吧，前后逐渐往中心靠近，两边各一个sum, 每次哪边小就哪边前进一位，直到两边见 ...

这种遇到负数情况就不行了吧…

two passes的解法我猜是

先遍历第一遍求出总和

第二遍计算当时的和，是总和的一半就返回那个point

wb7 发表于 2015-7-16 03:33
这种遇到负数情况就不行了吧…

two passes的解法我猜是

看我后面的回复

楼主的解法应该是先取得total,然后往左移一个的时候, total- array[当下的]和从新扫的之前的total进行比较

two passes的意思是, 先从左扫一遍记录在每个位置是的total, 再从右到左扫一遍, 记录每一个total, 然后如果在某个位置, 左边的和等于右边的就是分割点
虽然都是o(n),楼主的好处需要额外空间o(1), 第二种需要额外空间的o(2n).

two passes的好处是, 如果要求所有的分割点, 那用这种不错

第二题就是synchorize, 每次增加a时, b也增加, 这样就不用log file了

应该能过~~~~~~

gameboyying 发表于 2015-7-16 06:09
楼主的解法应该是先取得total,然后往左移一个的时候, total- array[当下的]和从新扫的之前的total进行比较
...

嗯！第一题的解析没错！

第二题是要求从A到B拷贝一个备份文件，没有log，要求的是文件二分法=。=

handsomecool 发表于 2015-7-10 15:17
I will come onsite six months later, see you then :)

啊，可以这样吗？随便延后多久都行吗？
不需要和hr商量？

wllw881231 发表于 2015-8-9 02:55
啊，可以这样吗？随便延后多久都行吗？
不需要和hr商量？

我是和hr商量啊，但我说啥她都同意了。。听说可以延期一年，至少半年我是亲测了没问题。

楼主能稍微讲讲第三题大概是个什么情况么？

muancy 发表于 2015-8-24 10:43
楼主能稍微讲讲第三题大概是个什么情况么？

他用Go写了一段会multi thread运行的程序，然后给我一些test case， 问我这些test case 有那些输出的可能性，因为多线程中有时候顺序前后不是固定的

handsomecool 发表于 2015-7-8 01:07
还有负数哦，那改一下还是可以吧，依旧two pointers，两边哪边挪动的判定方式改一下：

这回不记左右 ...

收你的启发，我觉得是不是还可以这样。
按照 你给的例子，-5 -3 -1 -3 -7 -2

先从左到右依次加一遍，得出 -5 -8 -9 -12 -19 -21
再反过来加一遍，得出 -21 -16 -13 -12 -9 -2

然后同时遍历这两个序列，当遍历到-12 的时候，发现他俩相等，那么所求的 Index 就是这个-12 所在的 Index。时间：O(3n) = O(n) 空间 O(2n) = O(n). 这种方法空间比你的大哈。