一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2902|回复: 18
收起左侧

Google Onsite MTV

[复制链接] |试试Instant~ |关注本帖
kingfu 发表于 2015-11-14 13:02:39 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 博士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
一共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). 1point3acres.com/bbs
. 1point 3acres 璁哄潧

第二轮,东欧口音极重的白人小哥,比前面那位随和多了,话也会多说两句。问我知不知道multithread如何work,我说基本不知道。。。然后他说没关系,假如现在有一个闹钟系统,你可以任意时间添加reminder,包括提醒时间和提醒内容需要调用的函数,你怎么设计这个操作?楼主没有system design基础,问了半天似懂非懂的就开始写addReminder,用一个hashmap存时间为key,value为list of events。然后main函数让时间无限循环,遇到time in events就调用所有的提醒内容函数。需要注意的是,1.及时删除已经提醒过的events,2. 调用提醒内容是时间在继续,调用完要回头补上调用期间可能会添加的event。最后一点是小哥提醒的,要check是否有多人同时在sync reminder,这我哪懂,就说加个函数不让多人同时sync,他说ok


第三轮,印度小哥,人很nice,很幸运!题目也设计的很专业,从最简单开始一点点加要求,一小题一小题的最后完成了一道大题。开始,给一段document,怎么word count?怎么按照词频sample单词?现在,要做一个random writer,如何process已有的document来随机生成一句话?反正就是一步一步的递进,每小问都以前面为基础,一点都不难。最后,就是类似存个bigram的count,sample 出一句话。


午饭不好吃。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


下午第四轮,一个瘦高的中东或者偏印度的小弟,口音是美国人,非常坑爹!这哥们是新手,还带了个shadower。楼主事后回想其实他的题目并不难,可是他的交流方式给当时紧张的我造成了不少困扰。上来就说”你简历上有提到做过nonlinear optimization的project,我不太了解nonlinear opt,你能给我讲讲吗?“ 我说行,你是要听我那个具体的project还是就generally 如何求解nonlinear opt?他说你就随便说说generally怎么解就行。说了几句就感觉他像例行公事一样,也不是在意我说了什么。然后出题。别人出题都会站起来在白板上把题目简单写一下,给个例子,这哥哥从进门开始屁股就没离开椅子。坐着说,给你一个长为n的string,如何找出最长的substring with k unique characters。一句话就没了。我跑到白板上把题写下来,还自己找了个例子google with k=2,问他应该是goog吧。结果这哥们说你觉得呢?顿时万匹草泥马奔腾,你tm不能好好说话吗?这基本就是接下来他的风格,问什么都是可能吧,你觉得呢。。。这还不是最烦的,他需要记录我的想法,就一直在噼里啪啦敲键盘,我边写边说,他还跟不上,经常打断我问我刚才说了什么或者写了什么。总之就是猴子派来坑我的,非但一点忙不帮,还尽是捣乱。。。。。。。。讲真他这题估计很多人做过原题的,可惜楼主没见过,再加上紧张和被他搅得心情烦躁,思路特别乱。总之是没能给出最优解。这期间shadower就说了一句,要不你从k=2开始想想,然后再没说过一句话。这轮目测跪残了。


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

. visit 1point3acres.com for more.
hr说下周送hiring committee,我觉得很悬。发个面经,攒点人品!

评分

1

查看全部评分

本帖被以下淘专辑推荐:

ChloeF 发表于 2015-11-15 03:32:14 | 显示全部楼层
感觉reminder这题考的是 intervals
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-11-15 17:08:57 | 显示全部楼层
第一轮uniformly sample是从剩下的N-k里取出K个元素的意思吗?uniform sampling就只知道reservoir sampling
回复 支持 反对

使用道具 举报

 楼主| kingfu 发表于 2015-11-16 02:17:17 | 显示全部楼层
不用,每次从n-k里uniformly sample一个元素就行
回复 支持 反对

使用道具 举报

面假空虚 发表于 2015-11-17 13:40:52 | 显示全部楼层
第一轮uniformly sample那个,请问那K个数字是已知的嘛?如果是这样那我们是不是可以用hashset记下这k个数字,然后就在1到N先sample一下, 如果sample的值在set里,往左或者往右找最近的一个不在set里的数?
回复 支持 反对

