Google Onsite MTV

一共5轮，4个technical+1个research

第一轮，亚裔小哥，话特别少。说先来个warmup question，不用写code。如果给你所有google search history，和一个新的input string，需要判断有没有被search过，你要用什么数据结构？如果有多个machine，怎么利用？如果有一个query总被search，怎么加速？楼主从hashmap开始，到prefix tree，再到先pre compute每个节点下面top 10，反正也不知道他到底想问什么，可能最后也没给出他最想要的结果。。。开始coding question。给一个数组是从1到N，就是sort好的1到N个整数，其中随机擦掉了k个数，如何uniformly sample剩下N-k个整数。不能无限次sample，空间复杂度O(k)


第二轮，东欧口音极重的白人小哥，比前面那位随和多了，话也会多说两句。问我知不知道multithread如何work，我说基本不知道。。。然后他说没关系，假如现在有一个闹钟系统，你可以任意时间添加reminder，包括提醒时间和提醒内容需要调用的函数，你怎么设计这个操作？楼主没有system

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

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

加上紧张和被他搅得心情烦躁，思路特别乱。总之是没能给出最优解。这期间shadower就说了一句，要不你从k=2开始想想，然后再没说过一句话。这轮目测跪残了。


第五轮，一个3-40岁的白人女，真的是来聊research的！楼主以前听说hr都会安排一轮聊research，但大多最后还是technical，所以没当回事。。。结果，就是一顿扯，反正research天天做，也不怕没得聊。白人女很健谈，懂一些但也不全懂。到最后就是介绍她在google的工作。估计这轮无功无过吧。


hr说下周送hiring committee，我觉得很悬。发个面经，攒点人品！

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)

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

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

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

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

感觉reminder这题考的是 intervals

第一轮uniformly sample是从剩下的N-k里取出K个元素的意思吗？uniform sampling就只知道reservoir sampling

不用，每次从n-k里uniformly sample一个元素就行

第一轮uniformly sample那个，请问那K个数字是已知的嘛？如果是这样那我们是不是可以用hashset记下这k个数字，然后就在1到N先sample一下， 如果sample的值在set里，往左或者往右找最近的一个不在set里的数？

这不uniform啊，这样离set越近被sample概率越大

LZ那个sampling的题是怎么做的啊？我就想的到把K个elements和array尾部的k elements互换，然后在array前N-K elements随机抽取一个

这样可能也行吧，但是要修改原来的array。我当时先给了naive的算法是把n-k个数copy出来再uniform sample，他说空间复杂度要o(k)，我就说那就只存每个区间的端点，比如存[(1,a1-1), (a1+1,a2-1), ..., (ak+1,N)]，然后再sample

楼主PHD?