Google Onsite MTV

第四题是我面google的原题。

1. import java.util.ArrayList;
   
2. import java.util.Arrays;
   
3. import java.util.Collections;
   
4. 
   
5. public class Solution {
   
6.     ArrayList<Integer> misses;
   
7.     public Solution(boolean[] nums) {
   
8.         misses = new ArrayList<Integer>();
   
9.         for (int i=0; i<nums.length; i++) {
   
10.             if (nums[i] == false) {
    
11.                 misses.add(i);
    
12.             }
    
13.         }
    
14.     }
    
15. 
    
16.     public int getRandom(int max) {
    
17.         int ranVal = (int) (Math.random() *  (max-misses.size()));
    
18.         int left = Collections.binarySearch(misses, ranVal);
    
19.         if (left < 0) {
    
20.             left = (left + 1) * (-1);
    
21.             ranVal += left;
    
22.         } else {
    
23.             ranVal += (left+1);
    
24.         }
    
25.         return ranVal;
    
26.     }
    
27. 
    
28.     public static void main(String agrs[]) {
    
29.         boolean[] nums = new boolean[5];
    
30.         Arrays.fill(nums, true);
    
31.         nums[3] = false;
    
32.         Solution s = new Solution(nums);
    
33.         int count[] = new int[nums.length];
    
34.         for (int i=0; i< 30000; i++) {
    
35.             count[s.getRandom(nums.length)] ++;
    
36.         }
    
37.         for (int i=0; i< nums.length; i++) {
    
38.             System.out.println(i+"\t"+count[i]);
    
39.         }        
    
40.     }
    
41. }

复制代码

写的第一题，感觉跟楼主的思路差不多~我是第一遍扫描把所有删除掉的数字的位置记录下来，接下来每次random[0, N-k), 然后二分搜索找到其中有多少个位置是被擦掉的，将这些位置加上即可。时间复杂度首先初始化的扫描是o(N),后来的每次随机是o(lgk)

lz有消息了吗？

第四题是用slide window + LRU思想解决吗？把现在windows里面的字符放在LRU的double linked list里面？

guoqinlong 发表于 2015-11-18 21:21
写的第一题，感觉跟楼主的思路差不多~我是第一遍扫描把所有删除掉的数字的位置记录下来，接下来每次ran ...

把数据又放到另一个arraylist, 跟让写reservoir sampling 没什么区别啊？

有戏,先恭喜lz. bless直接过不用match

kingfu 发表于 2015-11-18 02:35
这样可能也行吧，但是要修改原来的array。我当时先给了naive的算法是把n-k个数copy出来再uniform sample， ...

请问楼主是怎么存呢？List<Interval>, 那样sampling怎么写？

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

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

恭喜楼主，请问recruiter在hc之前有没有告诉你onsite的情况？