MTV狗狗昂塞1108

Job Hunting Interview
, , , , , ,
1

第一轮白人小哥，设计rate limiter。给定max QPS，让你设计一个boolean function判断能不能execute incoming task request…我用了一个deque记录每1ms的task count， 并且记录total task sum
follow up：如果QPS dynammic变化的怎么办…比如说server能承载的max qps是100，实际访问qps是1000, 要求平均地选择task来处理(每0.1秒accept一个)，不能有spike…我说那就dynamic的变化rolling window的size 和对于每个rolling window的max qps…也不知道他满不满意反正follow up没写code…

第二轮亚裔 给一个array，可以拼数 求拼数的和是否等于target，dfs。第二题find peak element……lz难题做太多这题卡壳了……edge case想不清楚……希望不要挂我这轮呜呜呜他说这题有个followup是2D find peak elelment但是没时间问我了

第三轮东欧人 一个array有正有负，两个player，每次能从左边拿一到三张牌，求player1能拿到的最大sum，dp

第四轮中国人 DNA找sequence 比特操作，蠡口以巴期原题秒，象棋走日求留在chessboard里面的概率 蠡口刘粑粑原题秒

第五轮墨西哥女 给一个Song class，里面有song的rating，给一个list of song，用户random playlist的时候，求根据rating的高低random输出song。cumulative possibility
第二题 给一个只有0和1的array，找一个cut position suchthat #0 on left + #1 on the right的sum最大，return这个index
比如 0 1 0 | 1 1 1 0 1 0 1 sum=7 return idx

lz是女生，硬件三年转软件。上周四面哒发个面经攒攒人品！！求过求过！！！

2

cut右边的1 = N1 - cut左边的1
所以求max(cut左边的0 + cut右边的1) = N1 + max(cut左边的0 - cut左边的1)。
也就是从左向右遍历数组并记录当前0和1数目的差，当这个差最大时的index即为所求。

3

find peak应该是一道binary search，楼主加油，肯定可以的

4

比如 0 1 0 | 1 1 1 0 1 0 1 sum=7

cut这道题你是在idx = 2之后cut算出的7，其实idx = 0之后也可以得到7？左边1个零，右边六个1
有什么好的解法吗

5

查了下发现 2D peak 竟然还有一个O(n)的解法

6

最后一个是用两个map记录1和0的频率然后cut从左往右运行的时候更新两个Map吗？

7

楼主能问下第五轮的player list random 输出song 的具体标准是什么么? 不太明白为什么跟cumulative possibility 有关系。

8

dp(i, j)表示从i到j区间能取到的最大值。
dp(i,j) = max dp1(i+k, j) + sum(i, i+k) k = {1, 2,3}
dp1(i, j)表示从i到j自己取完后对手能取到的最大值的最小值。
dp1{i,j} = min dp(i+k, j) k = {1,2,3}