一亩三分地论坛

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

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

Google 挂经

[复制链接] |试试Instant~ |关注本帖
liurudahai 发表于 2016-10-24 21:15:06 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
攒RP求OFFER,已经挂了6个ONSITE了

第一轮,亚裔女,第一问,让你还原一个所有元素全部是数字的数组,会给你一些数组中元素的顺序,比如给你三个数组[1,2,4], [3,4], [2,3],可以还原出原数组是1,2,3,4,5,就是用topology sort,秒了, 第二问让你求一个整数的质因数,我就用分解质因数的方法,从2开始一个一个质因数除,第三问让你说常见的数据结构的优点缺点,这里面有两个问题,第一个是我说到图的优点的时候,好像有些纠结,我说图用来寻找路径什么的很方便,比如用BFS, DFS,面试官好像不太满意,说我没说到图的最好的地方,第二个是她问我有些地方我们想用QUEUE而不用数组的,我说那就是有些地方你希望MAINTAIN一个先进先出的ORDER,但不想随机ACCESS元素吧,她好像也不是太满意
第二轮,三哥男,第一题求两个链表的交点,LC原题,第二题,N个SORTED LIST,要求写一个ITERATOR,按顺序输出元素,也秒了

第三轮,白男,感觉跪在这一轮了,题目是首先给你一个字符串数组,比如bobcat, cat, tag, age之类,然后client给你发一个字符流,SERVICE端每次收到一个字符,当有字符串组合HIT到给定的PATTERN的时候,RETURN HIT到的PATTERN数,不然RETURN 0,比如CLIENT给的字符流是bobcatage,然后在依次收到b, o, b, c, a的时候都return 0,到t的时候return 2,因为之前的字符流match了bobcat和cat,然后到a的时候又是0,到接下来的g的时候return 1因为match了tag,之后e的时候还是return 1,因为match 了age,我一开始说我在service端cache要字符串流,被否决,后来提出的是建立一个trie,然后每轮用一个set记录当前正在处理的trie node,他也不是很满意,一直问我能不能用一种更加fancy的way去用trie,纠结了几十分钟,没想出来,然后他看没时间了,要我用我上面说的第二种方法写CODE,当时时间很紧,又出了BUG,还没看出来,直觉感觉他会FAIL我了,然后留了5分钟问问题,我直接就问他我怎么样,他说他不能告诉我正确答案,但是确实没想到我没看出来那个BUG,然后我问他GOOGLE组的事情,他拒绝回答这个问题,反而让我如果没准备好,就不要急,说我现在有工作,不用急着去另一个公司,感觉就是要FAIL我了

第四轮,白男,比赛分组问题,假设有n个足球俱乐部队参加一个淘汰赛,淘汰赛要两两分组对战,然后国际上一般有规矩,同一个国家的球队一般要尽可能晚的相遇,然后让我分组,比如八个队比赛,国家A,有A1, A2两个队,国家B有B1, B2, B3三个队,其他三个队分别属于国家C,D,E,那么分组要是这样的,(A1, B1), (C, B2), (D, B3), (A2, E),这样可以保证,A国家两个队在决赛才会相遇,B国家有2个队最多在半决赛相遇,这两个队和剩下那个队最多在决赛相遇,这一轮也做的很纠结,不过最后应该是做出来而且写完代码了。之前因为做的很纠结,他帮我简化了一下,假设n是2的幂,后来follow up,如果n不是2的幂要如何改.1point3acres缃

第五轮,三哥男,给你一个binary tree,要你求binary tree所有的数和,要求给出iteration和recursion两种方法,我iteration用的层次遍历,recursion相加的实质其实就是后序遍历,然后他就问我iteration能不能相加的顺序和recursion一样,那我说就用iteration后序遍历,做完之后他说顺序还是有点不一样的,但也没说什么。因为我后序遍历用了个stack,他问我能不能不用额外空间,我说我记得有个morris后序遍历是不用空间的,但是我在学校学的,现在不太记得了。然后他说他不关心我知道什么知识,只关心我能不能解决这个问题。然后我在那弄了半天,凭借着自己的印象把莫里斯遍历弄出来了,但是他质疑我这不是O(n)解法,又跟他解释了半天为什么是o(n),然后他说不管你用什么方法,你这加法都是一个一个NODE加,但如果我给你N个独立运作的NODE,你能不能PARRALLEL的相加,这个题感觉他是不是想问多线程,但和我之前面的一个GROUPON的面经有点像,我就套用了那个方法,首先叶节点把自己的值发给父节点,最后汇总到根节点那求和,然后根节点再反向把值发给整个数,他认可我这个方法是parallel的,但是我因为里面用到node index判断NODE的父节点和子节点的INDEX,他说我这个如果不是完全二叉树就不能用了,我说父节点不是有到子节点的LINK么,直接用那个就好了,至于怎么从子节点到父节点,如果有一个PAERENT LINK就没问题了。他也认可。

