脸书新鲜电面面经

上周末刚刚结束脸书的实习电面 遂来分享华人大叔,比较耐心
题目如下

  1. merge 3 sorted lists
    举例:[-6, 1, 2] [-7, -6, 2, 5] [0, 5, 19] => [-7, -6, 0, 1, 2, 5, 19]
    算是简化版的 利口 儿山?
    每个输入list中没有重复,要求在合并后的list里面干掉重复的元素,O(n)解

  2. 给一个整数array [1,2,3,4,5,4,1,1,2,3,5] 和 k=3
    求包含只有最多k个不同元素的最长subarray的长度。
    这个例子里面最长的subarray 是 [4,5,4,1,1] 长度是5,答案也就是

**附加一个从别处听来的电面试题,也是脸书实习:
输入:[1,5] [8,10], [12, 15], 此时闭区间的涵盖范围sum = 5+3+3 = 11
附加输入区间 [11,16] 时,只计算之前区间未覆盖的数字加到sum 里面,也就是 11+1+1=13

感觉就是变种的merge intervals。 把新的区间merge到之前的list里面 得到新区间列表[[a,b],[c,d],[e,f]…]
之后遍历 计算 b-a+1 + d-c+1 + f-e+1 …即可得到sum. 不知道有没有更好的办法

祝大家顺利!

补充内容 (2018-11-7 04:58):
回头看了一下一年前刷过的题目,才发现第二题就几乎是 利口 易武久。。hard的题目啊 下手真狠。也不知道我那时候给的解是不是满意。

最后一个 “从别人那听到的题”,可以用segment tree,insert 一个新的interval再算sum的时间复杂度 O(logn)

1 Like

Segtree一开始需要知道range吗?

请问第二题是不是利口 伞寺凌?就是把 substring 换成了 subarray,思路都一样的?

第一题,merge前两个,然后再用merge好的merge第三个?还是pq直接merge所有lists? 第二题双指针,hashSet. set size一旦>k就move左指针?

merge 的问题是要直接merge 三个,不可以两两merge。

是的,三司令 会比较更难一点,易武久 是k=2的情况,十分类似

请问一下 楼主 第一题的O(n) 是怎么解的呀

假设三个list A B C 长度分别为 x, y, z
然后 j = j = k = 0
while j<x and j<y and k<z:
取min(A, B[j], C[k]) append到result list上
然后如果A, B[j], C[k] 任意一个等于现在的result list 最后一位,i或者j或者k++

然后你需要三个while 循环来cover A B C其中一个最短的结束了的情况
while j<x and j<y:
添加较小的那个
while…
while…

然后同理你还需要三个 while 去处理 两个 list 结束的情况。

然后结束了。

每一个list 的元素都过了一遍,所以复杂度是 O(x+y+z)
这个方法代码会比较长,但是确实work。不知道有没有更巧妙的办法。

补充内容 (2018-11-17 14:26):
抱歉,两个 j 应该被替换为 i。typo