timeline:
9月初找人内推,一周后收到邮件,约了面试
9月30日,两轮back to back phone interview
10月10日, 收到邮件说要加面(哭)
10月18日, 加面
题目
第一轮:
题目抽象出来就是给一个array,找出和为K的两个不overlap的subarray,让它们的number of elements最小
比如:[1,1,1,2,1,2,1], K = 3, 结果应该是[2,1],[2,1]。 错误结果:[1,2][2,1] 因为overlap了
第二轮:
给一系列task,还有它们的depency关系,和完成这个task所需要的时间,假设有无限的资源,问所有task完成时间最少要多久
Task{
int time;
vector<Task*> next;
}
我这题用dfs写的,先找到所有indegree为0的node,然后对这些node各自dfs一次,找到最大时间,在所有的最大时间里求最大。后来问时间复杂度我答不上来了,应该是这个被加面。
后来觉得可以加一个weight为0的dummynode作为0 indegree node的起点,从这个dummy node做dijkstra,不知道是否可行。想问问大家有没有好办法。
第三轮:
给两个api,写webcrawler
- string getwebcontent(string url)
- vector geturl(string webcontent)
最开始我用dfs递归写了,他说ok
followup1: 如果stack overflow了怎么办,我有点懵,找他要了提示,然后用bfs写了一遍
followup2: 如果执行时间太久怎么办,还是有点懵,聊了一会儿说用multithread,需要一个thread safe hashset 和 thread safe queue,因为时间不够了,没有实现,说了下想法
攒攒人品,希望可以过吧。。。但感觉希望有点渺茫了,现在已经10月底,我是winter intern,即使过了估计也很难team match上了。
Anyway,祝大家面试顺利,offer多多!