一亩三分地论坛

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

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

孤狗以及“拼趣斯特”跳槽面经

[复制链接] |试试Instant~ |关注本帖
tlang1991 发表于 2016-7-23 08:49:50 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@Google - Other - 技术电面 Onsite |Other在职跳槽

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

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

x
OP微软在职不到一年,因为分配的组实在不满意,毅然决定跳槽。面了Google(onsite挂),还有pinterest(offer并且接受)。现在决定发帖回报地里。先说Google:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
首先Google说来也巧,在我想找朋友refer的时候google recruiter主动找了我。楼主上大学的时候面过Google,但是死在了phone interview,被问到implement malloc & free。。。.1point3acres缃
. visit 1point3acres.com for more.
首先是phone interview,在google doc上写,一共问了三道题,都是非常简单的题,其中两到LC原题。
1. Increment a number that is represented by an array of its digits.(LC 66, Plus one)
  1. void incrementArray(vector<int>& nums) {
  2.    int carry = 1;
  3.    int size = nums.size();
  4.    for(int i = size - 1; i >= 0; --i) {
  5.       if(nums[i] + carry != 10) {
  6.          nums[i] += carry;. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.          carry = 0;
  8.          break;
  9.    }

  10.    carry = 1;
  11.    nums[i] = 0;
  12.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  13.         if(carry == 1) {
  14.       nums.insert(nums.begin()\n 1);
  15.    }
  16. }
复制代码
2. Normalize a URL by handling .. segments. For example: /a/b/../c.txt => /a/c.txt (LC 71, simplify path)
  1. string normalizeURL(const string& url) {
  2. deque<string> tokenBuffer;. from: 1point3acres.com/bbs
  3. vector<string> tokens = url.toknize('/');
  4.         int size = tokens.size();
    . from: 1point3acres.com/bbs

  5.         for(int i = 0; i < size; ++i) {
  6.                 if(tokens[i] != ..) {
  7.                         tokenBuffer.push_back(tokens[i]);. more info on 1point3acres.com
  8. } else {
  9.         if(tokenBuffer.empty()) {
  10.                 throw exception(Invalid Operation);
  11. } else {
  12.         tokenBuffer.pop_back();
  13. }. visit 1point3acres.com for more.
  14. } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15. }

  16. string result;
  17. while(!tokenBuffer.empty()) {. 1point 3acres 璁哄潧
  18.         result += / + tokenBuffer.front();. From 1point 3acres bbs
  19.         tokenBuffer.pop_front();
  20. }

  21. return result;
  22. }
复制代码
3. Given a list of numbers\n output a list of their relative ranks. For example: [10 3 8 9 4] => [1 5 3 2 4]
  1. vector<int> computeRanks(vector<int>& nums) {
  2.         int size = nums.size();
  3.         vector<int> result(size\n 0);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4. unordered_map<int\n vector<int>> indexLookup;
  5. unordered_map<int\n int> rankLookup;
  6. for(int i = 0; i < size; ++i) {
  7.         indexLookup[nums[i]].push_back(i);
  8. }
  9. sort(nums.begin()\n nums.end());
  10. int index = 0;
  11. while(index < size) {
  12.         int rank = size - index;
  13.         rankLookup[nums[index]] = rank;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  14.         while(index + 1 < size && nums[index] == nums[index + 1]) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  15.         ++index;. 1point 3acres 璁哄潧
  16. }
  17. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  18. for(auto& kvp: indexLookup) {
  19.         int val = kvp.frist;
  20.         vector<int>& indices = kvp.second;
  21.         for(auto index: indices) {
  22.                 result[index] = rankLookup[val];
  23. }
  24. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  25. return result;
  26. }
复制代码
上面楼主的code直接从google doc上粘过来的,一些引号,逗号,空格还有indentation被搞砸了,实在懒得改了,也不是难题,大家凑合吧。


过了几天通知了onsite interview,一共五轮,被不负责俄罗斯哥和傻逼阿三姐坑了,也就顺理成章的挂了。
第一轮,不负责俄罗斯哥,问的是最大假期机票问题。楼主先说了可以brute force穷举所有可行的行程,找最大,然后说可以用dp优化。然后楼主说了从第一天开始往最后一天iterate结果这俄罗斯哥就狂问问题,不让我下笔。他各种不明白,这情况咋办,那情况咋办,如何从dp array reconstruct最终的答案。然后楼主一笔没动结束了这轮,直接GG。最后楼主问他是不是解法太难懂了,人家说不难懂,标准答案是倒着从最后一天往第一天dp。。。我觉得他不负责是因为感觉他就是从题库随便挑了一题然后看了标准答案,并没有理解这题如何做,所以楼主的办法只是颠倒了顺序他就不能理解了。。。。。。Welp, guess I did not rush B
. Waral 鍗氬鏈夋洿澶氭枃绔,

第二轮,没黑我阿三哥(真他妈不容易)。问的是LC原题,LC 207(Course Schedule),还有一个system design。system design是让design一个master-slave的机制,基本上说对transaction log就在right track上。还有一些很detail的东西楼主不记得了,比如master如何找到delta然后只发给slave这些delta来最小化data through the wire。. from: 1point3acres.com/bbs

. 1point3acres.com/bbs
第三轮,极其nice中国哥。问的是string decompression的题。比如abc5[a]变成abcaaaaa。注意可以嵌套比如abc5[3[a]]就是abc + 15个a。这题recursion+一点点string manip简单搞定。最后问了runtime,和小哥讨论了一会儿觉得是exp和n!这个级别的,但俩人都不确定。最后楼主机智的说是decompressed的string长度。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

第四轮,态度极其不好傻逼印度姐+shadow的中国小哥。这印度逼全程爱答不理,我问她问题飘着白眼回答我,然后还在用自己的电脑忙。。。问的题两道,第一道就是给你个2D aray,给你个x和y然后query(y,x)和(0,0)这个长方形里面所有数的和。也是LC原题(Range Sum Query 2D)。问了几种情况,比如需要update快,比如query快,比如update和query一样快。最后扯了binary indexed tree,没让implement。第二题是一个算是problem solving的题,没让写code。你有很多绿卡的application,有很多stack of them.每个stack有很多application,多到无法把一个stack全放进memory.这些绿卡申请有重复的。要求是de-dup这些申请,并且保持原有绿卡申请的顺序。对于重复的申请,保留最早的申请。这题楼主没想出来,一直再往divide n conquer上想,但是无果。最后白眼印度姐提示是Multi-level hashing。实在想不到如何利用,gg了。


第五轮,乐呵呵白人弟。这轮应该是楼主面的最好的一轮(lol of fking course,白人一般都比较公平,不像印度逼)。问的题也比较有意思。是说你有一个正方形房间,左下角坐标(0,0),右上角坐标(1,1)。空间坐标是用float表示的,所以无法grid-ify。然后房间里有很多motion detector,每个Motion detector是个圆形。有个center还有个radius。要求让你判断一个点(没有体积)能不能从左下角走到右上角,不触发任何motion detector。这题有意思就有意思在是个graph题,其实本质是每个motion detector是graph里的一个node。如果这个点不能不触发的话,那必有motion detector连起来,从这个房间的左到右,上到下,或者斜着。用dfs或者bfs判断即可。


Google的面试总体来说方差极大。。。遇上个印度逼基本可以宣告gg。楼主是面的kirkland办公室。按理来说印度人少点,应该还好。但是在俄罗斯哥和印度姐的帮助下成功报废。

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
再说pinterest:
他们家应该算是bullshit很少的一家面试。投完简历,直接问Phone interview的时间。没有hr和你逼逼介绍流程bla bla bla。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴


Phone: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
是一个中国大哥面的,问的是:一个binary tree给你俩node,让你把从一个Node到另一个的路径print出来。这俩Node都一定在tree里。其实就是Lowest common ancestor。
. 1point3acres.com/bbs

Onsite:
貌似一共五轮,但是其实只有三轮是技术面,算法,implementation,还有system design各一轮。其次就是和这个team的manager聊天还有一轮behavior。
算法:
word break II. LC原题。需要用dp memoization.然后需要说出runtime.. 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
. Waral 鍗氬鏈夋洿澶氭枃绔,
sys design:
Design pinterest。引入pins, users, boards的概念和他们之间的关系,然后让你设计。推荐看这个网站,这个网站有各大公司DB的architecture。http://highscalability.com/all-time-favorites/


Implementation:
一个网站的hit count。需要输出15分钟内的hit count。本质是circular buffer。需要考虑system lag的情况。Follow up是如何优化。答案是可以让发送hit count的那一端先aggregate所有结果,然后发个histogram。这样可以减少hit counter的负荷。
. 鍥磋鎴戜滑@1point 3 acres
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴




楼主的跳槽之路算是结束了。实在是太费精力了。希望pinterst不坑可以让我好好学东西,发光发热。.鏈枃鍘熷垱鑷1point3acres璁哄潧
相信大家字里行间可以看出楼主对印度人的不喜欢。原因就是印度人坑了楼主太多次。楼主从大学到跳槽,基本上有印度人的面试都被黑(Google, twitter)。所以实在是厌倦了。希望我们中国人可以团结点,不知道为啥中国人总喜欢自己坑自己。。。-google 1point3acres
我觉得CS找工作,面试官的权利实在是太大了。一个Phone interview,你就完全可以一手遮天。就算jeff dean来,你要想黑他也能黑。
所以我觉得国人面国人,起码要公平公正。之前聊天有人想很变态的题,自己都他妈不会做,然后说要当面试题,楼主听了很气愤。

最后祝福大家可以拿到自己想要的Offer,面试遇到正常的面试官。. 1point3acres.com/bbs

评分

8

查看全部评分

 楼主| tlang1991 发表于 2016-7-25 13:30:22 | 显示全部楼层
say543 发表于 2016-7-25 12:29
是从起点做BFS 吗? 觉得因该从任何一个detector 做BFS 如果可以整个横跨 or 综跨 就代表no path 搂主指教 ...

不是从左下角开始。是从和正方形的几条边相交的detector作为起点开始。比如从下边开始的话,那最后如果可以一路走到上边,或者左边,那就是no pass。以此类推。
回复 支持 1 反对 0

使用道具 举报

 楼主| tlang1991 发表于 2016-7-24 13:15:09 | 显示全部楼层
say543 发表于 2016-7-24 12:36
恭喜拿到pinterest offer 最近要面google 想讨论一些面经  round 2: 只要考察是transaction log 要存在哪吗 ...

transaction log只是一个必须提的点,这个不提出来估计面试官不会问你后面的问题。他听我提出了transaction log以后开始问我Master如何Mark这些需要发送过去的delta,这我和他讨论了一通最后貌似是说得在syscall的level做一些事儿,来Mark这些delta。这人不错,一直提出新的问题并且引导你找到答案。

对,这个题的time complexity那个面试官其实都不是很确定。我后来说是指数级的他说make sense,但是他立刻提醒我换个角度想,我就说是decompressed的string长度。他就满意了。所以我觉得你答decompressed string length可以。可是我想了想,觉得如果Input是这样5[5[5[5[a]]]],那最后岂不就和5^n很接近,可能不是n,但是可能是n/2,n/3之类的?这题有大神希望可以回复一下,觉得挺有意思的,想弄明白。

每个application有applicant的名字(你可以认为这可以uniquely identify每个人),申请的时间貌似没有,因为顺序都是靠每个申请在stack里的位置来判断的。

那个link我在原帖里写了。
回复 支持 1 反对 0

使用道具 举报

wtcupup 发表于 2016-7-23 09:52:52 | 显示全部楼层
output a list of their relative ranks 是什么意思?
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-23 10:10:18 | 显示全部楼层
wtcupup 发表于 2016-7-23 09:52
output a list of their relative ranks 是什么意思?

就是这个数是第几大。[10 3 8 9 4] => [1 5 3 2 4]
10是第一大,3是最小,所以10对应1,3对应5。平局的话,比如两个10,可以都是1.
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-7-23 10:33:24 | 显示全部楼层
LZ能报个pinterst的包裹吗
回复 支持 反对

使用道具 举报

珠子手镯 发表于 2016-7-23 11:07:24 | 显示全部楼层
想请问楼主面的是什么position?
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-23 11:11:07 来自手机 | 显示全部楼层
珠子手镯 发表于 2016-7-23 11:07
想请问楼主面的是什么position?

Sde platform infra
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-23 11:21:13 来自手机 | 显示全部楼层
jmnjmnjmn 发表于 2016-7-23 10:33.鐣欏璁哄潧-涓浜-涓夊垎鍦
LZ能报个pinterst的包裹吗

Base你去glassdoor看就好,那个和我的很接近。stock的话不方便透露。实在想知道的话可以pm我
回复 支持 反对

使用道具 举报

csushin1992 发表于 2016-7-23 12:21:09 | 显示全部楼层
赞楼主的给的各公司关于system desgin的链接,可以当厕所读物了!
回复 支持 反对

使用道具 举报

Soviet 发表于 2016-7-23 12:31:09 | 显示全部楼层
楼主之前微软啥组的啊这么不满意?能透露下么。。。
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-23 15:07:52 来自手机 | 显示全部楼层
Soviet 发表于 2016-7-23 12:31. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主之前微软啥组的啊这么不满意?能透露下么。。。

Universal store下面的一个internal组。没有test framework,一天hotfix n次。根本没法呆。组里的人也不聪明,我够傻逼的了,我还算组里聪明的。。。实在没法呆
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-23 15:09:44 来自手机 | 显示全部楼层
csushin1992 发表于 2016-7-23 12:21
赞楼主的给的各公司关于system desgin的链接,可以当厕所读物了!

这东西确实不错,但感觉比较high lvl。别的大神说需要看各大公司的paper,了解lower lvl这些sys design的东西。
回复 支持 反对

使用道具 举报

Soviet 发表于 2016-7-23 15:16:19 | 显示全部楼层
tlang1991 发表于 2016-7-23 02:07-google 1point3acres
Universal store下面的一个internal组。没有test framework,一天hotfix n次。根本没法呆。组里的人也不 ...

这样啊。。那还是跳了好。。微软公司太大产品太多,组跟组之间差异还真是不小
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-24 12:36:48 | 显示全部楼层
恭喜拿到pinterest offer 最近要面google 想讨论一些面经  round 2: 只要考察是transaction log 要存在哪吗? 还有什么需求吗?  round 3: time cmoplexity 感觉不是指数级的 是不是就是o(m) m: decompressed string length 指教一下?  round 4: 什么条件能判断两个applications 是相同? 能否假设application 有id 跟申请的time stamp ? 也就是说同样的id 代表是相同的applications?   可以顺便求一下各公司关于system desgin的链接 的link 吗 ? thanks
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-24 13:34:23 | 显示全部楼层
感谢分享。楼主能详细说下最大机票问题吗,在面经里看到过,但是都不太全。谢谢
回复 支持 反对

使用道具 举报

sophiehu 发表于 2016-7-25 00:25:44 | 显示全部楼层
谢谢楼主,希望楼主今后都顺利。也希望我能找到 工作 T T
回复 支持 反对

使用道具 举报

flying2001 发表于 2016-7-25 00:46:49 | 显示全部楼层
谢谢分享。 对于google第5轮,那些detectors是以graph的形式给的吗?如不是的话,怎末建这个graph?另外,还是不明白怎么dfs/bfs就能知道能不能路可过?能不能再详细点解释一下?十分感谢。
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-25 04:02:57 来自手机 | 显示全部楼层
flying2001 发表于 2016-7-25 00:46
谢谢分享。 对于google第5轮,那些detectors是以graph的形式给的吗?如不是的话,怎末建这个graph?另外, ...

给的时候只有半径,还有在正方形里面的坐标(x,y)。首先你可以判断哪些圆相交,圆心距vs半径和。每个圆是个node,相交的圆可以看作之间有个undirected edge。你还可以找出哪些圆和正方形的变相交,这些圆是你的destination。这样你的graoh就出来了。你从起点run bfs,如果有一条path从起点到任意destination,那就说明无法cross这房间,肯定碰detector
回复 支持 反对

使用道具 举报

 楼主| tlang1991 发表于 2016-7-25 04:03:34 来自手机 | 显示全部楼层
sophiehu 发表于 2016-7-25 00:25
谢谢楼主,希望楼主今后都顺利。也希望我能找到 工作 T T

加油。找工作感觉随缘程度很大。
回复 支持 反对

使用道具 举报

sophiehu 发表于 2016-7-25 09:29:35 | 显示全部楼层
tlang1991 发表于 2016-7-25 04:03
加油。找工作感觉随缘程度很大。

谢谢楼主,我还在努力刷题,能看出来楼主是很努力的人  加油 :)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 00:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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