一亩三分地论坛

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

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

Youtube 11/17 Onsite 面经

[复制链接] |试试Instant~ |关注本帖
AnthonyNeu 发表于 2015-12-5 06:38:22 | 显示全部楼层 |阅读模式

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

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

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

x
第一轮:亚洲人,Youtube Security组,上来问了简历,然后出了一个题:
implement a CSV parser.. Waral 鍗氬鏈夋洿澶氭枃绔,
input: a, a'b, c, d'c, b
output:
a      
a'b, c, d'c        
b

. from: 1point3acres.com/bbs
要求是:
1. 用,分隔string
2. 两个单引号之间是一个字符串的一部分
3. 两个单引号相连转义为一个单引号的 ‘’  ->  ‘

我写完这个题之后被面试官指出了一个bug,写完改完bug大约花了20多分钟。 因为这个题目的corner case比较多,所以我也就处理了一些情况,比如两个引号内部有引号的情况等。.鏈枃鍘熷垱鑷1point3acres璁哄潧
之后面试官又开始问简历,问了我的某个DBMS的项目有没有实现concurrency,transaction以及有没有实现SQL parser。. Waral 鍗氬鏈夋洿澶氭枃绔,

第二轮:. 鍥磋鎴戜滑@1point 3 acres
白人,Youtube Music组。
问了一个3 Sum Smaller,10分钟写完了。然后面试官说可以了,我们做下一个题:
Suppose we have a line and M points in this line. If we define the distance of a subset of points which has N (N <= M) points to be the minimum distance of the distance between of each pair of point, write a algorithm to find the maximum distance of a subset which has N points.
举个例子,加入我们有一条直线,上面有x = 1, x = 2, x = 5, x = 10 等等的点,给定一个数字N = 2。那么能让这个距离最大的点的子集就是{x = 1, x = 10}。

经过面试官提示之后可以先实现一个简单的function:. 1point 3acres 璁哄潧
给定一个距离d,如果可以找到一个含有N个点的子集让距离等于d,返回true,否则返回false. 大致意思就是需要一直使用这个简单的function去尝试找到最大的d。. from: 1point3acres.com/bbs

第三轮:.鐣欏璁哄潧-涓浜-涓夊垎鍦
国人,
longest substring without repeated characters
longest substring with at most two distinct characters

follow up:
对于第二个题目,要是传入的不是string而是data stream应该怎么办?
因为我用的是hash table存的每个字母对应的下标地址,所以面试官又问我怎么优化空间。


第四轮:
白人,Youtube Gaming 组,感觉面试得最好的一轮。
实现一个name query system,是一道面经里面出现过的题目。我用trie写了代码,然后问了一堆follow up:
1. 如何压缩trie的空间?
2. 在进行prefix匹配的时候,如何在执行用户每个query的时候降低搜索的负载? 大致就是如何优化auto complete的问题,或者如何防止恶意请求。
3. 在返回搜索结果的时候,怎么决定返回值里面姓名的priority?

四轮里面第一轮的面试官不满意,觉得我写代码的速度太慢。 第二轮的第二题是在面试官给出提示之后才想明白的,面试官也不是很满意。最后HR在面试完的第二天就给了feedback:
. visit 1point3acres.com for more.
一二轮面试官不满意,后面两个面试官都是positive,比较满意。然后HR就跟我说挂了,不进HC。


评分

10

查看全部评分

本帖被以下淘专辑推荐:

 楼主| AnthonyNeu 发表于 2015-12-17 11:25:20 | 显示全部楼层
xiaoniuona 发表于 2015-12-17 11:18
所以一旦出现一个引号,直到最后一个引号之间都是一个字符串?譬如a, a'b, c’, d"c, b“d,ba里面 a'b,  ...

你的例子应该输出

a. more info on 1point3acres.com
a'b,c'
d'c
b'd
. 1point3acres.com/bbsba

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

xiaoniuona 发表于 2015-12-14 06:55:23 | 显示全部楼层
AnthonyNeu 发表于 2015-12-13 12:47
正在等大神写。。并不会

我在StackOverflow上找到个DP解法:
http://stackoverflow.com/questions/22424885/find-subset-of-size-k-such-that-the-minimum-distance-between-values-is-maximum

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

xiaoniuona 发表于 2015-12-9 05:11:47 | 显示全部楼层
AnthonyNeu 发表于 2015-12-9 03:08
因为这个地方是at most two distinct,所以我觉得这个heap其实优化的程度并不大

面试官只是对于我用一 ...

at most two的话,不用hash table,也不用min heap,直接2个指针维护window的start和end就好了,扫描的时候每次char跟前一个不一样了,就把end移到前一个,也就是最后出现的地方。
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.length()<=1) return s.length();
        int length=0;
        int start=0, end=-1;
        for(int k=1; k<s.length(); k++){
            if(s.charAt(k)==s.charAt(k-1)) continue;
            if(end!=-1 && s.charAt(k)!=s.charAt(end)){
                length=Math.max(length,k-start);
                start=end+1;
            }
            end=k-1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        }
        length=Math.max(length,s.length()-start);
        return length;
    }

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

姐姐不吃糖 发表于 2015-12-5 12:54:54 | 显示全部楼层
这么严啊,两个negative就不进HC了。。。LZ在MTV的那个YouTube面的吗?
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-5 14:15:09 | 显示全部楼层
姐姐不吃糖 发表于 2015-12-5 12:54
这么严啊,两个negative就不进HC了。。。LZ在MTV的那个YouTube面的吗?