使用道具 举报

 楼主| kingfu 发表于 2015-11-17 14:30:17 | 显示全部楼层
这不uniform啊,这样离set越近被sample概率越大
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-11-17 15:29:59 | 显示全部楼层
LZ那个sampling的题是怎么做的啊?我就想的到把K个elements和array尾部的k elements互换,然后在array前N-K elements随机抽取一个
回复 支持 反对

使用道具 举报

 楼主| kingfu 发表于 2015-11-18 02:35:45 | 显示全部楼层
这样可能也行吧,但是要修改原来的array。我当时先给了naive的算法是把n-k个数copy出来再uniform sample,他说空间复杂度要o(k),我就说那就只存每个区间的端点,比如存[(1,a1-1), (a1+1,a2-1), ..., (ak+1,N)],然后再sample
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-11-18 04:14:04 | 显示全部楼层
kingfu 发表于 2015-11-18 02:35
这样可能也行吧,但是要修改原来的array。我当时先给了naive的算法是把n-k个数copy出来再uniform sample, ...

这个方法好!这样的话等于就是weighted sampling?因为每个区间的长度不一样,所以时间复杂度应该是O(logK)吧
.1point3acres缃
补充内容 (2015-11-18 04:15):
今天约的电话面试完全被放鸽子,打电话写邮件都没人回。。。真是呵呵了,怎么都这么不professional...
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-11-18 13:47:15 | 显示全部楼层
第四题是我面google的原题。
回复 支持 反对

使用道具 举报

guoqinlong 发表于 2015-11-18 21:21:08 | 显示全部楼层
  1. import java.util.ArrayList;.1point3acres缃
  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>();.1point3acres缃
  9.         for (int i=0; i<nums.length; i++) {
  10.             if (nums[i] == false) {. From 1point 3acres bbs
  11.                 misses.add(i);
  12.             }
  13.         }
  14.     }. from: 1point3acres.com/bbs
  15. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  16.     public int getRandom(int max) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.     public static void main(String agrs[]) {
  28.         boolean[] nums = new boolean[5];
  29.         Arrays.fill(nums, true);
  30.         nums[3] = false;
  31.         Solution s = new Solution(nums);
  32.         int count[] = new int[nums.length];
  33.         for (int i=0; i< 30000; i++) {
  34.             count[s.getRandom(nums.length)] ++;
  35.         }
  36.         for (int i=0; i< nums.length; i++) {
  37.             System.out.println(i+"\t"+count[i]);
  38.         }        
  39.     }
  40. }
复制代码

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

使用道具 举报

宝贝忆彼岸 发表于 2015-11-26 18:55:41 | 显示全部楼层
lz有消息了吗?
回复 支持 反对

使用道具 举报

千骨娜娜 发表于 2015-11-27 01:12:22 | 显示全部楼层
第四题是用slide window + LRU思想解决吗?把现在windows里面的字符放在LRU的double linked list里面?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 23:25:08 | 显示全部楼层
guoqinlong 发表于 2015-11-18 21:21
写的第一题,感觉跟楼主的思路差不多~我是第一遍扫描把所有删除掉的数字的位置记录下来,接下来每次ran ...

把数据又放到另一个arraylist, 跟让写reservoir sampling 没什么区别啊?
回复 支持 反对

使用道具 举报

nothingtrouble 发表于 2015-12-1 23:34:24 | 显示全部楼层
有戏,先恭喜lz. bless直接过不用match
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-4 12:38:40 | 显示全部楼层
kingfu 发表于 2015-11-18 02:35
这样可能也行吧,但是要修改原来的array。我当时先给了naive的算法是把n-k个数copy出来再uniform sample, ...
. visit 1point3acres.com for more.
请问楼主是怎么存呢?List<Interval>, 那样sampling怎么写?
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-7-16 06:04:03 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

zxcnn 发表于 2016-7-21 06:19:39 | 显示全部楼层
恭喜楼主,请问recruiter在hc之前有没有告诉你onsite的情况?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表