近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 8159|回复: 73
收起左侧

G家实习电面挂经

[复制链接] |试试Instant~ |关注本帖
wnbaicai 发表于 2016-11-9 04:40:56 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Fail其他

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
基础差了再加上人生首面就给了G家,跪得很正常(安慰自己)

第一面应该是个阿三妹子,口音不重,先叫简短的介绍下自己,然后出题
1.不用写码,说思路,给两个list,一个表示前一天公司的员工,一个表示今天的公司员工,如何找到哪些是新来的哪些人走了?
比如昨天的list是{a, b, c}, 今天的list是{b, c, d},表示今天a员工走了,新来了d员工,问你使用什么数据结构,分析run time。
2.给你一个数字的list,然后给一个target,求所有由list里面数字组合成的小于target的数,数字可以重复使用
比如list是{3,7,8},target是8700,然后3, 8, 7 ... 333, 888, ... , 8377 等等都算
这题典型的backtrack,我一开始没想到,想到了长度小于target的肯定是,然后一直在想长度等于target怎么弄,最后写了个helper函数才想到了backtrack,然后对面表示对的,这才是正确的方法,然后没时间实现了T_T,最后问了下有什么想问的就结束了-google 1point3acres

第二面直接从mountain view打过的来的,是个小哥,但是声音不太清楚,期间叫他重复了好多东西....稍微确认了下我的背景就直接出题了
给一个String和一个字典,找字典里面长度最长的能由String里面删去某些字符后组成的单词-google 1point3acres
比如S = abpcplea, Dict = {ale, apple, monkey, plea}, 就返回apple. from: 1point3acres.com/bbs
我用了暴力法,对所有单词查询一次,最后返回最长的,然后小哥要求分析run time, 分析完后优化, 我先说可以把dict按长度排序,从最长的开始找,他要求继续,我想了半天不知道,他给了点提示,说要是S特别长怎么办?然后我又说可以记录S里面每个字符的位置,然后每次找下一个位置,他表示如果重复字符太多这办法不行,然后到时间了他问我有啥想问的没就结束了。


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

评分

4

查看全部评分

