一亩三分地论坛

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

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

Google onsite MTV面经以及一些准备

[复制链接] |试试Instant~ |关注本帖
flashpacker 发表于 2016-11-2 02:46:12 | 显示全部楼层 |阅读模式

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

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

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

x
闲来无事,发个面经回馈大家,攒攒RP。上周五Google onsite MTV。

由于冬季面过实习,刚点开full time OA就收到了Onsite消息,毕竟dream company,认真准备了一个半月,lc完整两遍。于10.28 onsite

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 1st round: 10.45第一轮开始,10.00从酒店出发,有些堵车,提醒需要面试的朋友早点出发,看来google的员工上班时间比较晚。。10.30到达,ABC小哥兼第一轮面试官在入口check in处带我进入building.由于时间比较充裕,于茶水间交谈15分钟,10.45进入非常大的一个meeting room. 上来直接,let's see a problem: 给定一个screen,高度为H pixels,宽度为W pixels,给定string, 由很多word组成,中间由空格分开。需要将string print到screen里面。但是麻烦的地方是,还有一个variable叫做fontsize,在不同的fontsize下每个letter有不同的height和width(单位是pixel)。问,最大能够fit到screen中的fontsize是多少。

答:lz先double check了screen和string的条件,与面试官讨论了几种可能情况,最终提出用binary search加一个check function解答。小哥说sounds good,于是开始写代码。写完后小哥一直在check我的binary search,鄙人写bs使用lo <= hi作为终止,所以举了四个例子给小哥,小哥说make sense开始check第二个func。check function的corner case很多,这里lz开始没有考虑到极端情况,小哥提出后修改代码,拍照,交谈,结束。


2nd round: 紧接着进来一个白人大叔。他的macbook air的电池出了问题,先问了hashtable实现方法,于是直接开始出问题。给一个stock,这只股票在不同的timestamp下有不同的price,(800, 1), (700, 2), (900, 3), (400, 4)。 Looks like this. 需要实现几个方法:1.getMaxHistory, 2.getCurrentPrice, 3.Correction, 4. update。比如说刚才给出的例子是900最高,但是如果调用correction,将ts = 3的price改为600,那么最高的将变为800.
. 1point 3acres 璁哄潧
答:开始分析题目,key-value pair自然想到hashtable,问题是如何最快拿到最高价格,当然bf是遍历hashtable,于是鄙人说可以加多一个treeset存储price。但紧接鄙人发现treeset有些情况不能覆盖,举例子给了大叔,于是改为treeMap实现,key是price,value是price出现次数。大叔说sounds good. LZ: Let me write some code now. 写完交谈五分钟结束。

lunch interview: 做computer vision的phd,聊了不少research的topic,PS:午饭人真是多。。. 1point3acres.com/bbs

3rd round: 不知国际的亚裔小哥,口语不是很好,他有些紧张。鄙人莫名其妙的来了句,你放松点。。没有废话,直接来了题目:给一个输入stream,是一个key-value pair。key是一个token,value是timestamp. 比如说("foo", 1), ("foo2",2),("foo", 10),(foo3, 11). ts总是不小于之前的ts,要求输出一个stream,输出的前提是,在之前的10s中没有出现过相同token,否则并不输出。

答:鄙人先double check了一些case,这应该是类似于cache的问题,用hashtable可以简单实现。小哥提出了第一个follow up,如果输入的stream的token不相同的占大多数怎么办?给我举了一些例子,这里我个人觉得google的这种follow up还是不少的,但是尽量不要从distributed的角度去分析,而是改进自己的数据结构。lz提出可以建一个sliding window类似的东西,类似于garbage collector,把10s前的储存的信息自动删除。小哥说sounds good,不过楼主脑抽说并不想遍历hashtable,能否使用其他data structure以提升速度。小哥很疑惑,于是我说可能使用deque可以更明了,小哥说好像可行。于是提出了第二个follow up,如果冲突(10s 中出现了相同token),那么两个token都不能输出到output stream中。这是一个有latency的cache输出的问题,lz答曰可以将hashtable的value变成一个object,这个object可以有一个boolean的value,对于一个新的input,拿到后先不输出,10s latency后check后在输出。小哥反应很快,说like this idea,不得不说,google这些面试官他们的思维很好,沟通很流畅。之后聊了聊他做的什么,反正我是没听懂。。

