Google电面面经 估计一轮游2016

直接上题

给一个sorted int array 定义popular item的frequency/occurerence 大于N/4
求item 值最小的frequency.

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

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

ex 两个index减一下得出frequency，应该是个O(lgN)的解法。
基本走远了。。。但还是祈祷给我个机会。

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

大致写了一下，不知道有没有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. }

复制代码

2分左右逼近...

pattern是啥?

ykwwind 发表于 2016-3-26 03:43
2分左右逼近...

pattern是啥?

1 1 2 2 2 2 2 3 4
分成
1  1 2 2 2     
2 2 3 5
他就让我找 也没说是啥

sorted int array 一定是从1开始的连续整数么？

N/4才算popular item, 那不是最多只有四个？
分成四段 只有每段的头尾才是candidate 然后从最小段开始check哪个有N/4 freq。。。？

跪拜楼上 原来是这样思考。。 跪拜。。

感觉这题和leetcode上的major element是一个解法的

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

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

slashGu 发表于 2016-3-28 08:50
要大于N/4才行，所以最多应该是3个。
另外，我觉得应该是用建一个BST，每个节点记录出现的次数，然后从 ...

从小到大找第一个popular num应该是O(n)时间吧

slashGu 发表于 2016-3-28 08:50
要大于N/4才行，所以最多应该是3个。
另外，我觉得应该是用建一个BST，每个节点记录出现的次数，然后从 ...

建bst要O(N)   面试官要求至少是O(lgN)的算法