一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3116|回复: 73
收起左侧

G家实习电面挂经

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
基础差了再加上人生首面就给了G家,跪得很正常(安慰自己)
-google 1point3acres
第一面应该是个阿三妹子,口音不重,先叫简短的介绍下自己,然后出题
1.不用写码,说思路,给两个list,一个表示前一天公司的员工,一个表示今天的公司员工,如何找到哪些是新来的哪些人走了?-google 1point3acres
比如昨天的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 等等都算. 1point 3acres 璁哄潧
这题典型的backtrack,我一开始没想到,想到了长度小于target的肯定是,然后一直在想长度等于target怎么弄,最后写了个helper函数才想到了backtrack,然后对面表示对的,这才是正确的方法,然后没时间实现了T_T,最后问了下有什么想问的就结束了

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


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

评分

4

查看全部评分

zzgzzm 发表于 2016-11-10 03:41:23 | 显示全部楼层
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. 1point 3acres 璁哄潧
  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);
    . visit 1point3acres.com for more.
  11. }

  12. int longestSubsequence(string& s, const vector<string>& dict) {
  13.   int ls = s.length(); if (!ls) return 0;. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.   // generate pos map index: time O(ls)
  15.   for (char c = 'a'; c <= 'z'; c++) {
  16.     for (int start = 0; start < ls; ) {
  17.       int i = start; while (i < ls && s[i] != c) i++;
  18.       for (int j = start; j <= min(i, ls-1); j++) pos[c][j] = i<ls? i : -1;
  19.       start = i + 1;. 1point 3acres 璁哄潧
  20.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.   }    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.   int maxLen = 0; dfs(createTrie(dict, ls), 0, 0, maxLen);
  23.   return maxLen;
  24. }

  25. // Create trie for words with length <= maxDepth
  26. // Time: O(L) L= total word length in dictionary with length <= maxDepth
  27. Node* createTrie(const vector<string>& dict, int maxDepth) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.   auto r = new Node(), cur = r;
  29.   for (const auto& w : dict) {.1point3acres缃
  30.     if (w.length() > maxDepth) continue;
  31.     for (char c : w) {
  32.       int i = c - 'a';. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  33.       if (!cur->next[i]) cur->next[i] = new Node();
  34.       cur = cur->next[i];. more info on 1point3acres.com
  35.     }
  36.     cur->isWord = true;
  37.   }. from: 1point3acres.com/bbs
  38.   return r;
  39. }
复制代码
回复 支持 2 反对 0

使用道具 举报

jacky841102 发表于 7 天前 | 显示全部楼层
用了trie合并字典中的prefix
预处理S,把a~z在S中的index按照先后次序存进charList中. from: 1point3acres.com/bbs
idxs表示目前各个char的index
每选一个char需要把其他所有char的index增加使得其他的char index都比所选char index的还大

