G家实习电面挂经

谢谢楼主！

看了下楼主的经理感觉我基本上跪了，下周三面好紧张。碰到第二轮这种题目就毫无办法了。。。。

wnbaicai 发表于 2016-11-9 12:26
给跪了，我能说我扫了一遍没看懂么，等有空了再研究下...

假设s="abcdefgh", dict ="abd","cegh","ea". 那么要匹配s的最长subsequence 只有2种情况：包括首字母”a"或不包括。若不包括，那就在原字典中匹配”bcdefgh"的最长subsequence   。若包括，那么只看字典中首字母为”a"的单词并去掉该字母，也就是用“新”字典｛“bd"}去匹配”bcdefgh"的最长subsequence。这个trie 的引入完全是为了如何快速的得到“新”字典。理论上完全可以用loop over string list来完成，但时间复杂度会相当高，而且会不停地建新的字典占空间。这种在tree node和线性index 二维DP我是头一次用，感觉应该很对这个字典问题的路。不确定是否还有其他捷径，但感觉时间复杂度应该已经优化了。

zzgzzm 发表于 2016-11-9 13:21
假设s="abcdefgh", dict ="abd","cegh","ea". 那么要匹配s的最长subsequence 只有2种情况：包括首字母”a ...

Trie 实际上就是用Node* (integral type)去代替了原始的复杂字典结构vector <string>，并利用child node关系才得以实现在字典维度的DP。DP的边界条件就是空字典匹配任何string 都是0，任何字典匹配空string都是0.

为什么感觉你们讨论的那么复杂呀，我写了一下判断subsequence的函数。什么fancy structure都没用。O(|S|)的时间就行了，S是input String. 然后再按lz的思路给字典按长度排序，然后总时间是O(|S|* |D|)。 |D|表示字典的size，也就是单词数。

/* return true when S could be trimmed to get v, false otherwise
   Time Complexity: O(|S|); Space: in space */
Boolean stringContains(String S, String v){
        // not topological sort,
        // deal with corner case
        If (S==null | v==null) return false;
        If (v.length() == 0) return true;
// If (S.length() == 0) return false;
If (v.length() > S.length()) return false;


// Go through each char in v
Int indexM = -1;
For (int i=0; i<v.length(); i++){
        indexM = S.indexOf(v.charAt(i), indexM+1);
        if(indexM < 0)
                Return false;
        // taking care of boundary condition
        if(indexM == S.length()-1 && i < v.length() - 1)
                Return false;
}
Return true;
}

oldwhite 发表于 2016-11-9 14:00
为什么感觉你们讨论的那么复杂呀，我写了一下判断subsequence的函数。什么fancy structure都没用。O(|S|)的 ...

...这是正解了。忽略我的trie 吧，我居然将subsequence match 的算法想成是O(M*N)的（那个应该是看match 了多少次吧），所以用了trie. .....纯娱乐吧

oldwhite 发表于 2016-11-9 14:00
为什么感觉你们讨论的那么复杂呀，我写了一下判断subsequence的函数。什么fancy structure都没用。O(|S|)的 ...

这不就是楼主的方法吗...貌似面官觉得复杂度太高?

谢谢楼主的面经，我也是首面G家。。下周就要面了。。。同基础薄弱。。。只求好运吧！希望你也能有好运！

同打星际，同面google实习

oldwhite 发表于 2016-11-9 14:00
为什么感觉你们讨论的那么复杂呀，我写了一下判断subsequence的函数。什么fancy structure都没用。O(|S|)的 ...

即使用O(|s|)时间判断字典中每个单词w是否是s的sunsequence，那么总时间O(|s|*|D|)也会有很多浪费的地方。例如当字典中2个单词有公用prefix的时候，这时公共的prefix只需要在s中查找一次，所以这个O(|s|*|D|)的是个很大的上界（与|s|成正比）。
为了避免重复prefix matching，还是应该将字典中所有长度不超过|s|的单词建立一个Trie，pre-calculate 每个字母在s.substr(j)中的初始位置，然后DFS在Trie中寻找最长matching.
时间复杂度：建立Trie = O(L), L=字典中所有长度不超过|s|的单词总长；
pre-calculate 每个字母在s.substr(j)中的初始位置=O(|s|);
DFS: O(Trie node个数) <= O(L)
总复杂度 = O(|s| + L). 这个比O(|s|*|D|)是小很多的，尤其是|s|很大而字典单词并不长的时候。

1. // pos[c][i]: position of first occurrence of c in s.substr(i)
   
2. unordered_map<char, vector<size_t>> pos; // default -1 if not found
   
3. 
   
4. // r: current matched prefix represented by TrieNode
   
5. // start: position in s matched so far
   
6. // len/maxLen: max/length of subsequence matched so far
   
7. void dfs(Node* r, size_t start, int len, int& maxLen) {
   
8.   if (!r || start == -1) return;
   
9.   if (r->isWord) maxLen = max(maxLen, len);
   
10.   for (char c = 'a'; c <= 'z'; c++) dfs(r->next[c - 'a'], pos[c][start], len + 1, maxLen);
    
11. }
    
12. 
    
13. int longestSubsequence(string& s, const vector<string>& dict) {
    
14.   int ls = s.length(); if (!ls) return 0;
    
15.   // generate pos map index: time O(ls)
    
16.   for (char c = 'a'; c <= 'z'; c++) {
    
17.     for (int start = 0; start < ls; ) {
    
18.       int i = start; while (i < ls && s[i] != c) i++;
    
19.       for (int j = start; j <= min(i, ls-1); j++) pos[c][j] = i<ls? i : -1;
    
20.       start = i + 1;
    
21.     }
    
22.   }   
    
23.   int maxLen = 0; dfs(createTrie(dict, ls), 0, 0, maxLen);
    
24.   return maxLen;
    
25. }
    
26. 
    
27. // Create trie for words with length <= maxDepth
    
28. // Time: O(L) L= total word length in dictionary with length <= maxDepth
    
29. Node* createTrie(const vector<string>& dict, int maxDepth) {
    
30.   auto r = new Node(), cur = r;
    
31.   for (const auto& w : dict) {
    
32.     if (w.length() > maxDepth) continue;
    
33.     for (char c : w) {
    
34.       int i = c - 'a';
    
35.       if (!cur->next[i]) cur->next[i] = new Node();
    
36.       cur = cur->next[i];
    
37.     }
    
38.     cur->isWord = true;
    
39.   }
    
40.   return r;
    
41. }
    

复制代码