狗家新鮮店面

新人帖，大家請見諒：
小弟今天早上剛結束狗家的電面，上來分享一下今天面的題目，希望能幫助到最近要面谷歌的大佬們
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 i

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

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

?
def preprocess():

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

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

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

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

1. public static void main(String[] args){
   
2.         int[] nums = {7,5,7,7};
   
3.         MoreThanHalf m = new MoreThanHalf(nums);
   
4.         System.out.println(m.isMoreThanHalf(0, 3, 6));
   
5.         System.out.println(m.isMoreThanHalf(1, 3, 7));
   
6.         System.out.println(m.isMoreThanHalf(2, 5, 7));
   
7.         System.out.println(m.isMoreThanHalf(4, 10, 4));
   
8.     }
   
9. 
   
10.     static class MoreThanHalf{
    
11.         Map<Integer, List<Integer>> myMap;
    
12.         int numsLength;
    
13.         MoreThanHalf(int[] nums){
    
14.             numsLength = nums.length;
    
15.             myMap = new HashMap<>();
    
16.             for(int i=0; i<numsLength; i++){
    
17.                 if(!myMap.containsKey(nums[i]))
    
18.                     myMap.put(nums[i], new ArrayList<>());
    
19.                 myMap.get(nums[i]).add(i);
    
20.             }
    
21.         }
    
22. 
    
23.         boolean isMoreThanHalf(int start, int end, int log){
    
24.             if(start < 0 || end >= numsLength || !myMap.containsKey(log))
    
25.                 return false;
    
26.             int length = end - start + 1;
    
27.             int low = binarySearch(start, myMap.get(log), true);
    
28.             int upper = binarySearch(end, myMap.get(log), false);
    
29.             return (upper - low + 1) * 2 > length;
    
30.         }
    
31. 
    
32.         private int binarySearch(int target, List<Integer> nums, boolean findLowerBound){
    
33.             int low = 0, high = nums.size() - 1;
    
34.             while(low + 1 < high){
    
35.                 int mid = low + ((high - low) >> 1);
    
36.                 if(nums.get(mid) > target)
    
37.                     high = mid;
    
38.                 else if(nums.get(mid) < target)
    
39.                     low = mid;
    
40.                 else
    
41.                     return nums.get(mid);
    
42.             }
    
43.             if(findLowerBound){
    
44.                 if(nums.get(low) >= target)
    
45.                     return nums.get(low);
    
46.                 return nums.get(high);
    
47.             }
    
48. 
    
49.             // find upperbound
    
50.             if(nums.get(high) <= target)
    
51.                 return nums.get(high);
    
52.             return nums.get(low);
    
53. 
    
54.         }
    
55.     }

复制代码

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

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

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

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

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

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

byfwh 发表于 2018/10/30 03:16:46
我想是不是可以简历一个HashMap数组如arr
然后每次arr[end].get(num) - arr[start - 1].get(num)
但是这样的空间复杂度会不会很高？

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

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

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

hlckl123456 发表于 2018-10-30 14:53
log里的数不是随机的嘛，binary search的原理是什么

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

lf963 发表于 2018-10-31 01:22
原來是隨機的!?  那我錯題目了

我誤解題目的意思了