推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

G家实习电面挂经

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

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

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

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

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

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

第二面直接从mountain view打过的来的,是个小哥,但是声音不太清楚,期间叫他重复了好多东西....稍微确认了下我的背景就直接出题了
给一个String和一个字典,找字典里面长度最长的能由String里面删去某些字符后组成的单词
比如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|成正比)。. 1point3acres.com/bbs
为了避免重复prefix matching,还是应该将字典中所有长度不超过|s|的单词建立一个Trie,pre-calculate 每个字母在s.substr(j)中的初始位置,然后DFS在Trie中寻找最长matching.. From 1point 3acres bbs
时间复杂度:建立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
    .1point3acres缃

  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. visit 1point3acres.com for more.
  6. void dfs(Node* r, size_t start, int len, int& maxLen) {-google 1point3acres
  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);. more info on 1point3acres.com
  10. }
  11. .1point3acres缃
  12. int longestSubsequence(string& s, const vector<string>& dict) {. visit 1point3acres.com for more.
  13.   int ls = s.length(); if (!ls) return 0;. From 1point 3acres bbs
  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++;-google 1point3acres
  18.       for (int j = start; j <= min(i, ls-1); j++) pos[c][j] = i<ls? i : -1;
  19.       start = i + 1;
  20.     }. 鍥磋鎴戜滑@1point 3 acres
  21.   }   
  22.   int maxLen = 0; dfs(createTrie(dict, ls), 0, 0, maxLen);. 鍥磋鎴戜滑@1point 3 acres
  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) {
  28.   auto r = new Node(), cur = r;
  29.   for (const auto& w : dict) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.     if (w.length() > maxDepth) continue;. more info on 1point3acres.com
  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];
  35.     }
  36.     cur->isWord = true;
  37.   }-google 1point3acres
  38.   return r;
  39. }
复制代码
回复 支持 4 反对 0

使用道具 举报

jacky841102 发表于 2016-11-29 17:27:16 | 显示全部楼层
用了trie合并字典中的prefix
预处理S,把a~z在S中的index按照先后次序存进charList中
idxs表示目前各个char的index
每选一个char需要把其他所有char的index增加使得其他的char index都比所选char index的还大
. 1point3acres.com/bbs
另外写了brute force的方法,和test的method
跑出来brute force的比较快啊。。。. 鍥磋鎴戜滑@1point 3 acres
10 个 case 的数据. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
trie time: 5.45. from: 1point3acres.com/bbs
brute time: 0.08 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
trie time: 3.86. visit 1point3acres.com for more.
brute time: 0.05. 1point 3acres 璁哄潧
trie time: 3.96
brute time: 0.05
trie time: 5.05
brute time: 0.07.1point3acres缃
trie time: 3.90
brute time: 0.05
trie time: 4.13
brute time: 0.05
trie time: 3.64. more info on 1point3acres.com
brute time: 0.05
trie time: 5.44
brute time: 0.07. 1point 3acres 璁哄潧
trie time: 3.43
brute time: 0.04
trie time: 4.07
brute time: 0.05. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
单位是秒

  1. from random import choice, randint-google 1point3acres
  2. import string
  3. from time import time

  4. def dictSearch(S, words):
  5.     global ans. 鍥磋鎴戜滑@1point 3 acres
  6.     trie = Trie()
  7. . 1point3acres.com/bbs
  8.     for word in words:. 鍥磋鎴戜滑@1point 3 acres
  9.         trie.insert(word)

  10.     charList = [list() for _ in range(26)]
  11.     for i, c in enumerate(S):
  12.         charList[ord(c) - ord('a')].append(i). from: 1point3acres.com/bbs

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

  15.     def dfs(node, cur_idxs):
  16.         global ans
  17.         if node is None:
  18.             return. from: 1point3acres.com/bbs
  19.         if node.isword and len(node.word) > len(ans):
  20.             ans = node.word
  21.         for i, child in enumerate(node.childs):.1point3acres缃
  22.             if child and cur_idxs[i] < len(charList[i]):. 1point3acres.com/bbs
  23.                 idxs = list(cur_idxs)
  24.                 for j in range(26):
  25.                     while idxs[j] < len(charList[j]) and charList[j][idxs[j]] < charList[i][idxs[i]]:
  26.                         idxs[j] += 1
  27.                 dfs(child, idxs)
  28.         return. visit 1point3acres.com for more.

  29.     dfs(trie.root, idxs)
  30.     return ans
  31. . 鍥磋鎴戜滑@1point 3 acres
  32. class Trie:
  33.     def __init__(self):
  34.         self.root = TrieNode()

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

  44. class TrieNode:
  45.     def __init__(self):
  46.         self.isword = False
  47.         self.childs = [None] * 26
  48.         self.word = None 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


  49. def brute(S, words):
  50.     ans = ''.鐣欏璁哄潧-涓浜-涓夊垎鍦
  51.     for word in words:
  52.         next = 0
  53.         for c in word:.鐣欏璁哄潧-涓浜-涓夊垎鍦
  54.             next = S.find(c, next)
  55.             if next == -1:
  56.                 break
  57.         else:
  58.             if len(word) > len(ans):.1point3acres缃
  59.                 ans = word
  60.     return ans

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

  66.         now = time()

  67.         trie_result = dictSearch(S, words)
  68.         print('trie time: %.2f' % (time() - now))

  69.         now = time()
  70.         brute_result = brute(S, words)
  71.         print('brute time: %.2f' % (time() - now))

  72.         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);.1point3acres缃
就是说在寻找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-google 1point3acres
  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) {
  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;
  20.   for (auto x:r->next) postOrder(x, post);
  21.   post.push_back(r);. more info on 1point3acres.com
  22. }

  23. int longestSubsequence(string& s, const vector<string>& dict) {
  24.   int len = s.length(); if (!len) return 0;
  25.   auto r = createTrie(dict);   
  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'];.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.     }  . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.   }
  37.   return dp[0][r];
  38. }
复制代码
回复 支持 2 反对 0

使用道具 举报

dokolo 发表于 2016-11-10 11:08:41 | 显示全部楼层
可以把所有的words做成一个Trie,再用S来搜索。
大概写一下思路。
. visit 1point3acres.com for more.
  1. def search(i, node):
  2.     if i >= len(S):
  3.         return .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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的思路。
然后每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. }. visit 1point3acres.com for more.

  6. vector<int> getNumbers(set<int>& digits, int target) { dfs(digits, 0, target); return res; }
复制代码
-google 1point3acres
补充内容 (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就行了吧。
. visit 1point3acres.com for more.
对,最后我说了这个思路她说是对的,但是没时间写了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邮箱吗,想问一下,一直没消息。。怕是被漏了

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 04:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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