一亩三分地论坛

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

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

FLG 10/11月面经

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

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

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

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

x
FLG
EE PhD fresh grad
直接上干货
Facebook
店面:
1. Leetcode: FindFirst Bad Version.
2. Leetcode: GreyCode
onsite: 10/27/2015
1.  Coding:
(1) 设计一个SparseVector (就是一个超vector,大部分elements都是0)的class实现dot product的操作。follow-up1:如果一个vectormillionsof non-zeros), 另一个vector很短(hundredsof  non-zeros),如何化。follow-up2:如何利用index的关系(比如设计class定按照增的原non-zeroelementsindex一步优化。
(2) Leetcode:3 Sum
2. System Design:设计一个K recent contact 的service,就是当用户把鼠标点到chat对话框的时候,自动弹出K个最近的联系人。follow-up是如果要弹出K个最熟悉的人怎么设计,以及资源估计(需要多少台机器来做数据存储,多少个处理request等等)。
3. Research conversation。 最后15分钟做一道简单的coding题,最常见的Leetcode:Valid Palindrome原题
4. Machine Learning:SVM和logistic regression的对比分析。对全Palo Alto的居民做全样本调查,收集性别、血型、身高、体重、是否抽烟、是否有高血压。。。等数据,然后最回归分析,发现抽烟和高血压是负相关,即抽烟的人不容易患高血压。与intuition相反,为啥?设计一个news feed的排名算法,用用户的implicit反馈做label:share,clickthrough,like等。
5. Coding:
(1) Leetcode: Subset. 需要用iterative的方法做,不能递归。
(2) Leetcode:  Reverse words in a string.  
Linkedin
店面:
Leetcode: Find minimum in arotated array.
onsite: 10/29/2015
只有一轮是coding。其他都是data mining 相关面试。两个题:
1. 实现replaceStr(strings, string foo, string bar)。即在文档s中把所有foo的occurrences都替换成bar。算复杂度。
2. 实现 doublecubeRoot(double x)。可以用二分搜索或牛顿迭代法求解。
Google
店面:
第一轮:
A和B两个setof words。写一个方法返回(a) 只在A中出现的words. (b) 只在B中出现的words.(c) 同时在两个set中的words。follow-up是如果A和B很大,无法全都装进内存里,如何处理。
第二轮:
1. 给一个dictionaryof words(可以重复),实现一个方法判断一个document是不是可以用dictionary里面的words来表示出来。如果一个word在dictionary里出现了K次,那么它在这个文档里最多也只能出现K次。
2. 有很多jobs在一个machine上运行,每个job的属性有[jobID.UserID, startTime, endTime, ramRequired] 。求每个UserID的peak ram usage是多少。如果将方法扩展到大数据上?(多线程,多机)
onsite: 11/4/2015
1.  
(1) find second largestelements in an array.
(2) 给一堆2Dplane上面的点,判断这些点是不是vertical symmetric。即:是否存在一条线x=k。使得这些点关于这条线对称。follow-up是如何处理可以容许有一个点不对称的情况。
2. Rains on the sidewalk.
一个sidewalk可以用[0, 1]的闭区间表示,一个raindrop可以用[a, a+0.01]的闭区间表示,其中a是随机在[0,1]中产生的数。写一段程序simulate雨点打湿sidewalk的过程,并返回整个sidewalk被打湿所需要的时间。自己设计sidewalk的class和raindrop的class并实现两个函数:(a) 随机产生新的雨点并根据雨点的位置更新sidewalk的状态.(2) 判断sidewalk是否被全部cover。两个函数都要求是O(1)
3.
(1) 给一个2Dvector表示一个image。如果image中有值为0的pixel,就删除掉该pixel所在的行和列,最后返回一个处理后的新的image。
(2) 统计一个uint8的image的histogram。返回是一个size是256的array,其中第K个element是image中值为K的pixel出现的次数。
4.
(1) 实现一个swap的template。问如果输入的type是如下的class
class MyVector{
int*buf;
intsize;
};
如何高效地swap。
(2) 读一段程序,大概是在一个array中找一个index,使得index左边的summation和右边的summation最接近。如何用O(1) 的复杂度实现。
(3) OOP design: 设计一个Google Car 的Sensor SynchronizationSystem。从多个有着不同的CPU时钟的sensor读取message,并找到不同sensor的同步关系
5. Research conversation.

. From 1point 3acres bbs

补充内容 (2015-11-12 09:03):
Google 的4(2)应该是用O(1)的空间复杂度。Sorry。。。

评分

7

查看全部评分

本帖被以下淘专辑推荐:

 楼主| chrisliup 发表于 2015-11-12 14:02:27 | 显示全部楼层
hj867955629 发表于 2015-11-12 09:19
楼主Google 2 4能说说做法嘛?

2是把[0,1]的区间分成100个宽0.01的小格,每个小格维护两个状态,一个是从左边界算起被打湿的长度,一个是从右边界算起被打湿的长度。每次有新的雨点就更新与该雨点有overlap的两个小格的状态。如果某个小格两个长度加起来大于或等于0.01,则该小格已经被完全打湿。再维护一个counter,每次有新的小格被打完全打湿,counter加1。这样就可以O(1)复杂度实现更新小格状态和判断是否sidewalk完全被cover。

4(1) 交换指针
4(2) 扫描一遍array记下total。然后从左边扫描并累积,再从total里面减去左边的累积量得到右边的累积值。扫描一遍就知道左右相差最近的index在哪
4(3) 我也不知道,OOP不熟,凭感觉写了个,就不贴上来献丑了。
回复 支持 1 反对 0

使用道具 举报

queeniejing 发表于 2015-11-12 08:43:49 | 显示全部楼层
多谢LZ分享! 请问lz是Phd的话面的是 senior 职位吗? 感觉GOOGLE的题好难哦
回复 支持 反对

使用道具 举报

 楼主| chrisliup 发表于 2015-11-12 09:04:46 | 显示全部楼层
queeniejing 发表于 2015-11-12 08:43
多谢LZ分享! 请问lz是Phd的话面的是 senior 职位吗? 感觉GOOGLE的题好难哦

不是呀~就是普通职位。。。是比其他两家难一些
回复 支持 反对

使用道具 举报

bunnyNova 发表于 2015-11-12 09:16:23 | 显示全部楼层
谢谢分享,google题好难
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-12 09:19:54 | 显示全部楼层
楼主Google 2 4能说说做法嘛?
回复 支持 反对

使用道具 举报

swly 发表于 2015-11-12 10:24:10 | 显示全部楼层
看来还是G高大上,多谢LZ分享,F的是个ML的职位么
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 11:20:08 | 显示全部楼层
facebook system design 楼主是怎么做的?
回复 支持 反对

使用道具 举报

anyjlucky 发表于 2015-11-12 11:44:31 | 显示全部楼层
楼主L家DM的题目能不能分享一下呀!感谢感谢!还有那个抽烟的人和高血压负相关的哪道题你怎么回答的呀?
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-12 11:46:09 | 显示全部楼层
楼主,您好。
Facebook 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Machine Learning那一轮system design,要用到多少system design啊,我看有两个题目,
主要是不是做设计一个news feed的排名算法,用用户的implicit反馈做label:share,clickthrough,like等。
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-11-12 12:08:41 | 显示全部楼层
另外面试前需要先选好组吗?还是general的
回复 支持 反对

使用道具 举报

anyjlucky 发表于 2015-11-12 12:40:36 | 显示全部楼层
楼主,“设计一个news feed的排名算法” 你能不能讲讲思路啊?
有好几个行为的话,click, share, like什么的,对不同的行为给不同的score,然后learn to rank吗?
还是可以做prediction,每个行为一个predictor,最后aggregate(按不同的权重aggregate?)




回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-11-12 14:46:08 | 显示全部楼层
chrisliup 发表于 2015-11-12 14:02
2是把[0,1]的区间分成100个宽0.01的小格,每个小格维护两个状态,一个是从左边界算起被打湿的长度,一个 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
谢谢楼主,祝好运!下周三也要去onsite了,虚。。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-11-12 14:57:49 | 显示全部楼层
楼主, cube root 肿么做啊。。
回复 支持 反对

使用道具 举报

 楼主| chrisliup 发表于 2015-11-12 15:17:51 | 显示全部楼层
haifengc 发表于 2015-11-12 11:46
楼主,您好。.鏈枃鍘熷垱鑷1point3acres璁哄潧
Facebook
Machine Learning那一轮system design,要用到多少system design啊,我看有两个 ...

两个大问题大概一半一半吧。其实设计的部分比较少,主要是在讨论的过程中对各个知识点逐一考察。
回复 支持 反对

使用道具 举报

 楼主| chrisliup 发表于 2015-11-12 15:18:38 | 显示全部楼层
haifengc 发表于 2015-11-12 12:08
另外面试前需要先选好组吗?还是general的
. visit 1point3acres.com for more.
貌似不用,不过如果简历里如果有data mining相关的经历就会加面一轮machine learning
回复 支持 反对

使用道具 举报

 楼主| chrisliup 发表于 2015-11-12 15:24:11 | 显示全部楼层
anyjlucky 发表于 2015-11-12 12:40
楼主,“设计一个news feed的排名算法” 你能不能讲讲思路啊?
有好几个行为的话,click, share, like什 ...

我是按照你说的第一种来说的,不过面试官说可以用data driven的办法来给不同的行为score,比如如果你用heuristic来强制clickthrough是1,like是2,share是3的话,相当于假设like和clickthrough的距离与like和share的距离是一样的。用data driven的办法可以基于data给不同行为赋予不同的分数,比如可能更好的权重设置是clickthrough=1, like=2,share=5。
回复 支持 反对

使用道具 举报

 楼主| chrisliup 发表于 2015-11-12 15:27:06 | 显示全部楼层
hulahu 发表于 2015-11-12 14:57.1point3acres缃
楼主, cube root 肿么做啊。。

可以用binary search或用牛顿法迭代解方程 x^3 - b = 0
回复 支持 反对

使用道具 举报

 楼主| chrisliup 发表于 2015-11-12 15:28:16 | 显示全部楼层
haifengc 发表于 2015-11-12 12:08
另外面试前需要先选好组吗?还是general的
. Waral 鍗氬鏈夋洿澶氭枃绔,
不选组,但是phd的话HR会根据你背景来match相关组的人来问非coding的问题
回复 支持 反对

使用道具 举报

anyjlucky 发表于 2015-11-12 15:41:36 | 显示全部楼层
chrisliup 发表于 2015-11-12 15:24
我是按照你说的第一种来说的,不过面试官说可以用data driven的办法来给不同的行为score,比如如果你用he ...

learn to rank的算法 面试的时候都要记得吗?
构造比较的pair,然后变成binary classification的问题,这样的解法可以接受吗
还有直接optimize ndcg 和map 的解法,怎么解得,objective function是啥。。都要会写不。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 19:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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