一亩三分地论坛

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

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

独角兽,谷歌和脸书 onsite

[复制链接] |试试Instant~ |关注本帖
yakhe 发表于 2016-3-25 23:19:51 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Pass在职跳槽

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

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

x
注:华人独有资源,请勿翻译成英文,尽量不要用英文回复,谢谢!. Waral 鍗氬鏈夋洿澶氭枃绔,

三月面的,有幸都过了,题目都mix了,GFU的,都准备就是了。不要谢我,碰上同胞多帮忙就好了!
这次面了六个公司,所有的国人都很好很帮忙,感激不尽啊!
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
一点建议:
0. 题目理解完之后先把自己要做的事情一件件跟面试官说一下,比如打算先设计算法,再决定写几个类/函数,然后coding,然后跑test cases,然后分析复杂度,然后谈谈改进,这样一个是面试官心里有数,不至于看到bug就要指出来,会等到你跑test cases;另一个你和面试官都会有个时间把握,如果面试官觉得你时间不够了,可能会让你skip一些coding;再一个你自己时间不够了,也不至于后边就全是0,至少正确的流程摆在那了,feedback也会好看一些
1. 碰上难题很正常,不要慌,和面试官一起分析,找解法,犯了错误也不要紧,面的就是这个过程
2. 白板编程,不要上来就下笔,那样会很乱。先把框架打起来,要写哪几个类,哪几个函数,然后往里填。如果碰上复杂的操作,比如数组越上下界检查,不妨另写一个inline或是macro来做,这样不影响主程序的清晰度
3. 一边写一定要一边解释,闷葫芦不行. Waral 鍗氬鏈夋洿澶氭枃绔,
4. 写完了不要拍拍手就很高兴了,一定要跑test cases!!
5. 尽量避免和面试官争论,即使他错了,旁敲侧击提醒他就是了
6. 碰上不善的烙印要会保护自己,找个合理借口,礼貌的把白板自己拍了照片再说,不然太被动。我现在就后悔12题那一轮没拍照片!



1.  设计实现 ClickCounter,每次被click时候onClick被call到,timestamp是以秒为单位的,getCount需要返回前M秒内所有的点击数。 假设:无需考虑多线程
class ClickCounter {
public void onClick(int timestamp) {}
public int getCount() {}. Waral 鍗氬鏈夋洿澶氭枃绔,
}
这题做的一般般,想复杂了,幸亏主面试官是国人,很照顾,感谢!


2. 给三个数组A,B,C,都是正整数,数有重复,要求返回所有的组合(a,b,c),使满足:a 属于 A,b 属于B,c属于C, a+b=c
要求编程,并分析时间复杂度和空间复杂度
延伸:四个数组,返回所有(a,b,c,d)组合,使a+b+c=d, 分析时空复杂度
. from: 1point3acres.com/bbs           N个数组,分析时空复杂度. 1point 3acres 璁哄潧
这题也是国人面试官主面,白人shadow。coding没问题,哈希表解决(跑完test case后还考虑过排序是否能更快,被主面果断提醒不要管排序,多谢!)。到N个数组时候分析复杂度颇有坎坷,跟两个面试官一起讨论了半天,几番提示,终于对了。惭愧!. more info on 1point3acres.com


3. 说你发明了一种新编程语言,操作一个足够大的正整数数组,有下列符号:
.  输入存到数组当前位置
/  输出当前数组元素. from: 1point3acres.com/bbs
> 当前操作位置在数组中右移一位
< 当前操作位置在数组中左移一位
+ 当前元素++
-  当前元素--
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷[  while (当前元素>0)
]  end while
举例: .++/    如果输入是2,那么输出为4
要求:编程,接收用户两次输入a和b,输出 a+b
延伸:同上,但要求不但输出a+b,还要输出a和b
这题是hiring manager问完behavior问题还剩10分钟问的,不难

4.  a. 荷兰国旗问题
     b. Trie, 构建前缀树,在树里搜索字符串,要支持*(匹配任何字符)
     国人面试官,非常nice
