转发: 狗家新鮮店面

Job Hunting Interview
, , , , ,
1

新人帖，大家請見諒：
小弟今天早上剛結束狗家的電面，上來分享一下今天面的題目，希望能幫助到最近要面谷歌的大佬們
1.
Given an array “log” with N entries (N in the order of billions) and M type of numbers in the array. Define a function isMoreThanHalf(startIdx, endIdx, logType). Determine if the “logType” appears more than half of the subarray starts from “startIdx” and ends in “endIdx”.
For example,
log = [6, 6, 6, 7, 3, 8]
isMoreThanHalf(0, 3, 6) -> True
isMoreThanHalf(1, 4, 6) -> False
isMoreThanHalf(2, 5, 7) -> False

Note: startIdx and the endIdx is the closed interval.
startIdx could be the same as endIdx.

You are now able to use a preprocess function one time. How would you define the function?
def preprocess():

  1. How would you utilize your preprocess function to improve 1. ?

第一題沒什麼難度，但第二題想問問各位大神對這題有什麼想法嗎??

2

Binary search可以用 因为index是递增的
比如[6,4,1,2,2,2,3,6]
1: 2
2: 3 4 5
3: 6
4: 1
6: 0 7
query (2, 4, 2)
2: [3 4 5]
binary search 找 2: 找到index 0
binary search 找 4: 找到index 1
len = 1 - 0 + 1 = 2
2 > 3 / 2 = 1
所以返回true

3

你考的python语言呀？怎么还有pre process

4

我想是不是可以简历一个HashMap数组如arr
然后每次arr[end].get(num) - arr[start - 1].get(num)
但是这样的空间复杂度会不会很高？

5

第一题是直接遍历一下就好了吗？

6

是不是可以建立对应每个log类型的数目的presum array

7

m * n
m log类型数目
n log总条数

8

[Java] 纯文本查看 复制代码public static void main(String[] args){
int[] nums = {7,5,7,7};
MoreThanHalf m = new MoreThanHalf(nums);
System.out.println(m.isMoreThanHalf(0, 3, 6));
System.out.println(m.isMoreThanHalf(1, 3, 7));
System.out.println(m.isMoreThanHalf(2, 5, 7));
System.out.println(m.isMoreThanHalf(4, 10, 4));
}

static class MoreThanHalf{
    Map<Integer, List<Integer>> myMap;
    int numsLength;
    MoreThanHalf(int[] nums){
        numsLength = nums.length;
        myMap = new HashMap<>();
        for(int i=0; i<numsLength; i++){
            if(!myMap.containsKey(nums[i]))
                myMap.put(nums[i], new ArrayList<>());
            myMap.get(nums[i]).add(i);
        }
    }

    boolean isMoreThanHalf(int start, int end, int log){
        if(start < 0 || end >= numsLength || !myMap.containsKey(log))
            return false;
        int length = end - start + 1;
        int low = binarySearch(start, myMap.get(log), true);
        int upper = binarySearch(end, myMap.get(log), false);
        return (upper - low + 1) * 2 > length;
    }

    private int binarySearch(int target, List<Integer> nums, boolean findLowerBound){
        int low = 0, high = nums.size() - 1;
        while(low + 1 < high){
            int mid = low + ((high - low) >> 1);
            if(nums.get(mid) > target)
                high = mid;
            else if(nums.get(mid) < target)
                low = mid;
            else
                return nums.get(mid);
        }
        if(findLowerBound){
            if(nums.get(low) >= target)
                return nums.get(low);
            return nums.get(high);
        }

        // find upperbound
        if(nums.get(high) <= target)
            return nums.get(high);
        return nums.get(low);

    }
}
9

log里的数不是随机的嘛，binary search的原理是什么

10

原來是隨機的!? 那我錯題目了

11

我誤解題目的意思了