《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 9222|回复: 73
收起左侧

G家实习电面挂经

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

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

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

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

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,最后问了下有什么想问的就结束了. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

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|的单词总长;. Waral 鍗氬鏈夋洿澶氭枃绔,
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
  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. -google 1point3acres
  12. int longestSubsequence(string& s, const vector<string>& dict) {
  13.   int ls = s.length(); if (!ls) return 0;
  14.   // generate pos map index: time O(ls)
  15.   for (char c = 'a'; c <= 'z'; c++) {
  16.     for (int start = 0; start < ls; ) {. 鍥磋鎴戜滑@1point 3 acres
  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;.1point3acres缃
  19.       start = i + 1;
  20.     }
  21.   }   
  22.   int maxLen = 0; dfs(createTrie(dict, ls), 0, 0, maxLen);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23.   return maxLen;
  24. }. 1point3acres.com/bbs

  25. . 1point3acres.com/bbs
  26. // Create trie for words with length <= maxDepth
  27. // Time: O(L) L= total word length in dictionary with length <= maxDepth
  28. Node* createTrie(const vector<string>& dict, int maxDepth) {
  29.   auto r = new Node(), cur = r;
  30.   for (const auto& w : dict) {. 1point 3acres 璁哄潧
  31.     if (w.length() > maxDepth) continue;
  32.     for (char c : w) {
  33.       int i = c - 'a';
  34.       if (!cur->next[i]) cur->next[i] = new Node();
  35.       cur = cur->next[i];
  36.     }. Waral 鍗氬鏈夋洿澶氭枃绔,
  37.     cur->isWord = true;-google 1point3acres
  38.   }
  39.   return r;
  40. }
复制代码
回复 支持 4 反对 0

使用道具 举报

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

另外写了brute force的方法,和test的method
跑出来brute force的比较快啊。。。
10 个 case 的数据-google 1point3acres
trie time: 5.45
brute time: 0.08. 1point 3acres 璁哄潧
trie time: 3.86. Waral 鍗氬鏈夋洿澶氭枃绔,
brute time: 0.05
trie time: 3.96.1point3acres缃
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. visit 1point3acres.com for more.
  2. import string
  3. from time import time
  4. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  5. def dictSearch(S, words):
  6.     global ans. From 1point 3acres bbs
  7.     trie = Trie()
  8. . Waral 鍗氬鏈夋洿澶氭枃绔,
  9.     for word in words:
  10.         trie.insert(word)

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

  14.     idxs = [0] * 26
  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):. visit 1point3acres.com for more.
  21.             ans = node.word. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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)
  29.         return

  30.     dfs(trie.root, idxs)
  31.     return ans. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  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()
  41.             i = i.childs[t]
  42.         i.isword = True
  43.         i.word = word

  44. class TrieNode:
  45.     def __init__(self):.1point3acres缃
  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:. 1point3acres.com/bbs
  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):-google 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)))
  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)). from: 1point3acres.com/bbs
  69. . From 1point 3acres bbs
  70.         now = time()
  71.         brute_result = brute(S, words)
  72.         print('brute time: %.2f' % (time() - now))

  73.         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
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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) {. from: 1point3acres.com/bbs
  9.     for (char c:s) {
  10.       int i = c - 'a';  . from: 1point3acres.com/bbs
  11.       if (!cur->next[i]) cur->next[i] = new Node();
  12.       cur = cur->next[i];
  13.     }
  14.     cur->isWord = 1;
  15.   }.1point3acres缃
  16.   return r;
  17. }. Waral 鍗氬鏈夋洿澶氭枃绔,

  18. void postOrder(Node* r, vector<Node*>& post) {. visit 1point3acres.com for more.
  19.   if (!r) return;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.   for (auto x:r->next) postOrder(x, post);
  21.   post.push_back(r);
  22. }

  23. int longestSubsequence(string& s, const vector<string>& dict) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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). From 1point 3acres bbs
  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) {. visit 1point3acres.com for more.
  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]);. From 1point 3acres bbs
  35.     }  
  36.   }
  37.   return dp[0][r];
  38. }
复制代码
回复 支持 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. more info on 1point3acres.com
  5.     if S[i] in node.children:
  6.         search(i+1, node.children.pop(S[i])-google 1point3acres
  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
请问第一题是用什么数据结构?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
用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的数字长度。. more info on 1point3acres.com
  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. 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就行了吧。

. 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. Waral 鍗氬鏈夋洿澶氭枃绔,
我是星期天找人推的然后星期一一早上就来了邮件叫做OA约电面,但并不是本人简历厉害,因为其他找的内推, ...

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

使用道具 举报

 楼主| wnbaicai 发表于 2016-11-9 12:26:45 | 显示全部楼层
zzgzzm 发表于 2016-11-9 12:00
第二面:这个题等价于求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-11-25 01:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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