zzgzzm 发表于 2016-11-10 03:41:23 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
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. Waral 鍗氬鏈夋洿澶氭枃绔,

  3. // r: current matched prefix represented by TrieNode
  4. // start: position in s matched so far
  5. // len/maxLen: max/length of subsequence matched so far
  6. void dfs(Node* r, size_t start, int len, int& maxLen) {
  7.   if (!r || start == -1) return;
  8.   if (r->isWord) maxLen = max(maxLen, len);
  9.   for (char c = 'a'; c <= 'z'; c++) dfs(r->next[c - 'a'], pos[c][start], len + 1, maxLen);
  10. }

  11. int longestSubsequence(string& s, const vector<string>& dict) {
  12.   int ls = s.length(); if (!ls) return 0;
  13.   // generate pos map index: time O(ls)
  14.   for (char c = 'a'; c <= 'z'; c++) {
  15.     for (int start = 0; start < ls; ) {
  16.       int i = start; while (i < ls && s[i] != c) i++;
  17.       for (int j = start; j <= min(i, ls-1); j++) pos[c][j] = i<ls? i : -1;
  18.       start = i + 1;
  19.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.   }   
  21.   int maxLen = 0; dfs(createTrie(dict, ls), 0, 0, maxLen);
  22.   return maxLen;
  23. }

  24. // Create trie for words with length <= maxDepth
  25. // Time: O(L) L= total word length in dictionary with length <= maxDepth. From 1point 3acres bbs
  26. Node* createTrie(const vector<string>& dict, int maxDepth) {
  27.   auto r = new Node(), cur = r; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.   for (const auto& w : dict) {
  29.     if (w.length() > maxDepth) continue;
  30.     for (char c : w) {
  31.       int i = c - 'a';
  32.       if (!cur->next[i]) cur->next[i] = new Node();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  33.       cur = cur->next[i];
  34.     }
  35.     cur->isWord = true;
  36.   }
  37.   return r;
  38. }
复制代码
回复 支持 4 反对 0

使用道具 举报

jacky841102 发表于 2016-11-29 17:27:16 | 显示全部楼层
关注一亩三分地微博:
Warald
用了trie合并字典中的prefix
预处理S,把a~z在S中的index按照先后次序存进charList中
idxs表示目前各个char的index
每选一个char需要把其他所有char的index增加使得其他的char index都比所选char index的还大.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 1point3acres.com/bbs
另外写了brute force的方法,和test的method
跑出来brute force的比较快啊。。。
10 个 case 的数据
trie time: 5.45
brute time: 0.08
trie time: 3.86
brute time: 0.05. from: 1point3acres.com/bbs
trie time: 3.96
brute time: 0.05
trie time: 5.05. Waral 鍗氬鏈夋洿澶氭枃绔,
brute time: 0.07
trie time: 3.90. From 1point 3acres bbs
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
单位是秒
. 1point3acres.com/bbs
  1. from random import choice, randint
  2. import string
  3. from time import time

  4. def dictSearch(S, words):
  5.     global ans
  6.     trie = Trie()
  7. . visit 1point3acres.com for more.
  8.     for word in words:
  9.         trie.insert(word). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  10. -google 1point3acres
  11.     charList = [list() for _ in range(26)]. 鍥磋鎴戜滑@1point 3 acres
  12.     for i, c in enumerate(S):
  13.         charList[ord(c) - ord('a')].append(i)

  14.     idxs = [0] * 26. visit 1point3acres.com for more.
  15.     ans = ""

  16.     def dfs(node, cur_idxs):
  17.         global ans. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.         if node is None:
  19.             return
  20.         if node.isword and len(node.word) > len(ans):
  21.             ans = node.word-google 1point3acres
  22.         for i, child in enumerate(node.childs):
  23.             if child and cur_idxs[i] < len(charList[i]):
  24.                 idxs = list(cur_idxs)
  25.                 for j in range(26):
  26.                     while idxs[j] < len(charList[j]) and charList[j][idxs[j]] < charList[i][idxs[i]]:
  27.                         idxs[j] += 1
  28.                 dfs(child, idxs). visit 1point3acres.com for more.
  29.         return

  30.     dfs(trie.root, idxs)
  31.     return ans
  32. . Waral 鍗氬鏈夋洿澶氭枃绔,
  33. class Trie:.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.     def __init__(self):
  35.         self.root = TrieNode()

  36.     def insert(self, word):
  37.         i = self.root. From 1point 3acres bbs
  38.         for c in word:
  39.             t = ord(c) - ord('a')
  40.             if i.childs[t] == None:. from: 1point3acres.com/bbs
  41.                 i.childs[t] = TrieNode()
  42.             i = i.childs[t]
  43.         i.isword = True
  44.         i.word = word

  45. class TrieNode:
  46.     def __init__(self):
    . 1point 3acres 璁哄潧
  47.         self.isword = False
  48.         self.childs = [None] * 26
  49.         self.word = None. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


  50. def brute(S, words):
  51.     ans = ''
  52.     for word in words:
  53.         next = 0
  54.         for c in word:. more info on 1point3acres.com
  55.             next = S.find(c, next). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  56.             if next == -1:
  57.                 break
  58.         else:
  59.             if len(word) > len(ans):. 1point 3acres 璁哄潧
  60.                 ans = word
  61.     return ans

  62. def test():
  63.     for i in range(10):
  64.         S = ''.join(choice(string.ascii_lowercase) for _ in range(randint(500,1000)))
  65.         words = [''.join(choice(string.ascii_lowercase) for _ in range(randint(10,20))) for _ in range(randint(10000, 20000))]
  66.         words.sort()

  67.         now = time()
  68. . 1point 3acres 璁哄潧
  69.         trie_result = dictSearch(S, words)
  70.         print('trie time: %.2f' % (time() - now))
  71. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  72.         now = time()
  73.         brute_result = brute(S, words)
  74.         print('brute time: %.2f' % (time() - now))

  75.         assert(trie_result == brute_result)
复制代码
回复 支持 2 反对 0

使用道具 举报

zzgzzm 发表于 2016-11-9 12:00:47 | 显示全部楼层
第二面:这个题等价于求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)) {}. Waral 鍗氬鏈夋洿澶氭枃绔,
  5. };
  6. . 鍥磋鎴戜滑@1point 3 acres
  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. void postOrder(Node* r, vector<Node*>& post) {
  20.   if (!r) return;. more info on 1point3acres.com
  21.   for (auto x:r->next) postOrder(x, post);
  22.   post.push_back(r);
  23. }

  24. int longestSubsequence(string& s, const vector<string>& dict) {
  25.   int len = s.length(); if (!len) return 0;
  26.   auto r = createTrie(dict);   
  27.   vector<Node*> post; postOrder(r, post);
  28.   // dp[i][x] = length of longest subsequence of s.substr(i)
  29.   // found in dictionary defined by trie node x
  30.   auto dp = vector<unordered_map<Node*, int>>(len+1); // default all 0's
  31.   for (int i = len - 1; i >= 0; --i) {
  32.     for (auto x:post) {
  33.       auto y = x->next[s[i] - 'a'];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  34.       if (y) dp[i][x] = dp[i+1][y]? (dp[i+1][y]+1) : y->isWord;
  35.       dp[i][x] = max(dp[i][x], dp[i+1][x]);
  36.     }  
  37.   }
  38.   return dp[0][r];
  39. }