4th round: 三姐姐,进来让我介绍一些我做的ml project,说了有点久,大姐说那我们做一个cache和garbage collector的问题,给一个key-value pair。。。我说,之前那轮我们讨论了类似的问题,咱们要不要换一个..?三姐说好的,于是问我会不会OOD,lz直接说了不太会。(PS楼主除了algo和data structure其他都不太懂。。)于是三姐来了一个类似于find increasing path的问题。给一个2D的grid,每个值代表高度,从左边第一列出发,每次只能向右边的三个方向移动,而且必须要increasing。寻找一条这样的路径。三姐一开始的描述非常奇怪。。

答:开始楼主写的BFS,三姐感觉有些奇怪,不过BFS确实是make sense的,需要一个boolean的visited数组,复杂度是N方。写到一半,楼主提出有些方块会重复check所以为了避免duplicates,需要有个visited数组。三姐说为什么要用BFS,lz分析了一下,然后说这题DFS+memorization也是可以做的,你想让我这么写么?三姐点头,于是开始写,说实话第四轮有点累了,写出来后三姐说make sense to her。由于最后一轮,我们交谈了很久,这轮大概有一个小时多,虽说是三姐,但是人还是挺好的。所以大家不要带有什么偏见对待,以诚相待,别人也不会为难你。之后三姐送我出了大门,然后see you.

总结:整个面试流程还是非常轻松地,心跳并没有加速过。。说实话这是lz的唯一一个onsite,对于找工作比较消极怠工吧。。一直懒得投,只是积极准备了g这一家,所有的赌注压在了上面。真心建议其他同学不要学习。。这样一点好处都没有。给自己留条后路还是好的。g家的面试官给人是很和蔼的感觉,但是我觉得思考的过程一定要描述清楚,让他人觉得你具备独立思考解决问题的能力。无论结果如何,这次经历对我是一个很好的锻炼。希望能有好消息吧。也祝大家找工作顺利,刷题刷不下去的时候,咬咬牙再坚持一下,逼一下自己,胜负就在这一个一个瞬间积累的。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
鏉ユ簮涓浜.涓夊垎鍦拌鍧.


补充内容 (2016-11-22 03:19):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
offer get

评分

5

查看全部评分

本帖被以下淘专辑推荐:

gaocan1992 发表于 2016-11-2 02:52:37 | 显示全部楼层
我也遇到了round3的紧张小哥,感觉他比我紧张多了搞得我像面试官一样

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-2 02:59:24 | 显示全部楼层
楼主面的题目都不是leetcode呀..看楼主回答的很不错啊!!!
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 03:15:54 | 显示全部楼层
gaocan1992 发表于 2016-11-2 02:52
我也遇到了round3的紧张小哥,感觉他比我紧张多了搞得我像面试官一样

这个小哥还是挺逗的。。不过刚进来确实。。哈哈。。
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 03:17:02 | 显示全部楼层
leixiang5 发表于 2016-11-2 02:59
楼主面的题目都不是leetcode呀..看楼主回答的很不错啊!!!

感觉他们家lc原题考的确实不多,回答的还凑合吧,因为只有一个面试,所以把经历发出来供大家查看。
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-11-2 03:18:43 | 显示全部楼层
flashpacker 发表于 2016-11-1 11:17
感觉他们家lc原题考的确实不多,回答的还凑合吧,因为只有一个面试,所以把经历发出来供大家查看。
. more info on 1point3acres.com
感觉很多题目是原题改一改然后包装一下。
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-11-2 04:07:41 | 显示全部楼层
楼主感觉很有希望啊。问题都不简单还答的这么好。

反观我。。。
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 04:42:04 | 显示全部楼层
gaocan1992 发表于 2016-11-2 03:18
感觉很多题目是原题改一改然后包装一下。

是的…感觉还是踏实的做lc是正路。
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 04:42:39 | 显示全部楼层
Henry要工作 发表于 2016-11-2 04:07
楼主感觉很有希望啊。问题都不简单还答的这么好。
. visit 1point3acres.com for more.
反观我。。。