另外写了brute force的方法,和test的method
跑出来brute force的比较快啊。。。
10 个 case 的数据
trie time: 5.45.鏈枃鍘熷垱鑷1point3acres璁哄潧
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. 鍥磋鎴戜滑@1point 3 acres
trie time: 3.90
brute time: 0.05
trie time: 4.13
brute time: 0.05. From 1point 3acres bbs
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):. 1point 3acres 璁哄潧
  5.     global ans
  6.     trie = Trie()

  7.     for word in words:
  8.         trie.insert(word). from: 1point3acres.com/bbs

  9.     charList = [list() for _ in range(26)]
  10.     for i, c in enumerate(S):
  11.         charList[ord(c) - ord('a')].append(i)

  12.     idxs = [0] * 26
  13.     ans = ""

  14.     def dfs(node, cur_idxs):
  15.         global ans
  16.         if node is None:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  17.             return
  18.         if node.isword and len(node.word) > len(ans):
  19.             ans = node.word
  20.         for i, child in enumerate(node.childs):
  21.             if child and cur_idxs[i] < len(charList[i]):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  22.                 idxs = list(cur_idxs)
  23.                 for j in range(26):
  24.                     while idxs[j] < len(charList[j]) and charList[j][idxs[j]] < charList[i][idxs[i]]:
  25.                         idxs[j] += 1
  26.                 dfs(child, idxs). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.         return

  28.     dfs(trie.root, idxs)
  29.     return ans

  30. class Trie:.1point3acres缃
  31.     def __init__(self):
  32.         self.root = TrieNode()

  33.     def insert(self, word):
  34.         i = self.root
  35.         for c in word:
  36.             t = ord(c) - ord('a')
  37.             if i.childs[t] == None:
  38.                 i.childs[t] = TrieNode()
  39.             i = i.childs[t]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  40.         i.isword = True
  41.         i.word = word

  42. class TrieNode:
  43.     def __init__(self):
  44.         self.isword = False
  45.         self.childs = [None] * 26
  46.         self.word = None

  47. .1point3acres缃
  48. def brute(S, words):
  49.     ans = ''-google 1point3acres
  50.     for word in words:
  51.         next = 0
  52.         for c in word:
  53.             next = S.find(c, next)
  54.             if next == -1:
  55.                 break
  56.         else:
  57.             if len(word) > len(ans):
  58.                 ans = word
  59.     return ans

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

  65.         now = time()

  66.         trie_result = dictSearch(S, words)
  67.         print('trie time: %.2f' % (time() - now)). 鍥磋鎴戜滑@1point 3 acres

  68.         now = time(). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  69.         brute_result = brute(S, words)
  70.         print('brute time: %.2f' % (time() - now))

  71.         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=字典单词长度总和). From 1point 3acres bbs
  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. Node* createTrie(const vector<string>& dict) {. more info on 1point3acres.com
  7.   auto r = new Node(), cur = r;
  8.   for (const auto& s:dict) {
  9.     for (char c:s) {
  10.       int i = c - 'a';  
  11.       if (!cur->next[i]) cur->next[i] = new Node();
  12.       cur = cur->next[i];
  13.     }
  14.     cur->isWord = 1;
  15.   }
  16.   return r;
  17. }

  18. void postOrder(Node* r, vector<Node*>& post) {
  19.   if (!r) return;. From 1point 3acres bbs
  20.   for (auto x:r->next) postOrder(x, post);
  21.   post.push_back(r);
  22. }

  23. int longestSubsequence(string& s, const vector<string>& dict) {
  24.   int len = s.length(); if (!len) return 0;
  25.   auto r = createTrie(dict);    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  26.   vector<Node*> post; postOrder(r, post);
  27.   // dp[i][x] = length of longest subsequence of s.substr(i)
  28.   // found in dictionary defined by trie node x
  29.   auto dp = vector<unordered_map<Node*, int>>(len+1); // default all 0's
  30.   for (int i = len - 1; i >= 0; --i) {
  31.     for (auto x:post) {
  32.       auto y = x->next[s[i] - 'a'];
  33.       if (y) dp[i][x] = dp[i+1][y]? (dp[i+1][y]+1) : y->isWord;
  34.       dp[i][x] = max(dp[i][x], dp[i+1][x]);
  35.     }  . Waral 鍗氬鏈夋洿澶氭枃绔,
  36.   }
  37.   return dp[0][r];
  38. }
复制代码
回复 支持 2 反对 0

使用道具 举报

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的思路。
然后每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
  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. . more info on 1point3acres.com
  7. vector<int> getNumbers(set<int>& digits, int target) { dfs(digits, 0, target); return res; }. 1point3acres.com/bbs
复制代码

补充内容 (2016-11-9 09:37):.1point3acres缃
更正:若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周了一直没消息

我是星期天找人推的然后星期一一早上就来了邮件叫做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
第二面:这个题等价于求string s中的最长subsequence found in dictionary(注意是subsequence,不是substr ...

给跪了,我能说我扫了一遍没看懂么,等有空了再研究下...
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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