【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 6229|回复: 28
收起左侧

Google onsite MTV面经以及一些准备

[复制链接] |试试Instant~
我的人缘0
flashpacker 发表于 2016-11-2 02:46:12 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩

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

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

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

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开始没有考虑到极端情况,小哥提出后修改代码,拍照,交谈,结束。

. visit 1point3acres for more.
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 3 acres
答:开始分析题目,key-value pair自然想到hashtable,问题是如何最快拿到最高价格,当然bf是遍历hashtable,于是鄙人说可以加多一个treeset存储price。但紧接鄙人发现treeset有些情况不能覆盖,举例子给了大叔,于是改为treeMap实现,key是price,value是price出现次数。大叔说sounds good. LZ: Let me write some code now. 写完交谈五分钟结束。. from: 1point3acres

lunch interview: 做computer vision的phd,聊了不少research的topic,PS:午饭人真是多。。
. 牛人云集,一亩三分地
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这些面试官他们的思维很好,沟通很流畅。之后聊了聊他做的什么,反正我是没听懂。。. 1point3acres

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大米 +92 收起 理由
wuashuai + 3 爱你!一定有offer
spwahaha + 3 感谢分享!
xchenan + 3 坚持的不错,再接再厉!
yiyizheliu + 3 感谢分享!
candy_shmily + 80

查看全部评分


上一篇:楼主又来分享Liveramp跪经
下一篇:Bloogberg Phone

本帖被以下淘专辑推荐:

我的人缘0
zzgzzm 发表于 2016-11-2 05:31:21 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
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);

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

  5. pair<int, int> getWordSize(string& w, int fs) {
  6.   int width = 0, height = 0;.本文原创自1point3acres论坛
  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
  20.   while (i < ws.size()) {
  21.     // width to fit in current line
  22.     int wToFit = sz.first + (curW? spaceW : 0);. from: 1point3acres
  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.     }
  28.     // even a single word cannot fit
  29.     else if (!curW) {-google 1point3acres
  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.   }. 1point3acres
  38.   // get height of last line
  39.   if (curW) totalH += curH;
  40.   return totalH;
  41. }. From 1point 3acres bbs

  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;. Waral 博客有更多文章,
  48.   }
  49.   return minFS;
  50. }
复制代码
. 一亩-三分-地,独家发布


补充内容 (2016-11-2 05:33):. From 1point 3acres bbs
Line 29 correction: "if (i < ws.size() - 1) sz = getWordSize(ws[++i], fs);"
回复

使用道具 举报

我的人缘0
gaocan1992 发表于 2016-11-2 02:52:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (102)
 
 
5% (6)  踩
我也遇到了round3的紧张小哥,感觉他比我紧张多了搞得我像面试官一样

评分

参与人数 1大米 +10 收起 理由
忆梦前尘 + 10 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

我的人缘0
leixiang5 发表于 2016-11-2 02:59:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  82% (196)
 
 
17% (41)  踩
楼主面的题目都不是leetcode呀..看楼主回答的很不错啊!!!
回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 03:15:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
gaocan1992 发表于 2016-11-2 02:52
我也遇到了round3的紧张小哥,感觉他比我紧张多了搞得我像面试官一样

这个小哥还是挺逗的。。不过刚进来确实。。哈哈。。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 03:17:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
leixiang5 发表于 2016-11-2 02:59
楼主面的题目都不是leetcode呀..看楼主回答的很不错啊!!!

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

使用道具 举报

我的人缘0
gaocan1992 发表于 2016-11-2 03:18:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  94% (102)
 
 
5% (6)  踩
flashpacker 发表于 2016-11-1 11:17
感觉他们家lc原题考的确实不多,回答的还凑合吧,因为只有一个面试,所以把经历发出来供大家查看。

感觉很多题目是原题改一改然后包装一下。
回复

使用道具 举报

我的人缘0
Henry要工作 发表于 2016-11-2 04:07:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  90% (10)
 
 
9% (1)  踩
楼主感觉很有希望啊。问题都不简单还答的这么好。 来源一亩.三分地论坛.
.1point3acres网
反观我。。。
回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 04:42:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
gaocan1992 发表于 2016-11-2 03:18
感觉很多题目是原题改一改然后包装一下。

