转发: 狗家加面遇见国人姐姐

刚才面的,遇见国人姐姐,本来被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~~~

希望狗狗家收了楼主!

为什么我遇到的国人姐姐给我出dp

我也希望借你啊,但挂了也没什么,已经习惯了。。这是一种多么痛的领悟

amazon这大车也没坐上,fb挂的心痛,看来这次命有点好了。。。但也不抱太大希望,毕竟是Google

祝福楼主!多拿offer

这题频率是真高啊

我看以前面经讨论是用trie做的,还真没考虑过hashmap,一会再仔细想想

感谢分享,请问LZ是对String s建Hashmap然后再dictionary一一比较吗

十分感谢, 楼主附件里的题目都是实习题目吗? 还是包括全职的? 谢谢

都是实习,没看全职