11/19 sunnyvale 4轮狗家昂赛

11/19 sunnyvale 4轮狗家昂赛。
第一轮,第一题,删除二叉树每个结点的值只会是0或1,输入root node,要求删除所有子孙结点都是0的结点。比如 1 1
0 要删除左子树返回root, 0 返回原来的root就可以,因为左子树的后代不全为0
1
第二题,给一个数组,返回 是否数组里面存在三个数字,作为三角形三条边可以组成一个三角形。followup,一共能组成几个三角形。

第二轮,给一个先递增后递减的数组和一个target,问数组里是否能找到这个target。find peak element变种。楼主当时秒了这个题后面试官马上给了下一题,但是面试结束后仔细想了一下发现代码里少判断了几个条件,导致并不能跑出正确结果,不知道面试官为什么没有指出问题反而在时间充裕的情况下直接给了下一题。郁闷。。。。第二个题就是一个打印log的系统 给了两个api:start(requestid), end(requestid), 每条log的型式:%requestid started at %startTime, run了多长时间。就相当于call end时要实时打印出log,但是log要求按starttime升序排列,所以如果有request开始晚但是结束早,它要等之前还没结束的request结束之后才能被打印出来。楼主想法就是hashmap和双向链表(存starttime,endtime开始设成一个负数),每次call start就会往链表插入一项,但是call end时 如果不是头结点 就只更新一下endtime,如果是头结点就删除,然后while下一项endtime是valid,删除下一项,把所有log都打出来。

第三轮面试官迟到了半个小时,一度以为这轮要面不到了,感谢lunch interviewer国人小哥一直在会议室陪我聊天,最后面试官慌慌张张赶过来了。。第一题里寇伞吴酒,followup 类似map with expriration,因为想省空间,实现O(1) 的cleanup清除掉已经可以被print的message。做完这个题之后面试官一看还有十分钟 就又出了人找自行车那题。楼主勉强用剩下的时间把bfs框架写出来了。

第四轮上来先implement trie 然后实现getAllWord返回root下面存的所有单词,第二问getRandomWord,每个单词都要equal chance,楼主想法是在trienode里加一个field记录这个node之后一共存了多少个单词,然后递归,每一层都用水塘抽烟决定下一层访问哪个node。

最后提醒一下大家(也是提醒楼主自己)一定要写完代码自己手跑个testcase,说不定写代码的时候一马虎漏掉一些条件没有check导致代码不能work,就很遗憾

请问第四轮是这个意思吗?比如以下trie, b node之后存了两个单词,c node之后存了3个单词,所以如果当前在a, 有2/5的几率选择走b, 有3/5的几率选择走c

        a
   b      c 
d  e   f  g h   

是这个意思 zuzuzu

哈哈哈哈 水塘抽样!

lz太牛,SDE和DS一起找,实在佩服

伞吴酒是log rate limiter, 楼主能否稍微详细讲讲第三轮follow up思路,感谢