G家实习电面挂经

第二面：这个题等价于求string s中的最长subsequence found in dictionary（注意是subsequence，不是substring）。其实可对string s用DP。DP的一个维度就是从某 index=j 开始的子串s.subtr(j)对j = N, j>=0, j-- DP. 另一个维度是字典的prefix，每次匹配了一个字母时就只看字典中以该字母为首的单词，所以要用Trie建立字典。那么DP状态转移方程就容易写了：定义dp[j][TrieNode* x] := s.substr(j)的最长的能在Trie字典 x 找到的subsequence长度，那么：
dp[j][TrieNode* x] = max(dp[j+1][x], dp[j+1][x->next[s[j]-'a']]+1 or 0);
就是说在寻找s.substr(j)在字典 x的subsequence时，若不匹配char s[j]，那么就是在寻找s.substr(j+1)在字典 x的最长subsequence；否则就是匹配s[j]，然后在寻找s.substr(j+1)在字典 x->next[s[j]-'a']的最长subsequence，然后再根据结果和Trie node x->next[s[j]-'a']本身是否代表一个单词来决定+1或不加。最后要求的答案就是dp[0][root], root为原始字典的TrieNode root.
时间复杂度为O(Ns*Nt)，Ns=s.length(), Nt=TrieNode个数（这个比单词长度总和是可以远远得小的，因为合并了相同的prefix）。所以比用暴力比较s和每个单词的时间O(Ns*Nd)比还是快很多的 （Nd=字典单词长度总和）

1. struct Node { // Trie node for dictionary
   
2.     int isWord; // 1 if representing a word; otherwise 0
   
3.     vector<Node*> next;
   
4.     Node():isWord(0),next(vector<Node*>(26)) {}
   
5. };
   
6. 
   
7. Node* createTrie(const vector<string>& dict) {
   
8.   auto r = new Node(), cur = r;
   
9.   for (const auto& s:dict) {
   
10.     for (char c:s) {
    
11.       int i = c - 'a';  
    
12.       if (!cur->next[i]) cur->next[i] = new Node();
    
13.       cur = cur->next[i];
    
14.     }
    
15.     cur->isWord = 1;
    
16.   }
    
17.   return r;
    
18. }
    
19. 
    
20. void postOrder(Node* r, vector<Node*>& post) {
    
21.   if (!r) return;
    
22.   for (auto x:r->next) postOrder(x, post);
    
23.   post.push_back(r);
    
24. }
    
25. 
    
26. int longestSubsequence(string& s, const vector<string>& dict) {
    
27.   int len = s.length(); if (!len) return 0;
    
28.   auto r = createTrie(dict);   
    
29.   vector<Node*> post; postOrder(r, post);
    
30.   // dp[i][x] = length of longest subsequence of s.substr(i)
    
31.   // found in dictionary defined by trie node x
    
32.   auto dp = vector<unordered_map<Node*, int>>(len+1); // default all 0's
    
33.   for (int i = len - 1; i >= 0; --i) {
    
34.     for (auto x:post) {
    
35.       auto y = x->next[s[i] - 'a'];
    
36.       if (y) dp[i][x] = dp[i+1][y]? (dp[i+1][y]+1) : y->isWord;
    
37.       dp[i][x] = max(dp[i][x], dp[i+1][x]);
    
38.     }  
    
39.   }
    
40.   return dp[0][r];
    
41. }

复制代码

delly224 发表于 2016-11-9 05:21
请问楼主多久知道的结果？

结果两周内公布，自我感觉肯定跪了

zzgzzm 发表于 2016-11-9 06:52
用hashset 分別存两个list 就行了。时间O(m+n) one pass.

恩，我也说的set

坨坨 发表于 2016-11-9 07:00
请问第二题list里的number是任意的么还是只是0-9？

给的例子是0~9，这些条件都可以自己假定

xiaozhuxiaozhu 发表于 2016-11-9 07:01
第1轮，第2题，就是combination sum的小变形，加个小于target就行了吧。

对，最后我说了这个思路她说是对的，但是没时间写了T_T

何打发123 发表于 2016-11-9 07:05
感谢楼主的分享！~~  我在想第二题为什么lz的方法不行呢？ 是不是用一个HashMap 记录每个字符的位置 然后找 ...

对，就是记录字符的位置，但是不行，他给了个例子，比如 a: 0, 1, 2, 3, …, 1000000 然后b：999999，需要找aba的话找了b之后扫描a的时间还是太长

Jasonyuan 发表于 2016-11-9 09:23
楼主你好，请问你的timeline大概是怎么样的呢，我被内推后3周了一直没消息

我是星期天找人推的然后星期一一早上就来了邮件叫做OA约电面，但并不是本人简历厉害，因为其他找的内推，校招还有海投的其他公司一个回复的都没，所以还是看运气？

wnbaicai 发表于 2016-11-9 12:15
我是星期天找人推的然后星期一一早上就来了邮件叫做OA约电面，但并不是本人简历厉害，因为其他找的内推， ...

能麻烦给下recruiter邮箱吗，想问一下，一直没消息。。怕是被漏了

zzgzzm 发表于 2016-11-9 12:00
第二面：这个题等价于求string s中的最长subsequence found in dictionary（注意是subsequence，不是substr ...

给跪了，我能说我扫了一遍没看懂么，等有空了再研究下...

Jasonyuan 发表于 2016-11-9 12:16
能麻烦给下recruiter邮箱吗，想问一下，一直没消息。。怕是被漏了

发你站内信了