LinkedIn 实习电面 ml track 二面

原帖地址:一亩三分地

今天面了二面,只能用两个字形容,MD。。。。
之前HR联系我,今天面试官是两个中国人,主面试官还是女的,然后安排到了中午12:00-1:00,我以为会轻松加写意。谁知道接起电话,一个阿三的口音。。。。。
聊了两句,三哥直接贴题:

Update a set of (upto) K elements, when you see a new element from an incoming stream, to ensure that every element seen so far, has an equal chance of making it into the set of K elements that we are maintaining.

// newElem is the N+1th element

stream = [1, 2, 3, 4, 5, 6, 7]
K = 1

currentK = Any of the 7C1 possible combinations, e.g., 1 or 2 or 3 …

newElem = 8
currentK = Any of the 8C1 possible combinations

public elem[] updateK( int K, int N, elem newElem, elem[] currentK) {
}

Example:

K = 2;
elem = [1,2,3,4,5,….]

for (int i = 0; i < N; i++) currentK = updateK(K, i, elem[i], currentK); 这题太confused了, 楼主读题和理解题意用了二十分钟。。。。。。 然后开始code, 我新建了一个 数组等于 stream, 然后加入新的newElem, 组成新的要操作的stream。然后用DFS,产生新的combination序列。 然后三哥说stream could not be accessed。我心想,我去。。。。 我说可以用从 currentK 里边不断读取元素,recover 这个 stream 里边的元素。用一个Hashtable 存元素,如果Hashtable size 等于N,就停止。然后做DFS产生新序列。 三哥说,make sense. 但是 我忘了说一个前提,N个元素是内存存不下的。。。。。。我心想,我日了狗了。。。。 最后三哥告诉了我答案,这个可以用 reservoir sampling. 具体的可以Google 维基百科,就是通过有概率证明,N 足够大的话,随机选 N-k 就能实现了。这是coding 题么。。。。。 然后三哥开始问ML的问题,说你的简历做过Recommendation System,那我们来聊一下 Collaborative Filtering 吧。 他让我把 Objective function 和 优化方法写上去, 我说 我用的 Alternative Least Squares 做的, 就是 把 rating matrixdecompose 两个矩阵, R≈U*V, 然后U和V 分别加 regularization term. 然后他问 如果 U 已知怎么办,我说那就变成 regression 问题了,可以把U当成 sample, 对应的 R 中的值当 label。可以用regression 一列一列地解R中的 missing value。 然后他说know the country and age of users, can we use that information, 就是 U的 dimension 变成了 nx2(n is sample number). 我说 这种情况下 解出来的V的 rank 来低了,最后预测出来的结果不会太好。 他说: can you improve it?我说 可以让 U =[U1, U2].U1 是已知的, U2 是要求的,然后 objective function 中 加 U2 的 regularization term, U1 是已知的就不加了。然后同样用 Alternative Least Squares 求解。 Objective function 就变成了 ||R-(U1+U2)*V||F+ lambda1*||U2||F+lambda2*||V||F, 让后解出来 U2和 V, 然后U2 和U1 recover 原来的U, 就可以通过 U*V 来预测 R中的 missing value. 然后就到点了,QA 总体感觉第二问勉强答上来了,但是第一题答的太屎了,randomized 的算法知道的太少,估计这次要挂。。。。 楼主RP真的太爆发了,面的两次地里的面经一个题都没碰到。。。。