狗家winter intern 面经

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多多!

第一题,是任选一个i,i 左边做一次利口二零就,右边做一次,最后找size最小的,是不?
第二题,用dfs建图,把所有路径能包含所有点的找到,算时间,找最小时间那条?楼主用indegree的方法不是类似bfs吗?

第二轮和刷题网气死三差不多吧?bellman-ford和dijkstra都可以