复制代码
回复 支持 2 反对 0

使用道具 举报

dokolo 发表于 2016-11-10 11:08:41 | 显示全部楼层
可以把所有的words做成一个Trie,再用S来搜索。
大概写一下思路。

  1. def search(i, node):
  2.     if i >= len(S):
  3.         return . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  4.     result += node.isWord
  5.     if S[i] in node.children:
  6.         search(i+1, node.children.pop(S[i]). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  7.     search(i+1, node)
复制代码

回复 支持 0 反对 1

使用道具 举报

delly224 发表于 2016-11-9 05:21:14 | 显示全部楼层
请问楼主多久知道的结果?
回复 支持 反对

使用道具 举报

cookielee77 发表于 2016-11-9 06:42:27 | 显示全部楼层
请问第一题是用什么数据结构?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-9 06:52:25 | 显示全部楼层
cookielee77 发表于 2016-11-9 06:42
请问第一题是用什么数据结构?

用hashset 分別存两个list 就行了。时间O(m+n) one pass.
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-9 06:59:14 | 显示全部楼层
第2题 就是bfs input的词, 基本是word ladder的思路。. From 1point 3acres bbs
然后每bfs一个词,就在dict里面找,是不是在。

补充内容 (2016-11-9 07:05):
MARK一下,回家写代码。
回复 支持 反对

使用道具 举报

坨坨 发表于 2016-11-9 07:00:21 | 显示全部楼层
请问第二题list里的number是任意的么还是只是0-9?
回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-11-9 07:01:21 | 显示全部楼层
第1轮,第2题,就是combination sum的小变形,加个小于target就行了吧。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-11-9 07:05:44 | 显示全部楼层
感谢楼主的分享!~~  我在想第二题为什么lz的方法不行呢? 是不是用一个HashMap<Character, ArrayList<Integer>> 记录每个字符的位置 然后找下一个字符比这个大的index  array扫描的时间太长了? 是不是换成treeSet 用celling()取比这个大的最小的元素0.0 这样就是o(1)的查找了0.0  不知道这样想对不对~~
回复 支持 反对

使用道具 举报

Jasonyuan 发表于 2016-11-9 09:23:02 | 显示全部楼层
楼主你好,请问你的timeline大概是怎么样的呢,我被内推后3周了一直没消息
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-9 09:29:49 | 显示全部楼层
第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.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. . 鍥磋鎴戜滑@1point 3 acres
  7. vector<int> getNumbers(set<int>& digits, int target) { dfs(digits, 0, target); return res; }
复制代码

补充内容 (2016-11-9 09:37):
更正:若digits中没有0的话,最后把"res"中的0去掉。
回复 支持 反对

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:05:37 | 显示全部楼层
delly224 发表于 2016-11-9 05:21
请问楼主多久知道的结果?

结果两周内公布,自我感觉肯定跪了
回复 支持 反对

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:06:32 | 显示全部楼层
zzgzzm 发表于 2016-11-9 06:52
用hashset 分別存两个list 就行了。时间O(m+n) one pass.

恩,我也说的set
回复 支持 反对

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:09:42 | 显示全部楼层
坨坨 发表于 2016-11-9 07:00
请问第二题list里的number是任意的么还是只是0-9?

给的例子是0~9,这些条件都可以自己假定
回复 支持 反对

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:10:07 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-11-9 07:01
第1轮,第2题,就是combination sum的小变形,加个小于target就行了吧。

对,最后我说了这个思路她说是对的,但是没时间写了T_T
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:15:25 | 显示全部楼层
Jasonyuan 发表于 2016-11-9 09:23
楼主你好,请问你的timeline大概是怎么样的呢,我被内推后3周了一直没消息
.1point3acres缃
我是星期天找人推的然后星期一一早上就来了邮件叫做OA约电面,但并不是本人简历厉害,因为其他找的内推,校招还有海投的其他公司一个回复的都没,所以还是看运气?
回复 支持 反对

使用道具 举报

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

能麻烦给下recruiter邮箱吗,想问一下,一直没消息。。怕是被漏了
回复 支持 反对

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:26:45 | 显示全部楼层
zzgzzm 发表于 2016-11-9 12:00. 鍥磋鎴戜滑@1point 3 acres
第二面:这个题等价于求string s中的最长subsequence found in dictionary(注意是subsequence,不是substr ...
. 1point 3acres 璁哄潧
给跪了,我能说我扫了一遍没看懂么,等有空了再研究下...
回复 支持 反对

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:27:10 | 显示全部楼层
Jasonyuan 发表于 2016-11-9 12:16
能麻烦给下recruiter邮箱吗,想问一下,一直没消息。。怕是被漏了

发你站内信了
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-23 18:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表