Google电面面经 估计一轮游2016

hison7463 发表于 2016-3-28 08:42
感觉这题和leetcode上的major element是一个解法的

不太一样。。。这题要求的是popular element 的出现次数

切成4分，
头尾是candidates。一共有8个，
然後从小開始測試。
这满足要求么

dimi 发表于 2016-3-28 10:04
切成4分，
头尾是candidates。一共有8个，
然後从小開始測試。

要怎么测试呢？

Array时sort好了的，所以大于1/4 的元素只可能出现在1/4，1/2，3/4处，分别对这三处的数检测。检测方法就是binary search 找出出现的最左边的index，和最右边的index，index之差就是frequence。如果超过1/3 加入到结果里

请问楼主有结果了吗？面完几天后有结果呢？

bobzhang2004 发表于 2016-3-29 21:52
请问楼主有结果了吗？面完几天后有结果呢？

妥妥被拒啊

大致写了一下，不知道有没有cover不到的corner case：

1. class PopularItemInSortedArray {
   
2.         public int pupularItem(int[] nums) {
   
3.                 int seg = nums.length / 4;
   
4.                 for (int i = seg; i < nums.length; i += seg) {
   
5.                         int first = findFirst(nums[i], 0, i - 1, nums);
   
6.                         if (first == -1) first = i;
   
7.                         int last = findLast(nums[i], i + 1, nums.length - 1, nums);
   
8.                         if (last == -1) last = i;
   
9.                         if (last - first + 1 >= seg) {
   
10.                                 return nums[i];
    
11.                         }
    
12.                 }
    
13.                 return -1;
    
14.         }
    
15.        
    
16.         private int findFirst(int t, int s, int e, int[] nums) {
    
17.                 while (s <= e) {
    
18.                         int m = s + (e - s) / 2;
    
19.                         if (nums[m] == t && (nums[m - 1] != t || nums[m + 1] != t)) {
    
20.                                 return m;
    
21.                         } else if (nums[m] < t) {
    
22.                                 s = m + 1;
    
23.                         } else {
    
24.                                 e = m - 1;
    
25.                         }
    
26.                 }
    
27.                 return -1;
    
28.         }
    
29.        
    
30.         private int findLast(int t, int s, int e, int[] nums) {
    
31.                 while (s <= e) {
    
32.                         int m = s + (e - s) / 2;
    
33.                         if (nums[m] == t && (nums[m - 1] != t || nums[m + 1] != t)) {
    
34.                                 return m;
    
35.                         } else if (nums[m] > t) {
    
36.                                 e = m - 1;
    
37.                         } else {
    
38.                                 s = m + 1;
    
39.                         }
    
40.                 }
    
41.                 return -1;
    
42.         }
    
43.          
    
44.         public static void main(String[] args) {
    
45.                 PopularItemInSortedArray p = new PopularItemInSortedArray();
    
46.                 System.out.println(p.pupularItem(new int[]{1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6}));
    
47.         }
    
48. }

复制代码

感觉楼主没有问前提： 是否sorted？
嗯，确实是binary search比较快。

DaveLiu 发表于 2016-6-7 12:17
大致写了一下，不知道有没有cover不到的corner case：

19 和 32 行有bug

1. 
   
2.         public int popularItem(int[] nums) {
   
3.                 if(nums ==null || nums.length<4) {
   
4.                         return 0;
   
5.                 }
   
6.                 int seg = nums.length/4;
   
7.                 for(int i=seg; i<nums.length; i+=seg) {
   
8.                         int first = findFirst(nums[i], 0, i-1, nums);
   
9.                         if(first == -1)        first = i;
   
10.                         int last = findLast(nums[i], i+1, nums.length-1, nums);
    
11.                         if(last == -1) last = i;
    
12.                         if(last - first + 1 >= seg) {
    
13.                                 return nums[i];
    
14.                         }
    
15.                 }
    
16.                 return -1;
    
17.         }
    
18.        
    
19.         private int findFirst(int t, int s, int e, int[] nums) {
    
20.                 while(s<=e) {
    
21.                         int m = s + (e-s)/2;
    
22.                         if(nums[m] == t && (m==0 || nums[m-1]!=t || nums[m+1]!=t)) {
    
23.                                 return m;
    
24.                         } else if(nums[m]<t) {
    
25.                                 s = m + 1;
    
26.                         } else {
    
27.                                 e = m - 1;
    
28.                         }
    
29.                 }
    
30.                 return -1;
    
31.         }
    
32.        
    
33.         private int findLast(int t, int s, int e, int[] nums) {
    
34.                 while(s<=e) {
    
35.                         int m = s + (e-s)/2;
    
36.                         if(nums[m] == t && (nums[m-1]!=t || m+1==nums.length || nums[m+1]!=t)) {
    
37.                                 return m;
    
38.                         } else if(nums[m] > t) {
    
39.                                 e = m - 1;
    
40.                         } else {
    
41.                                 s = m + 1;
    
42.                         }
    
43.                 }
    
44.                 return -1;
    
45.         }

复制代码