狗家西雅图onsite挂经，不懂为什么，求大家帮忙分析一下

楼主12月6号在西雅图新的slu office面试的onsite， 4轮techinal，一轮behavior，今天收到recruiter电话说面挂了，实在想不懂为什么，大家帮忙分析一下
第一轮，美国人，问了一道autocomplete的简化版本，就是搜索一个prefix，然后自动suggest出出现频率最高的词。比如说搜索fa, 有两个单词facebook, fakebook, 然后facebook被搜索的次数是200， fakebook被搜索的次数是10的话，我们就返回facebook. input是所有单词和他们被搜索的次数，我分析比较了hashtable和trie的方法，跟面试官进行了讨论。最后用了hashtable来保存一个词可能出现的所有prefix作为key，value是这个词和频率的一个pair，加入单词的时候来看频率是否更高，更高的话就更新这个value pair。
这一轮开始的时候迟到了15分钟，因为slu是新office，到的时候进错办公楼了，后来好不容易找到front desk，跟面试官道歉并且说明了理由，这一轮并没有来得及问followup

第二轮，印度人，问了一道N-ary Tree longest consecutive的length, 可以从任何一点开始到它的child，我使用dfs来做的，用一个pos在parameter里面track，每一次的recursion如果child的val=cur的val+1，就会加一，否则就从1重新来看，同时更新一个global value maxlen。题目完成的很顺利，面试官加了一个follow up是有n个stack，然后每个stack上面会有不同数量的硬币，每个硬币的值也可能不同，然后让你取出总共N个硬币，可以取出来最大的值是什么。我给他讲了一下如何combination的思路，最后也没有时间写了，他告诉我you are on the right track 之类的

第三轮，美国人，给出已知的target string(比如说OKGOOG)，然后有一个string stream(ABCDOKGOOKGOOG), 每次call 一个api叫做 bool isAddCharValid(char c)每次添加一个char的时候判断是否包含target。上述例子的话只有call到最后一个G的话才返回true。我的思路就是一个siliding window，用一个cur string来表示当前有可能符合的string，如果input char不在target内，我把cur清空，否则的话cur+=c, 如果cur的长度等于target，判断是否cur==target, 然后把cur在pos 0的char去掉。面试官表示这个算法seems to work，写完代码后，他问了follow up是有多个target string的话应该怎么做，我也提出了相应的解法并没有写代码，思路也得到了面试官的认可

中午吃饭===不得不说谷歌slu新建的楼真的很赞，有一个休息室有一面水母墙，我被深深地吸引了=v=

第四轮，黑人经理，问的是lc jump game，我之前没做到过原题， 但是当时迅速做出了最基本的dp解法，dp 来表示当前index 是否可以到达，然后通过step来更新未来有可能到达的dp，这个算法是O(n^2),  然后他让我优化到O(n),这个是一个greedy算法，我当时没有立刻想到，他提示我有没有什么data structure可以帮助解决，我就觉得很奇怪，不知道这个题为啥还需要data stucture，我给了他一些优化，但是确实没有优化到O(n). 但是他最后告诉我excellent之类的

第五轮(behavior)，越南人，问了一些常规问题比如deadline之前有两个task，只能完成一个改怎么办，还有和别人有冲突的时候改怎么办，还有完成任务时没有达到预期该怎么办。

面完之后感觉还挺有信心的，没想到今天一个晴空霹雳。。看来是连hc都没有送，感觉灵魂都被抽离了。。。楼主已经第二次面狗家onsite了，第一次面的时候确实感觉自己发挥不好，可是这第二次，感觉题目都会做而且面试官当时的反馈都不错啊，出了这样的结果真的很意外。今天问recruiter feedback，她对我说面试官和我交流都很愉快，然后不好的地方说是data stucture和algorithm掌握的不好，我问了她是哪几轮表现不好，第一轮可能迟到了有些影响，她却告诉我说前两轮非常supportive我。那看来就是后三轮不是很理想了，我感觉更疑惑了，求大家帮忙分析开导，谢谢！顺便求一下大米过冬！！

第三轮用kmp可行
第四轮这种线段状态，可以用类似bfs思想，扫一遍吧

其实说实话，我觉得你面的也不差，居然HC都不送那是真的算不好了，搞得我也有点虚。。 第四题我看明白了，其实也是找最远点，A[i]+i,唯一就是必须在reachable的范围内找，这个范围是随着最远点而更新的。所以相当于是一个for loop,但是i<j，且j=max(i+A[i],j)， j就是到i可能到的最远点。 这题他说data structure可能是引导你往最优解想得一个过渡，我其实也不太清楚。但是理论上应该希望你那轮做两题吧

Gary92 发表于 2019-12-12 14:00
第三题应该用trie吧，特别是多个target string,更是必须要trie了。第四题只需要从0开始，把能要达到的地方 ...

第三题给出的input不是一个string，而是一个stringstream，不是一个固定的string，还会有可能有其他char加入，就相当于每次call isAddCharValid(A)->false, isAddCharValid(B)->false, 都要加一个char上去，我觉得还是需要一个string来保持历史记录的？ 第四题我也是这个思路，题目给的nums[i]是在index i可以跳最远的路程，然后for 每一个index i，我们都要mark一遍它可以从1跳到最远的点，所以runtime 还是O(n^2)

最后顺便求一波大米过冬，加米不会扣你积分的!

第三轮是用reversed trie

应该就是第三轮和第四轮吧

第三轮做法应该是kmp吧，或者用rolling hash

补充内容 (2019-12-11 21:57):
多个target就是ac自动机了

看起来应该是第三轮的algo答得不好和第四轮的优化不太好挂的

第三题应该用trie吧，特别是多个target string,更是必须要trie了。第四题只需要从0开始，把能要达到的地方存在unordered_set就行，然后最大存O(n)个，running time O(n)

journalfbus 发表于 2019-12-12 14:17
第三题给出的input不是一个string，而是一个stringstream，不是一个固定的string，还会有可能有其他char ...

你把target存在trie里面就行了，按reverse来存，然后stringstream你直接从结尾往头看有没有match的就行了。 stringstream你肯定得存，就看问题是啥了，理论上来说，你只需要存max target.size()就够了。第四题我其实也不确定，因为好像看了下最优解是直接greedy了，可能我也忽略了什么constraints，既然能constant space,那什么data structure好像都不需要了