没见过给两个negative还能进HC的,进HC的都是没有negative 还有strong positive 的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-5 15:34:05 | 显示全部楼层
姐姐不吃糖 发表于 2015-12-5 12:54
这么严啊,两个negative就不进HC了。。。LZ在MTV的那个YouTube面的吗?

San Bruno面试的
回复 支持 反对

使用道具 举报

orangepie 发表于 2015-12-6 04:27:53 | 显示全部楼层
请问楼主 第四轮, 第二问降低搜索负载, 是什么意思呢,  是说在座auto completion 的时候,只搜索一些概率更大的一些possible query吗?
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-6 04:46:17 | 显示全部楼层
orangepie 发表于 2015-12-6 04:27
请问楼主 第四轮, 第二问降低搜索负载, 是什么意思呢,  是说在座auto completion 的时候,只搜索一些概 ...

可以啊,我说的是限定搜索的深度
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-6 12:46:18 | 显示全部楼层
LZ能解释一下第2题吗 比方说有 x = 1, x = 4, x = 10, 那distance 是 (4 - 1) + (10 - 1) + (10  - 4) 吗?

补充内容 (2015-12-6 12:58):.1point3acres缃
好像看懂什么意思了 distance 是指MIN((4 - 1), (10 - 1), (10 - 4)) = 3. 那做法可以把N中的两个点定在最远的两个点 比方说1 和 10, 然后在剩下的 点里面选 N - 2, 算出每种combination的distance, 然后取MAX?
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-6 13:05:39 | 显示全部楼层
LifeGoesOn 发表于 2015-12-6 12:46
LZ能解释一下第2题吗 比方说有 x = 1, x = 4, x = 10, 那distance 是 (4 - 1) + (10 - 1) + (10  - 4) 吗? ...

不能算combination,复杂度太高

可以每次选择一个点X,然后去(X, X + d)里面找下一个点。要是能够找到N个点的话就返回true,否则就是false。
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-7 08:38:48 | 显示全部楼层
AnthonyNeu 发表于 2015-12-6 13:05
不能算combination,复杂度太高
. 1point3acres.com/bbs
可以每次选择一个点X,然后去(X, X + d)里面找下一个点。要是能够找到N ...

明白了 学习了。 但是还有一个问题  那d的增幅是多少呢? 每次加1 吗, 还是把所有distance排个序, 从这个排序的list里面选
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-7 09:04:29 | 显示全部楼层
LifeGoesOn 发表于 2015-12-7 08:38 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
明白了 学习了。 但是还有一个问题  那d的增幅是多少呢? 每次加1 吗, 还是把所有distance排个序, 从这 ...

可以先找到一个(d1, d2)的范围 d2 = d1 * 2,然后在这个范围里每次增加1找最大值d
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-8 02:35:16 | 显示全部楼层
谢谢分享~请问楼主是在san bruno面的嚒?还是MTV?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2015-12-8 02:36):
刚看到是在san bruno,不好意思啊,问重复了。。。
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-8 02:40:02 | 显示全部楼层
请问楼主第三轮第二题如果传入的不是string而是stream该怎么做呢?
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-8 02:47:49 | 显示全部楼层
xiaoniuona 发表于 2015-12-8 02:40
请问楼主第三轮第二题如果传入的不是string而是stream该怎么做呢?

用一个min heap,存在sliding window里面每个字母最后出现的Index

每次pop出heap的最小index,移动指针就行
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-9 00:58:06 | 显示全部楼层
AnthonyNeu 发表于 2015-12-8 02:47
用一个min heap,存在sliding window里面每个字母最后出现的Index.1point3acres缃

每次pop出heap的最小index,移动指针 ...

可是min heap里怎么用新的index覆盖掉原来的呢?譬如说a之前是第3个,add了3进min heap,之后第7个又是a,怎么把3去掉呢?e.g. bbabbbac这种
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-9 03:08:17 | 显示全部楼层
xiaoniuona 发表于 2015-12-9 00:58
可是min heap里怎么用新的index覆盖掉原来的呢?譬如说a之前是第3个,add了3进min heap,之后第7个又是a ...

因为这个地方是at most two distinct,所以我觉得这个heap其实优化的程度并不大

面试官只是对于我用一个hash table存 字母到index list的空间复杂度不满意,我就说其实只需要存最后一个出现的index就行了。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

然后她问我能不能不用hash table,我说可以,就维护min heap就行了。.鐣欏璁哄潧-涓浜-涓夊垎鍦

在用two pointers第一次扫描的时候, 你就直接可以把pointer移到a最后出现在7,b出现在6,下次直接把(6,b)这个tuple从min heap pop出来,然后直接把pointer移到6。
回复 支持 反对

使用道具 举报

wildchild 发表于 2015-12-9 13:54:26 | 显示全部楼层
lz请问一下电面的时候是什么题目呀?
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-9 13:56:21 | 显示全部楼层
wildchild 发表于 2015-12-9 13:54
lz请问一下电面的时候是什么题目呀?

没有电面
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-10 09:52:38 | 显示全部楼层
请问楼主最后一道题能详细说下嚒?面经里没看到过诶,或者能把您看的面经发我下嚒?xiaoniuona@gmail.com 谢谢啦!
回复 支持 反对

使用道具 举报

 楼主| AnthonyNeu 发表于 2015-12-10 10:22:03 | 显示全部楼层
xiaoniuona 发表于 2015-12-10 09:52
请问楼主最后一道题能详细说下嚒?面经里没看到过诶,或者能把您看的面经发我下嚒? 谢谢啦!

1. compressed trie. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

2. restrict DFS level-google 1point3acres

3. use frequency
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 13:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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