别这么说…乐观点,lz是个过于乐观的人…咱们平衡一下。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-2 05:31:21 | 显示全部楼层
1st Round: Word screen fit. 这个题是假设给定了一个求char的height/width的API吗?极端情况就是当在某个font size下screen width连给定的strings中的某一个单词都不能容下吧。感觉细节就在于strings之间换行的时候可以不加空格吧。
  1. // assumed given API
  2. pair<int, int> geLetterSize(char c, int fs);. visit 1point3acres.com for more.

  3. // global const: screen width/height, max font size
  4. static const int screenW, screenH, maxFontSize;

  5. pair<int, int> getWordSize(string& w, int fs) {. 1point 3acres 璁哄潧
  6.   int width = 0, height = 0;
  7.   for (char c : w) {
  8.     width += geLetterSize(c, fs).first;
  9.     height = max(height, geLetterSize(c, fs).second);
  10.   }
  11.   return make_pair(width, height);
  12. }

  13. int getTotalLineHeight(vector<string>& ws, int fs) {
  14.   int curH = 0; // current line height
  15.   int curW = 0; // current line width.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.   int totalH = 0; // total line height
  17.   int i = 0; // current word index in strings
  18.   auto sz = getWordSize(ws[i], fs); // current word size.鐣欏璁哄潧-涓浜-涓夊垎鍦
  19.   int spaceW = geLetterSize(' ', fs).first; // space width.鏈枃鍘熷垱鑷1point3acres璁哄潧
  20.   while (i < ws.size()) {
  21.     // width to fit in current line
  22.     int wToFit = sz.first + (curW? spaceW : 0);
  23.     // fit in current line
  24.     if (curW + wToFit <= screenW) {
  25.       curW += wToFit; curH = max(curH, sz.second);
  26.       if (i < ws.size()) sz = getWordSize(ws[++i], fs);
  27.     }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.     // even a single word cannot fit
  29.     else if (!curW) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  30.       cout << "Cannot even fit a single word width on screen!\n";
  31.       return INT_MAX;
  32.     }
  33.     // start a new line
  34.     else {
  35.       totalH += curH; curW = 0; curH = 0;
  36.     }
  37.   }-google 1point3acres
  38.   // get height of last line. from: 1point3acres.com/bbs
  39.   if (curW) totalH += curH;
  40.   return totalH;
  41. }

  42. int maxFontSizeToFit(vector<string>& ws) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  43.   int minFS = 1, maxFS = maxFontSize;
  44.   while (minFS < maxFS) {
  45.     int mid = (minFS + maxFS + 1) / 2;
  46.     if (getTotalLineHeight(ws, mid) <= screenH) minFS = mid;
  47.     else maxFS = mid - 1;
  48.   }
  49.   return minFS;
  50. }
复制代码



补充内容 (2016-11-2 05:33):
Line 29 correction: "if (i < ws.size() - 1) sz = getWordSize(ws[++i], fs);"
回复 支持 反对

使用道具 举报

jolesiawu 发表于 2016-11-2 05:34:46 | 显示全部楼层
感觉楼主会被录 坐等好消息
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 05:46:05 | 显示全部楼层
zzgzzm 发表于 2016-11-2 05:31. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1st Round: Word screen fit. 这个题是假设给定了一个求char的height/width的API吗?极端情况就是当在某个f ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对的,有get character的height和width的API,我在描述中忘记说了,您的解法很正确。极端情况有两种,一个是非常细长的screen一个是非常瘦高的screen,希望我的描述不confusing。
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 05:46:41 | 显示全部楼层
jolesiawu 发表于 2016-11-2 05:34
感觉楼主会被录 坐等好消息
. from: 1point3acres.com/bbs
谢谢,共勉。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-2 06:08:10 | 显示全部楼层
2nd Round: Stock. LZ请问这个“getMaxHistory”是只用返回历史最高价格吗?“update”是指给定当前新的stock price吗?
我不熟悉terminology "TreeMap"。在C++我用一个sorted set of pair(time, price)和一个hashmap<time, set iterator>记录位置来实现的。若当前时间为N, 我的“Correction”和“update”都是O(log N), 其它的都是O(1).
  1. struct MyComp { // comparator of pair by second component. From 1point 3acres bbs
  2.   bool operator () (pair<int, double> x, pair<int, double> y) {
  3.     return x.second < y.second;
  4.   }
  5. };. Waral 鍗氬鏈夋洿澶氭枃绔,

  6. class StockServer {. 1point 3acres 璁哄潧
  7. private:
  8.   set<pair<int, double>, MyComp> _prices; // pair(time, price) sorted by price
  9.   unordered_map<int, set<pair<int, double>, MyComp>::iterator> _pos; // time -> position in _prices-google 1point3acres
  10.   int _curTime; // current time stamp

  11. public:
  12.   StockServer():_curTime(0){}

  13.   double getMaxHistory() { // O(1). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.     return _prices.empty() ? -1.0 : _prices.rbegin()->second;
  15.   }

  16.   double getCurrentPrice() { // O(1)
  17.     return _prices.empty() ? -1.0 : _pos[_curTime]->second;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.   }

  19.   void Correction(int time, double newPrice) { // O(log N)
  20.     if (time > _curTime) return;
  21.     if (_pos[time]->second != newPrice) {
  22.       _prices.erase(_pos[time]);
  23.       _pos[time] = _prices.emplace(time, newPrice).first;
  24.     }
  25.   }

  26.   void update(double newPrice) { // O(log N)
  27.     _pos[_curTime] = _prices.emplace(++_curTime, newPrice).first;
  28.   }-google 1point3acres
  29. };
