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

handsomecool 发表于 2015-7-9 12:16
呃。。。你是昨天电面的呀，一般要一周左右吧，应该没问题的！

是吗？我一直感觉听大家的经历好像是第二天就会有消息呢

chenyy0527 发表于 2015-7-9 13:29
是吗？我一直感觉听大家的经历好像是第二天就会有消息呢

反正我是五天。。

handsomecool 发表于 2015-7-9 13:32
反正我是五天。。

是吗？那你后来是什么情况类？

stellari 发表于 2015-7-8 12:00
我想楼上说的Two passes可能是指：第一遍先得到所有的元素的和S；第二遍过的时候，如果某个元素A的左边的 ...

        int[] t = new int[]{3,-1,-1,5,7,-5,-1,-2,2};
切分点是第一个5.
两边和是1

chenyy0527 发表于 2015-7-8 12:28
哦，可以的！
我的方法也是类似。就是对于A[0]检测所有两边的和（当然左边没东西），然后不等的话，检测 ...

你这个是O(n^2)的解法把.

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

readman 发表于 2015-7-9 22:36
int[] t = new int[]{3,-1,-1,5,7,-5,-1,-2,2};
切分点是第一个5.
两边和是1

请问阁下的意思是？

这个例子的总和S = 3 - 1 -1 + 5 ... + 2 = 7.
当处理到t[3]的时候，因为当前的累积和S[0..2] == 1 == (S - t[3]) / 2。因此返回下标3。

如果你认为这个算法有问题，请明确指出。

stellari 发表于 2015-7-10 00:56
请问阁下的意思是？

这个例子的总和S = 3 - 1 -1 + 5 ... + 2 = 7.

- - 没, 我没看别人的帖子..我就贴上面的代码 然后post code

请问第二题interviewer想要什么答案

chenyy0527 发表于 2015-7-9 16:58
是吗？那你后来是什么情况类？

过是过了，没刷题不敢去onsite ╮(╯_╰)╭