狗家onsite面经

找人内推完,过了好久好久才收到OA,然后再网上很快就做了,都是原题,之后就直接收到了onsite了,也是很神奇,因为别的朋友都是要面一轮技术电面的,狗家的campus还是很美的,一日三餐免费,挺好吃的,还有班车,健身房,公园,游泳池什么的,感觉进去了就直接可以养老了,希望保佑保佑可能拿到狗家offer!!!

onsite一共五轮,四轮tech,一轮general,四轮都是亚裔,应该是三个中国人,一个韩国人。

第一人问的是splitwise app的那个怎么实现,比如四个人分别花了100,50,30,20,怎么相互转钱次数最少。

第二个问的是键盘一指滑动打字功能,比如说输入caront,然后你有个dictionary,然后你能找到car,cat。

第三个问的是一个tunnel往里放木头,比如高度分别是65437,从左往右放,那么你放第一个只能是3,然后放3,4,以此类推,一开始会给你一堆木头的长度,比如说23345这样。

第四个问的是一个undirected tree,然后从中间截断,两边node相等,问在哪儿截断。

最后一个general的是个印度人面试的,刚入职不就,加州理工的大佬www,问了问project,然后问了如果老板给你个活很赶,但是你手头很忙没时间做怎么办。

  1. 司柳武, 对于cost_i < mean的人把钱给另外一个人(给一个cost_j >mean + cost_i的人可以优化达到剪枝的效果)然后算剩下的人最小转账次数 + 1
  2. 和word break I II 有点像。
  3. 似乎有原题(或者是面经,不记得了。。)思路是维护一个数组tunnel tunnel[i]表示到位置i的最小值。然后把木堆排好序,按照位置选,理论复杂度是O(MlogN), 但是因为每次选好木堆之后要删除,很多语言达不到删除O(1)。
  4. 有个思路,先数算一遍count(node) = node子树节点数。 最后再遍历所有的edge。看是否能够均分。时间复杂度是O(V) + O(E)

请问楼主哪个office面的?

sunnyville的office