复制代码
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 06:10:25 | 显示全部楼层
zzgzzm 发表于 2016-11-2 06:08
2nd Round: Stock. LZ请问这个“getMaxHistory”是只用返回历史最高价格吗?“update”是指给定当前新的sto ...

对的对的。。两个是logN剩下两个都是O1. PS lz不太懂CPP。。不过看起来没什么问题的
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-2 06:14:20 | 显示全部楼层
flashpacker 发表于 2016-11-2 05:46-google 1point3acres
对的,有get character的height和width的API,我在描述中忘记说了,您的解法很正确。极端情况有两种,一 ...

感谢解释!~
赞LZ的临场沉稳表现~~ 我感觉要是我的话若给我充足的时间最终是可以写清楚的,但在现场有限的时间下就不容易了。
感觉很多东西是明白,但coding实现起来若让面试官看见过程会比较messy,虽然最终结果还OK。LZ觉得G家是不是对fluency and clean coding要求特别高啊?
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 06:17:04 | 显示全部楼层
zzgzzm 发表于 2016-11-2 06:14 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感谢解释!~
赞LZ的临场沉稳表现~~ 我感觉要是我的话若给我充足的时间最终是可以写清楚的,但在现场 ...

怎么说呢,鄙人其实思想很naive..从小到大什么都无所谓。。也无所畏..主要是想着临场紧张没有什么卵用,调整一下心态,轻松应对就好了,祝您好运!
回复 支持 反对

使用道具 举报

 楼主| flashpacker 发表于 2016-11-2 06:18:43 | 显示全部楼层
zzgzzm 发表于 2016-11-2 06:14
感谢解释!~. 1point 3acres 璁哄潧
赞LZ的临场沉稳表现~~ 我感觉要是我的话若给我充足的时间最终是可以写清楚的,但在现场 ...
. 鍥磋鎴戜滑@1point 3 acres
我觉得他们看重的是你的分析过程,而不是题做出来与否,思路并不是一蹴而就,但是能够快速达到最优还是重要的。一点见解而已。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-2 09:20:17 | 显示全部楼层
3rd Round: 这个题和地里的一个执行task with cooldown time求总时间的面经题很像。如果这道题就相当于是fix cooldown time = 10sec,那么用deque的确可以解决问题了(因为每次遇到一个token时要遍历deque该token是否在最近10sec中出现过,deque max size不超过10为有界常数,时间还是O(1)),整体时间O(N),空间O(1),输出空间不算。若对于一般任意的cooldown time,我觉得得用hashmap + list了:list记录最近cooldown 的tokens,hashmap记录近cooldown 的tokens的最后时间及在list中的位置,这样可以O(1)在list中删除,整体时间O(N),空间O(min(N, cooldown))。
  1. typedef pair<string,int> TokenTs; // pair(token, timestamp)
  2. typedef vector<TokenTs> Stream;

  3. Stream output(Stream& stream, int cooldown = 10) {
  4.   Stream out; // output stream
  5.   list<string> prevTokens; // tokens in last cooldown sec ordered by time, max size = cooldown
  6.   // last timestamp and order in list for tokens in last cooldown sec, max size = cooldown  
  7.   unordered_map<string, pair<int,list<string>::iterator>> lastTs;
  8.   . Waral 鍗氬鏈夋洿澶氭枃绔,
  9.   for (auto& p:stream) {
  10.     int curTs = p.second; string curToken = p.first;
  11.     // remove all expired token records: older than curTs-cooldown
  12.     auto it = prevTokens.begin();
  13.     while (it != prevTokens.end() && lastTs[*it].first < curTs-cooldown) {
  14.       lastTs.erase(*it);   
  15.       it = prevTokens.erase(it); // it gets incremented after removal   
  16.     }
  17.     // add to output only if token not in last cooldown sec
  18.     if (!lastTs.count(curToken)) {
  19.       out.emplace_back(curToken, curTs);
  20.       prevTokens.push_back(curToken);
  21.       lastTs[curToken] = make_pair(curTs, --prevTokens.end());
  22.     }
  23.   }
  24.   return out;
  25. }
复制代码
回复 支持 反对

使用道具 举报

OPheadache_h 发表于 2016-11-2 09:38:02 | 显示全部楼层
看楼主描述感觉拿offer应该问题不大,分析问题的思路、心态都很赞!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 03:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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