是的…感觉还是踏实的做lc是正路。
回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 04:42:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
Henry要工作 发表于 2016-11-2 04:07
楼主感觉很有希望啊。问题都不简单还答的这么好。

反观我。。。

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

使用道具 举报

我的人缘0
jolesiawu 发表于 2016-11-2 05:34:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (6)
 
 
14% (1)  踩
感觉楼主会被录 坐等好消息

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 05:46:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
zzgzzm 发表于 2016-11-2 05:31
1st Round: Word screen fit. 这个题是假设给定了一个求char的height/width的API吗?极端情况就是当在某个f ...

对的,有get character的height和width的API,我在描述中忘记说了,您的解法很正确。极端情况有两种,一个是非常细长的screen一个是非常瘦高的screen,希望我的描述不confusing。
回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 05:46:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
jolesiawu 发表于 2016-11-2 05:34
感觉楼主会被录 坐等好消息

谢谢,共勉。
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-2 06:08:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
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).. visit 1point3acres for more.
  1. struct MyComp { // comparator of pair by second component
  2.   bool operator () (pair<int, double> x, pair<int, double> y) {
  3.     return x.second < y.second;
  4.   }
  5. };

  6. class StockServer {. 围观我们@1point 3 acres
  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
  10.   int _curTime; // current time stamp

  11. public:
  12.   StockServer():_curTime(0){}.留学论坛-一亩-三分地
  13. .本文原创自1point3acres论坛
  14.   double getMaxHistory() { // O(1)
  15.     return _prices.empty() ? -1.0 : _prices.rbegin()->second;. 牛人云集,一亩三分地
  16.   }

  17.   double getCurrentPrice() { // O(1)
  18.     return _prices.empty() ? -1.0 : _pos[_curTime]->second; 来源一亩.三分地论坛.
  19.   }

  20.   void Correction(int time, double newPrice) { // O(log N). 留学申请论坛-一亩三分地
  21.     if (time > _curTime) return;
  22.     if (_pos[time]->second != newPrice) {
  23.       _prices.erase(_pos[time]);
  24.       _pos[time] = _prices.emplace(time, newPrice).first;-google 1point3acres
  25.     }. 1point3acres
  26.   }.1point3acres网

  27.   void update(double newPrice) { // O(log N). visit 1point3acres for more.
  28.     _pos[_curTime] = _prices.emplace(++_curTime, newPrice).first;
  29.   }
  30. };
复制代码
回复

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 06:10:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
zzgzzm 发表于 2016-11-2 06:08
2nd Round: Stock. LZ请问这个“getMaxHistory”是只用返回历史最高价格吗?“update”是指给定当前新的sto ...

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

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-2 06:14:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
flashpacker 发表于 2016-11-2 05:46. 牛人云集,一亩三分地
对的,有get character的height和width的API,我在描述中忘记说了,您的解法很正确。极端情况有两种,一 ...

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

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 06:17:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
zzgzzm 发表于 2016-11-2 06:14
感谢解释!~
赞LZ的临场沉稳表现~~ 我感觉要是我的话若给我充足的时间最终是可以写清楚的,但在现场 ...

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

使用道具 举报

我的人缘0
 楼主| flashpacker 发表于 2016-11-2 06:18:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
zzgzzm 发表于 2016-11-2 06:14
感谢解释!~
赞LZ的临场沉稳表现~~ 我感觉要是我的话若给我充足的时间最终是可以写清楚的,但在现场 ...
.1point3acres网
我觉得他们看重的是你的分析过程,而不是题做出来与否,思路并不是一蹴而就,但是能够快速达到最优还是重要的。一点见解而已。
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-2 09:20:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
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  . From 1point 3acres bbs
  7.   unordered_map<string, pair<int,list<string>::iterator>> lastTs;
  8.   
  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. }
复制代码
回复

使用道具 举报

我的人缘0
OPheadache_h 发表于 2016-11-2 09:38:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
看楼主描述感觉拿offer应该问题不大,分析问题的思路、心态都很赞!
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-22 09:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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