. 1point 3acres 璁哄潧
5. 设计稀疏向量(sparse vector)的数据结构,并做点乘. 1point 3acres 璁哄潧
    白人面试官,相谈甚欢.鏈枃鍘熷垱鑷1point3acres璁哄潧

6. cultrue fit问题, 问了做过的印象最深刻的项目,问了为何要加入xxx,问了如果工作中和同事意见相左怎么解决. visit 1point3acres.com for more.
    问完了还问了个小coding:
    1   2   3   4
    5   6   7   9. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    9 10 11 12
    对角顺序打印矩阵, {1}, {2, 5}, {3, 6, 9}, {4, 7, 10}, {8, 11}, {12}
    白人senior manager(还是director的)面的,有点紧张,没细看题目,就开始写zigzag,幸亏他人好,立刻提醒,一身冷汗,还好有惊无险

7. 设计题,设计 tweet search 系统,要求 50 million tweets/day,50 million searchs/day,搜索只需要支持搜索两个关键词的and和or,要搜索最近一年的所有tweets
这轮是加面的,因为onsite当天的设计轮问错了问题(楼主面的后端,被问了前端的问题,幸好那轮主面也是国人,一番爱护之后给加面了这一轮)
面试官是白人,长得巨像big bang里那个 Sheldon,忍得好苦没开口问,哈哈
难点是最后一问,说用户搜索两个很热门的关键词,比如奥巴马和贾斯汀碧波,然后timeout了,问为啥? 如何解决? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这一问没答出来,我说了cache热门关键词搜索结果、在写路径上预处理热门关键词两个方案,都被否决.鏈枃鍘熷垱鑷1point3acres璁哄潧
最后Sheldon说: “我直接告诉你答案吧,当年我被面这个问题,也没答出来,所以也没指望你能打出来”. Waral 鍗氬鏈夋洿澶氭枃绔,
我立刻识趣的大拍马屁!
正确解决方案是:
不要按关键词shard reverse index
而是按tweetid shard tweets,搜索的时候,每台机器产生一个本机的搜索结果,然后一级级combine,就快了

8. 一个二维矩阵,每个格子可以是空E、墙W或是灯L,设计算法计算每个空格E可以看见几盏灯L. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
国人面试官,很nice,写了O(n3)先,然后优化为O(n2)

9. 桌上摆着一排不同面额硬币,两个player A和B轮流拿走最左端或是最右端的硬币,设计算法求A能拿走的最大数额
俄罗斯人面试官,也很nice
. visit 1point3acres.com for more.
10. 打印二叉树中所有的重复子树
烙印面试官,不是很nice,我的算法是用一个子树的preorder+inorder做key,把树遍历一遍就能搭建一个hashtable<key, vector<node>>,然后把hashtable里所有vector size大于1的都打印出来就行了
面试官显然不是一个想法,他先是提示,问说什么情况下认为两个子树是identical?我说左右子树都identical,他又问那你是不是能写一个函数叫isIdentical(),我就猜到他问这个问题,之前的candidate肯定都晕了,然后他就这么提示,先写这个,然后brute force,然后优化。
我就直接很nice的说不用写这个isIdentical(),他问为啥,我说preorder+inorder唯一确定一棵二叉树。他又问为啥,我又在板上画了半天给他解释,全解释完了快20分钟了才开始coding。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
还好写完了,跑test cases的时候发现几个bug都修了。.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉烙印一个最大的不同是,他发现bug一定要当场说出来,哪怕我事先说了要跑test cases找bug,人家直接忽略,annoying!!!
. more info on 1point3acres.com
这轮的feedback不是很确定,不过即使不是100分也不至于不及格

11. a. 写程序把十进制转成k进制 (2<=k<=16).鏈枃鍘熷垱鑷1point3acres璁哄潧
      b. 把vector<string> serialize成string,然后deserialize回来
国人面试官,没得问题!