上上周四面的,周五收到HR电话说会送HC,上周五收到电话说挂了,感觉第四轮做的有点纠结但最后还是作出来了,1,2,5轮都是秒了的,第三轮确实没太做好,很可能是第三轮那个人给了我很低的分,google bar还是很高,现在面试的BAR感觉都很高,有一轮没面好就不行,找工作之路漫漫啊

评分

4

查看全部评分

本帖被以下淘专辑推荐:

yxyxyx 发表于 2016-10-24 23:00:56 | 显示全部楼层
不知道第三轮不能用cache是啥意思,是指不能开一个长度为单词数组里最长单词的string来存字母流里的字母吗?如果可以开这么一个字符串的话,那第三轮可不可以把所有的单词数组里的单词按照从尾到头的方法去建一个trietree,然后每新来一个字母就从头搜一遍trietree?
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-10-24 23:18:09 | 显示全部楼层
yxyxyx 发表于 2016-10-24 23:00
不知道第三轮不能用cache是啥意思,是指不能开一个长度为单词数组里最长单词的string来存字母流里的字母吗 ...

不可以用你这个方法,我表述可能不一样,但你说的起始就是我第一次提出的方法,他非常不喜欢
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-25 01:01:30 | 显示全部楼层
liurudahai 发表于 2016-10-24 11:18
不可以用你这个方法,我表述可能不一样,但你说的起始就是我第一次提出的方法,他非常不喜欢

hmm。那我能想到的也就是和你一样的了,维护一个set存储当前遍历到的node。

不知道他说的fancy的trie到底指的是啥- -
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-10-25 02:16:23 | 显示全部楼层
yxyxyx 发表于 2016-10-25 01:01
hmm。那我能想到的也就是和你一样的了,维护一个set存储当前遍历到的node。

不知道他说的fancy的trie ...
. 鍥磋鎴戜滑@1point 3 acres
回忆了一下,当时有个提示,他问我能不能用state change来做这题,当时一听很懵逼,不知道他要什么,我就想了用hashmap来记录一个字符下面可能的字符,但是最终这个approach没有走通,但是他说他很喜欢我这个idea,就算没走通也会给我一些points,不知道是不是和这个有关
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-25 02:43:29 | 显示全部楼层
liurudahai 发表于 2016-10-24 14:16
回忆了一下,当时有个提示,他问我能不能用state change来做这题,当时一听很懵逼,不知道他要什么,我就 ...

啊哈!我搜索了一下,大概是这个算法?
https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

意思就是用finite automata去模拟trie然后做string matching

