Youtube 11/17 Onsite 面经

原帖地址:一亩三分地

第一轮:亚洲人,Youtube Security组,上来问了简历,然后出了一个题:
implement a CSV parser.
input: a, a’b, c, d’c, b
output:
a
a’b, c, d’c
b

要求是:
1. 用,分隔string
2. 两个单引号之间是一个字符串的一部分
3. 两个单引号相连转义为一个单引号的 ‘’->‘
. 鍥磋鎴戜滑@1point 3 acres
我写完这个题之后被面试官指出了一个bug,写完改完bug大约花了20多分钟。 因为这个题目的corner case比较多,所以我也就处理了一些情况,比如两个引号内部有引号的情况等。
之后面试官又开始问简历,问了我的某个DBMS的项目有没有实现concurrency,transaction以及有没有实现SQL parser。

第二轮:
白人,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: 给定一个距离d,如果可以找到一个含有N个点的子集让距离等于d,返回true,否则返回false. 大致意思就是需要一直使用这个简单的function去尝试找到最大的d。 第三轮: 国人, 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: 一二轮面试官不满意,后面两个面试官都是positive,比较满意。然后HR就跟我说挂了,不进HC。