首先说一下自己的时间线，
八月初的时候Google hr reach out, 之后就进行了一轮intro call，随后做完了oa直接skip电面，安排onsite。
09/11 去onsite
09/18 hr说feedback收集完成，09/21送hc
09/21收到电话说hc通过，进行下一步。
下面简单聊一下onsite四轮题目。
第一轮是哥senior的白人大叔，很友好。题目是，给一个字符串（如“cadogt”)，判断是否存在两个单词，例子里就是“cat”，“dog”，并且这两个单词合并之后能得到这个串。合并规则和merge sort一样，这里就是 c<d a<d o>g。
第二轮，一个白人面试官，看起来有点像nerd。。。给定一个（timestanmp， val）二元组的序列（类似于股票在不同时间的价格），实现三个操作，min/max/most recent。其中二元组可以为（timestamp， None），这意味着删除这个timestamp之前的所有值。
第三轮是一个烙馍，题目利寇特饵跋耙，区别是生成一个单词所有的abbreviattion。follow up是给一个target单词和一个单词表，找到这个target的，不在单词表的，最短abbreviation。
第四轮是一个白人老哥，题目是在电影院有一排长度为n的座位，起始状态有的有人有的没人，新来一个人，为他安排座位，要求离两边人越远越好。follow up是如何为k个人安排座位。用堆即可，edge case就是开头和结尾的空位，注意解决。
祝大家找工顺利，早日拿到心仪的offer。
就是暴力法列出所有的结果，对所有结果判断1）两个单词都有效 2）两个单词合并可以得到原来的那个单词。复杂度是O(2**n)。可以用trie剪枝，暂时没想到复杂度更低的做法。
第一题的意思是cat中间要按顺序切开吗？ 还是只要里面还有catdog这几个字母就可以？
感谢分享
最后一轮的follow up的heap解法是类似巴武武吗 加k个人的话就是O(klogn)时间？
对的，之前没做那道题，看了下一毛一样
好的，你发我吧
第一轮: dfs+trie
第二轮: bst
第四轮：优先队列维护最长连续空位。
问下标准解法是什么？
第二轮我用的堆，其他都一样
用堆的话得用三个堆？ 然后用堆怎么实现删除指定time stamp之前的数据呢？
lazy deletion，用一个dict或者map记录已经被删除的