补充内容 (2016-10-24 15:02):
不过如果真的问的是这个那也真的是太难了。。。。。
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-25 03:49:40 | 显示全部楼层
写了一个刚刚学习了的Aho-Corasick algorithm的第三轮的实现。。。patpat lz,这题onsite问实在是太难了。。。

  1. #include <iostream>. Waral 鍗氬鏈夋洿澶氭枃绔,
  2. #include <unordered_map>
  3. #include <string>. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4. #include <vector>
  5. #include <queue>
  6. using namespace std;
  7. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  8. // Use Aho-Corasick algorithm for dictionary string searching.鏈枃鍘熷垱鑷1point3acres璁哄潧
  9. // Refer to WIKI: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

  10. struct TrieNode {
  11.   bool is_end;
  12.   unordered_map<char, TrieNode*> char_map;
  13.   TrieNode *prefix_node;
  14.   TrieNode() {
  15.     is_end = false;
  16.     prefix_node = NULL;
  17.   }
  18. };


  19. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20. TrieNode* find_prefix_node(TrieNode *node, char child_char, TrieNode *head) {. more info on 1point3acres.com
  21.   while(node != NULL) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.     if (node->char_map.count(child_char) != 0) {
  23.       return node->char_map[child_char];
  24.     }
  25.     node = node->prefix_node;. 1point3acres.com/bbs
  26.   }
  27.   return head;. 1point 3acres 璁哄潧
  28. }

  29. void build_Aho_Corasick_Trie(TrieNode *head) {
  30.   queue<TrieNode*> q;
  31.   q.push(head);
  32.   while(!q.empty()) {
  33.     int cur_size = q.size();.1point3acres缃
  34.     for (int i = 0; i < cur_size; i++) {
  35.       TrieNode *cur_node = q.front();
  36.       q.pop();
  37.       // find all prefix node for the its child nodes
  38.       for (auto iter = cur_node->char_map.begin(); iter != cur_node->char_map.end(); iter++) {
  39.         char child_char = iter->first;
  40.         iter->second->prefix_node = find_prefix_node(cur_node->prefix_node, child_char, head);-google 1point3acres
  41.         q.push(iter->second);
  42.       }
  43.     }-google 1point3acres
  44.   }
  45. }

  46. void build_TrieTree(TrieNode *head, vector<string> &dict) {
  47.   
  48.   for (int i = 0; i < dict.size(); i++) {
  49.     TrieNode *node = head;
  50.     for (int pos = 0; pos < (int)dict[i].size(); pos++) {
  51.       char cur_char = dict[i][pos];
  52.       if (node->char_map.count(cur_char) == 0) {
  53.         node->char_map[cur_char] = new TrieNode();
  54.       }
  55.       node = node->char_map[cur_char];. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  56.     }
  57.     node->is_end = true;
  58.   }. Waral 鍗氬鏈夋洿澶氭枃绔,
  59.   build_Aho_Corasick_Trie(head);
  60. }


  61. int find_string_Aho_Corasick_Trie(TrieNode *&node, char cur_char, TrieNode *head) {
  62.   int result = 0;
  63.   while (node != NULL) {
  64.     if (node->char_map.count(cur_char) == 0) {
  65.       node = node->prefix_node;
  66.       continue;
  67.     } else {
  68.       node = node->char_map[cur_char];
  69.       TrieNode *suffix = node;
  70.       while(suffix != head) {
  71.         if (suffix->is_end) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  72.           result++;
  73.         }
  74.         suffix = suffix->prefix_node;
  75.       }
  76.       break;
  77.     }
  78.   }. From 1point 3acres bbs
  79.   if (node == NULL) node = head;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  80.   return result;
  81. }


  82. void find_string(string s, TrieNode *head) {
  83.   TrieNode *node = head;
  84.   if (node->is_end) {
  85.     cout << "" << endl;
  86.   }
  87.   for (int pos = 0; pos < s.size(); pos++) {
  88.     char cur_char = s[pos];
  89.     int cur_result = find_string_Aho_Corasick_Trie(node, cur_char, head);
  90.     cout << cur_result << endl;
  91.   }. From 1point 3acres bbs
  92. }

  93.    
  94.     -google 1point3acres
  95. // To execute C++, please define "int main()"
  96. int main() {. Waral 鍗氬鏈夋洿澶氭枃绔,
  97.   vector<string> dict = {"he", "she", "hers", "his", "her"};
  98.   string target = "ahishers";. from: 1point3acres.com/bbs
  99.   TrieNode *head = new TrieNode();
  100.   build_TrieTree(head, dict);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  101.   find_string(target, head);
  102.   
  103.   return 0;. 鍥磋鎴戜滑@1point 3 acres
  104. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  105. .鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码
跑了一下结果是对的。。。
回复 支持 反对

使用道具 举报

haveto 发表于 2016-10-25 04:11:20 | 显示全部楼层
yxyxyx 发表于 2016-10-25 03:49
写了一个刚刚学习了的Aho-Corasick algorithm的第三轮的实现。。。patpat lz,这题onsite问实在是太难了。 ...

这个用来match sequence专门的算法之一! 拜托 这不就是跟考KMP似的 知道就知道 不知道就不知道了 也不算是general的思路吧。。。坑爹啊 pat pat
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-25 04:56:19 | 显示全部楼层
问下楼主第四轮是怎么做的?谢谢
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-10-25 06:10:55 | 显示全部楼层
同求第四轮解法,谢谢楼主,另外第三问这个要求有点过分,google明确说过不提倡考察这种知道就是知道,不知道就是不知道的解法
回复 支持 反对

使用道具 举报

rinto 发表于 2016-10-25 10:38:23 | 显示全部楼层
楼主,第三题可不可以这样做:你维持一个TrieNode的list,表示所有当前能走到的TrieNode;每次进来一个新的字母,你就重建一次这个list:遍历上一个字母的List,如果一个node没有这个字母的子node,就把它扔了;如果有这个字母的子node,你就放到新的list里面,特别的,如果这个子node是一个单词的结尾,就把要return的value+1;然后把当前字母当作第一个字母走到的node加到list里面。
以楼主的例子,当走到bobca的时候,list里面应该是bobca的a的match的TrieNode和ca的a的match的TrieNode,当t进来之后,list里面是bobcat的t的match和cat的match, return 2;再往下走这个list里面的node就都该扔了


补充内容 (2016-10-25 10:41):
呃,没仔细看,lz就是这个方法。。。。好吧,忽略我把
回复 支持 反对

使用道具 举报

rinto 发表于 2016-10-25 11:20:36 | 显示全部楼层
第四轮感觉可以用segment tree,每个结点存底下还有几个空的结点,从队伍最多的国家开始,尽可能均匀的分到下面的结点去,并且update那些结点的值。
回复 支持 反对

使用道具 举报

xintai404 发表于 2016-10-25 11:54:53 | 显示全部楼层
第四题,可以divide and conquer吧,首先一个国家有多个队伍的平均分配到左右赛区,然后在任意放只属于一个国家的队伍,然后分别处理左半区和右半区
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-10-26 01:25:19 | 显示全部楼层
xintai404 发表于 2016-10-25 11:54
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴第四题,可以divide and conquer吧,首先一个国家有多个队伍的平均分配到左右赛区,然后在任意放只属于一个 ...

对的,我最后就是这么做的
回复 支持 反对

使用道具 举报

joytostuffratio 发表于 2016-10-26 02:48:57 | 显示全部楼层
momo lz...白人面试官说话略伤人。。。
回复 支持 反对

使用道具 举报

zmyvszk 发表于 2016-10-26 06:19:26 | 显示全部楼层
求楼主第四题的代码!感谢!!
回复 支持 反对

使用道具 举报

mallow123 发表于 2016-10-26 12:08:30 | 显示全部楼层
楼主,同求第四轮的代码。
第三轮那白人好rude,我要是碰上这号人,肯定被打击的下轮发挥不好。
回复 支持 反对

使用道具 举报

suiyuan2009 发表于 2016-10-26 20:21:18 | 显示全部楼层
比赛那题,不是幂次怎么办
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 22:28:44 | 显示全部楼层
suiyuan2009 发表于 2016-10-26 20:21
比赛那题,不是幂次怎么办

我觉得这个比赛的组织可以用binary tree来表示。root表示冠军,leaf表示每个参赛队伍,每一层都是比赛的一轮。对于任意N个队伍的话应该用同时是full and complete binary tree. 这样有可能有的的队伍(不是最深层的leaf)会被对待成“种子队”而直接跳过第一轮。
-google 1point3acres
补充内容 (2016-10-26 22:32):
然后问题就转化成:给定每个leaf的value,如何安排可以让相同value的leaves的lowest common ancestor (LCA)的深度尽量小。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 22:50:58 | 显示全部楼层
比赛那题,如何定义一个可量化的metric来衡量一个安排整体是不是最好呢?(感觉这个比较主观啊)
如果这个比赛的组织用binary tree来表示。root表示冠军,leaf表示每个参赛队伍,每一层都是比赛的一轮。对于任意N个队伍的话应该用同时是full and complete binary tree. 这样有可能有的的队伍(不是最深层的leaf)会被对待成“种子队”而直接跳过第一轮。那么我想到一个用相同国家队伍两两的lowest common ancestor (LCA)的深度总和最小化是一个合理的标准:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
给定multiset<char> teams (teams from same country have same char value), 求一个teams的排列,使得以下函数最小化:
Y := Sum_{i<j} Depth(LCA(i, j)), 其中Sum对所有i < j pair 并且teams[i] == teams[j] (来自同一国家)求和。 但这个作为interview问题看起来似乎挺难,或者我弄复杂了,关键是怎么定义“让相同国家队伍尽量晚相遇”最优呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 09:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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