G家实习电面挂经

基础差了再加上人生首面就给了G家，跪得很正常（安慰自己）

第一面应该是个阿三妹子，口音不重，先叫简短的介绍下自己，然后出题
1.不用写码，说思路，给两个list，一个表示前一天公司的员工，一个表示今天的公司员工，如何找到哪些是新来的哪些人走了？
比如昨天的list是{a, b, c}， 今天的list是{b, c, d}，表示今天a员工走了，新来了d员工，问你使用什么数据结构，分析run time。
2.给你一个数字的list，然后给一个target，求所有由list里面数字组合成的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

然后到时间了他问我有啥想问的没就结束了。


G家面试果然没套路，真心要求能力强，自己确实弱了挂了也正常

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. }
    

复制代码

用了trie合并字典中的prefix
预处理S，把a~z在S中的index按照先后次序存进charList中
idxs表示目前各个char的index
每选一个char需要把其他所有char的index增加使得其他的char index都比所选char index的还大

另外写了brute force的方法，和test的method
跑出来brute force的比较快啊。。。
10 个 case 的数据
trie time: 5.45
brute time: 0.08
trie time: 3.86
brute time: 0.05
trie time: 3.96
brute time: 0.05
trie time: 5.05
brute time: 0.07
trie time: 3.90
brute time: 0.05
trie time: 4.13
brute time: 0.05
trie time: 3.64
brute time: 0.05
trie time: 5.44
brute time: 0.07
trie time: 3.43
brute time: 0.04
trie time: 4.07
brute time: 0.05
单位是秒

1. from random import choice, randint
   
2. import string
   
3. from time import time
   
4. 
   
5. def dictSearch(S, words):
   
6.     global ans
   
7.     trie = Trie()
   
8. 
   
9.     for word in words:
   
10.         trie.insert(word)
    
11. 
    
12.     charList = [list() for _ in range(26)]
    
13.     for i, c in enumerate(S):
    
14.         charList[ord(c) - ord('a')].append(i)
    
15. 
    
16.     idxs = [0] * 26
    
17.     ans = ""
    
18. 
    
19.     def dfs(node, cur_idxs):
    
20.         global ans
    
21.         if node is None:
    
22.             return
    
23.         if node.isword and len(node.word) > len(ans):
    
24.             ans = node.word
    
25.         for i, child in enumerate(node.childs):
    
26.             if child and cur_idxs[i] < len(charList[i]):
    
27.                 idxs = list(cur_idxs)
    
28.                 for j in range(26):
    
29.                     while idxs[j] < len(charList[j]) and charList[j][idxs[j]] < charList[i][idxs[i]]:
    
30.                         idxs[j] += 1
    
31.                 dfs(child, idxs)
    
32.         return
    
33. 
    
34.     dfs(trie.root, idxs)
    
35.     return ans
    
36. 
    
37. class Trie:
    
38.     def __init__(self):
    
39.         self.root = TrieNode()
    
40. 
    
41.     def insert(self, word):
    
42.         i = self.root
    
43.         for c in word:
    
44.             t = ord(c) - ord('a')
    
45.             if i.childs[t] == None:
    
46.                 i.childs[t] = TrieNode()
    
47.             i = i.childs[t]
    
48.         i.isword = True
    
49.         i.word = word
    
50. 
    
51. class TrieNode:
    
52.     def __init__(self):
    
53.         self.isword = False
    
54.         self.childs = [None] * 26
    
55.         self.word = None
    
56. 
    
57. 
    
58. def brute(S, words):
    
59.     ans = ''
    
60.     for word in words:
    
61.         next = 0
    
62.         for c in word:
    
63.             next = S.find(c, next)
    
64.             if next == -1:
    
65.                 break
    
66.         else:
    
67.             if len(word) > len(ans):
    
68.                 ans = word
    
69.     return ans
    
70. 
    
71. def test():
    
72.     for i in range(10):
    
73.         S = ''.join(choice(string.ascii_lowercase) for _ in range(randint(500,1000)))
    
74.         words = [''.join(choice(string.ascii_lowercase) for _ in range(randint(10,20))) for _ in range(randint(10000, 20000))]
    
75.         words.sort()
    
76. 
    
77.         now = time()
    
78. 
    
79.         trie_result = dictSearch(S, words)
    
80.         print('trie time: %.2f' % (time() - now))
    
81. 
    
82.         now = time()
    
83.         brute_result = brute(S, words)
    
84.         print('brute time: %.2f' % (time() - now))
    
85. 
    
86.         assert(trie_result == brute_result)

复制代码

第二面：这个题等价于求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. }

复制代码

请问楼主多久知道的结果？

请问第一题是用什么数据结构？

cookielee77 发表于 2016-11-9 06:42
请问第一题是用什么数据结构？

用hashset 分別存两个list 就行了。时间O(m+n) one pass.

第2题 就是bfs input的词， 基本是word ladder的思路。
然后每bfs一个词，就在dict里面找，是不是在。

补充内容 (2016-11-9 07:05):
MARK一下，回家写代码。

请问第二题list里的number是任意的么还是只是0-9？

第1轮，第2题，就是combination sum的小变形，加个小于target就行了吧。

感谢楼主的分享！~~  我在想第二题为什么lz的方法不行呢？ 是不是用一个HashMap<Character, ArrayList<Integer>> 记录每个字符的位置 然后找下一个字符比这个大的index  array扫描的时间太长了？ 是不是换成treeSet 用celling()取比这个大的最小的元素0.0 这样就是o(1)的查找了0.0  不知道这样想对不对~~

楼主你好，请问你的timeline大概是怎么样的呢，我被内推后3周了一直没消息

第2题好像是G家的高频题了。应该还有个限制就是除了0之外以0为首的不能算吧。
用Trie的思想，但不用真正建立Trie，做 DFS：next number = current number*10 + digit。时间复杂度 O(M^N)，M=digits个数，N=target的数字长度。

1. vector<int> res; // result to hold all valid numbers
   
2. void dfs(set<int>& digits, int cur, int target) {
   
3.   if (cur >= target) return; res.push_back(cur);
   
4.   for (int i:digits) {  if (int next = cur*10+i > 0) dfs(digits, next, target); }
   
5. }
   
6. 
   
7. vector<int> getNumbers(set<int>& digits, int target) { dfs(digits, 0, target); return res; }
   

复制代码

补充内容 (2016-11-9 09:37):
更正：若digits中没有0的话，最后把"res"中的0去掉。