刚才面的,遇见国人姐姐,本来被fb拒的低落了挺长时间,狗家就尽力而为听天由命了,没想到碰见个国人姐姐。真的感觉姐姐出的题是故意放水啊,最后磕磕绊绊在提示下做出来,希望没让国人姐姐失望。题目:
Given a string s and a word w, determine whether w is a subsequence of s
这个题一开始以为是连续的substring,后来告诉不是就O(n)过了,简单
主要是follow up是高能
Given a string s and a dict of words, find the longest word in D that is a subsequence of s
这个其实也简单,就是暴力解遍历一下两遍就搞定
再follow up,更简便的方法
就这卡住了,一开始想错了用trie tree,但讨论了得有10分钟吧,发现根本解不了,因为不是substring的,就傻了。
后来提示下,逐渐想到用hashmap,但key value又想错了,最后姐姐提示用hashmap character int[],我就知道了,到这就下面全答出来了,把每个char的index存一下,然后维持maxlen,curlen啥的。
感觉国人姐姐真的是想放我水,其实这题的followup 以前还和同学讨论过,当时就傻了没想起来这个,然后她一提示就想起来,希望没让国人姐姐失望。
原本都对狗家不抱什么希望了,但现在又有点希望了,这已经是加面了,不知道最后结果是什么,但无论怎么样都特别感谢国人姐姐!面完还给发个短信感谢一下。。
过两天把狗家整理的面经再发到地里吧。祝大家都有offer~~~