12. 设计+编程. more info on 1point3acres.com
假设你是一个大楼水管工,负责给一栋新大楼的底盘排水管,大楼底盘是一个二维矩阵,每个格子可以排水管也可以空着,水管入口在左上角,出口在右下角,有三种水管可以选,直管、直角弯管和T管,水管排的时候可以在平面上任意旋转。
设计数据结构表示水管、水管走线, 设计算法计算某给定走线是否从入口通到出口,是否漏水。. 1point3acres.com/bbs

烙印面试官,这轮确定是被他阴了,可惜忘记他名字了,是一个卷发略有驼背的40多岁的烙印,之前在vmware干过

我的解法是用adjacent list表示图,水管类型决定adjacent list的size,DFS找出口并mark水路,检测漏水就看管子是否在水路上并且是否有未接开口(adjacent list里有NULL),跟上一个烙印一样,这个家伙也是不管你最后跑不跑test cases,看到有bug就要折腾半天,妈的我程序还没写完呢,就被他数次打断。最后拼了终于写完,test cases也跑完,但是估计之前他指出的几个bug都被写到feedback里了,干!. visit 1point3acres.com for more.

13. 设计+编程  . 鍥磋鎴戜滑@1point 3 acres
这轮是加面的,就是因为被12的烙印阴了,还好其他feedback估计不错,Recruiter说给加面一轮 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
设计CallLater库,用户call registerCallback来注册一个callback,和一个delay值(精确到ms),这个库需要在delay ms之后call用户的callback. visit 1point3acres.com for more.
要求:1. 不能假设用户的callback的执行时间,可能很长也可能很短
          2. 要求吞吐量20million /day
          3. (隐形要求)显然了,多线程
class CallLater {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
public void registerCallback(FUNC_POINTER callback, int delay) {}
}
韩国面试官,人很好,我一边写一边解释,这位就很安静,从不打断,我用的每个callback产生一个新线程,也跟面试官讨论过线程池,但是不熟悉boost的线程池,自己写又没把握,所以跟面试官说我先用generate新线程写,因为很多c++实现新开线程也是很light weight的,最后看看有时间再改成线程池,他说好。
写完代码后没时间了,就在google doc上说了下怎么建testbench,怎么改进
这轮feedback应该是positive,不然不可能拿到offer. more info on 1point3acres.com


. 鍥磋鎴戜滑@1point 3 acres



补充内容 (2016-3-25 23:24):
14. design Netflix
白人面试官问的,这个就很野了,准备这类题的路数请参考九章算法系统设计班
.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-3-25 23:25):
u是两轮coding,一轮desgin,两轮culture fit,他家一定要准备behavior question,coding都是两个面试官,一个煮面一个shadow


补充内容 (2016-3-25 23:27):
f是两轮coding,两轮design,一轮culture fit
G全是coding,design轮设计完了也要coding,最变态!

评分

3

查看全部评分

bobzhang2004 发表于 2016-3-25 23:34:46 | 显示全部楼层
多谢分享,不过没有分公司啊
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-3-26 12:35:57 | 显示全部楼层
楼主能说下哪几道是U的嘛?
回复 支持 反对

使用道具 举报

user123456 发表于 2016-3-26 13:13:01 | 显示全部楼层
谢谢分享!可是如果对方不让拍照呢?
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-3-26 14:11:24 | 显示全部楼层
延伸:同上,但要求不但输出a+b,还要输出a和b
这题要求输出a和b是在a + b后面吧?楼主怎么做的?

reorder+inorder唯一确定一棵二叉树

这个树中有duplicates就不能确定吧?
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-3-26 14:25:47 | 显示全部楼层
a+b=c 那题最快 n^2? 用hashset存所有C的值
回复 支持 反对

使用道具 举报

bbsbbstry 发表于 2016-3-26 14:42:56 | 显示全部楼层
想请问下楼主是new grad么?
回复 支持 反对

使用道具 举报

appliang 发表于 2016-3-26 15:30:43 | 显示全部楼层
谢谢分享干货
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 12:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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