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

新鲜Google面经来啦！

电面， 三个问题：
1. array， 找一个point，两边总和相等， 很简单，要注意负数情况

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

个领域，还是有卡住的地方，如果拿分的话算30-40%吧

面试官人挺好的

chenyy0527 发表于 2015-7-8 07:16
Two passes 是什么？
我是检测第一个element，然后遍历剩下的，每次对比一加一减就可以。都是O（n)

哦哦，原来是给test cases看输出结果啊，那还是看你对于代码的理解。谢谢楼主

package Leetcode;/**
* Created by gaoyike on 7/9/15.
*/

import java.util.*;

/**
* 1. array， 找一个point，两边总和相等， 很简单，要注意负数情况

*/
public class PointinMiddle {
    public int find (int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int suml = 0; // sum of left side
        int sumr = 0; // sun of right side
        while (l <= r) {
            if (l == r && suml == sumr) // if it is the result
                return l;
            else if (suml > sumr){ // if left side is larger
                if (nums[r] > 0) { // if the next element of right is positive
                    sumr += nums[r]; // pick right next element
                    r--;
                }
                else if (nums[l] < 0){ // if the next element of left is negative
                    suml += nums[l]; // pick left next element
                    l++;
                }
                else { // have no f***ing greedy choice in this step, just move on
                    sumr += nums[r];
                    suml += nums[l];
                    r--;
                    l++;
                }
            }
            else{
                if (nums[l]>0) {
                    suml += nums[l];
                    l++;
                }else if (nums[r] < 0){
                    sumr += nums[r];
                    r--;
                }
                else {
                    sumr += nums[r];
                    suml += nums[l];
                    r--;
                    l++;
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] t = new int[]{1,1,1,1,100,4,5,-5};
        System.out.println(new PointinMiddle().find(t));
    }
}

求帮测哈
贪婪思想, 左边比右边大, 如果左边下一个是负数, 选它, 如果右边下一个是正数, 选它, 不然真的没法选了, 大家各进一步把

补充内容 (2015-7-10 00:04):
返回的是index, 顺便求短code

写了下不知道有木有bug，欢迎指正。

1. def findHalf(A):
   
2.         if A == None or len(A) == 0:
   
3.                 return -1
   
4.                
   
5.         for i in range(1, len(A)):
   
6.                 A[i] += A[i - 1]
   
7. 
   
8.         for i in range(len(A) - 1, 0, -1):
   
9.                 if A[i - 1] == A[-1] - A[i]:
   
10.                         return i
    
11. 
    
12.         return -1

复制代码

楼主 第二题感觉是使用rsync。

谢谢楼主，第一题o(n)解法two passes可以吗？

还有就是multi-thread那个是给你一段代码，然后让你理解程序要做什么？

dmsehuang 发表于 2015-7-8 07:09
谢谢楼主，第一题o(n)解法two passes可以吗？

Two passes 是什么？
我是检测第一个element，然后遍历剩下的，每次对比一加一减就可以。都是O（n)

后面那题要我理解程序是问我test case ，看会出现哪几种情况，会输出什么东西

主要是我对平行运算完全不熟所以。。。

不知道他们对于这种只能写代码的怎么评定

adiggo 发表于 2015-7-8 07:08
楼主 第二题感觉是使用rsync。

T.T 那是哪个领域的知识？我该去哪里补类？

adiggo 发表于 2015-7-8 07:08
楼主 第二题感觉是使用rsync。

T.T 那是哪个领域的知识？我该去哪里补类？

chenyy0527 发表于 2015-7-8 07:17
T.T 那是哪个领域的知识？我该去哪里补类？

rsync 是一个unix command， 很多backup是基于它的。他使用了delta-transfer algorithm， 因为两个file 差别很少， 所以使用它比较合适。

第一题two pointers最简单吧，前后逐渐往中心靠近，两边各一个sum, 每次哪边小就哪边前进一位，直到两边见面。

第二个问题 主要思想 应该是 对文件 partition（partition的 办法可以有 很多种） 分成多个fragment
因为 改动较小 所有 大部分 fragment 就没有改变 然后 处理 改动的 部分就好了