一亩三分地论坛

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

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

Google Onsite 挂经

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

2016(7-9月) 码农类 硕士 全职@Google - Other - Onsite |Failfresh grad应届毕业生

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

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

x
一个月前Google的oniste跪了,才想起来发面经。

1. 一个亚裔,找一个tree的所有的相等的subtree。我用post-order做的。但是我这个人心里素质比较差,面试之前就会紧张,睡不着觉。第二天整个人是飘的。一开始打算用iterative的方法后来脑子转不了写不下去了就换recursive。结果卡住了,我就是一个sb

2. 一个国人大哥,leetcode 422, 但是如果有一行长度不同就判false,不考虑末尾单词不一样的地方。然后是lintcode的coins in line iii,呵呵呵呵呵,我知道可以用dp做,但渣智商只能把搜索树画出来面试官说你都把搜索树画出来了就先用backtracking写吧,我就一边写他一边给我指bug。话说我至今都没有动手吧coin in line的那个系列的题写出来,懒癌晚期. from: 1point3acres.com/bbs
. from: 1point3acres.com/bbs
3. 一个美国人,一个html的tree然后用把body的文本内容连起来,我写了recursive的,问了时间复杂度, 又问用dfs的缺点是什么,然后换了bfs又问了一遍。再问了比较两个file相不相同,我说就指针扫吧,又问文件特别大怎么办,我说就规定一个size,一点点取。也是有小bug改过来了

4. 一个阿三吧, 问了一个data stream怎么统计字数的freq,我先说维持一个hashmap然后换了一个题,h-index,答完看时间还有好多就又回到统计字的题问如果是一个图怎么更新。。。一个做chromecast硬件的,我心想我还想吐槽你做的破烂玩意动不动就自己发热视频加载不出来得关掉散一会冷下来才能继续用。你这还没windows的重启大法好用呢。

电话收拒信,未来几年不想面了。等我把紧张睡不着觉的病治好再说吧。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

tjcd 发表于 2016-10-23 04:38:28 | 显示全部楼层
我跟LZ一样,面试前会紧张或兴奋到睡不着觉。。。
回复 支持 反对

使用道具 举报

mengmeng88717 发表于 2016-10-23 06:50:28 | 显示全部楼层
一个月才有消息?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-10-23 07:01:33 | 显示全部楼层
求问第一题,所有相等的subtree指什么?最大的相等的?如果两个subtree相等, 那么他们的所有子树也都对应相等啊
回复 支持 反对

使用道具 举报

joytostuffratio 发表于 2016-10-23 07:18:29 | 显示全部楼层
第三轮什么意思呢?没太明白题意。。。
回复 支持 反对

使用道具 举报

小雨嘀嗒 发表于 2016-10-24 00:48:22 | 显示全部楼层
没事楼主,我也这样,多面几次就好了
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-10-24 01:01:13 | 显示全部楼层
请问楼主求所有相等subtree,那么根据subtree的大小,可能会有很多个个集合,每个集合有大小相等的tree,题目是要求返回所有集合吗?
回复 支持 反对

使用道具 举报

 楼主| skye_luobopi 发表于 2016-10-24 01:35:31 | 显示全部楼层
WhatsFLAG 发表于 2016-10-24 01:01
请问楼主求所有相等subtree,那么根据subtree的大小,可能会有很多个个集合,每个集合有大小相等的tree,题 ...

对的。。。这不是一道经典面经题吗,你可以去翻一翻,好多人都考到了所以我没细讲
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-24 12:26:34 | 显示全部楼层
WhatsFLAG 发表于 2016-10-24 01:01
.鏈枃鍘熷垱鑷1point3acres璁哄潧请问楼主求所有相等subtree,那么根据subtree的大小,可能会有很多个个集合,每个集合有大小相等的tree,题 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个题可以用post-order traversal将以每个node作为root的subtree sequentialize 成一个可以容易比较的数据类型(我用的是string, 类似Leetcode 297)。这样就可以找出相同的subtrees了。
Note: 关键在于post-order traversal, 因为一个tree的sequentialized string可以很容易用其left/right subtrees推导(定义)出来。这种由subtree的attribute来推导tree的attribute的思路都可以由post-order traversal完成。(例如:求binary tree中max average value subtree)
  1. struct Node {
  2.   int val; Node* left, *right;
  3.   string seq; // sequentialized string of tree with this node as root
  4.   Node(int x):val(x),left(NULL),right(NULL),seq(""){}
  5. };

  6. // map from sequentialized string to subtree roots
  7. unordered_map<string, vector<Node*>> subtrees;
  8. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9. // set sequentialized string of a given node
  10. void setNodeSeq(Node* x) {
  11.   if (!x) return;
  12.   auto xl = x->left, xr = x->right;
  13.   x->seq = (xl? xl->seq : "N") + "," + (xr? xr->seq : "N") + "," + to_string(x->val);
  14.   subtrees[x->seq].push_back(x);
  15. }

  16. // set sequentialized strings of all nodes in the tree
  17. void setSeq(Node* r) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.   if (!r) return;
  19.   setSeq(r->left);
  20.   setSeq(r->right); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  21.   setNodeSeq(r);
  22. }

  23. vector<vector<Node*>> getSameSubtrees(Node* r) {. From 1point 3acres bbs
  24.   setSeq(r); vector<vector<Node*>> res;
  25.   for (auto& p:subtrees) { // collect same subtrees.1point3acres缃
  26.     if (p.second.size() > 1) res.push_back(p.second);
  27.   }
  28.   return res;
  29. }
复制代码

补充内容 (2016-10-24 12:35):
以上算法得到的是所有相同的subtrees(包括所有大小以及相同subtrees的相同子树)。时间O(N),空间O(N*logN) (N为tree的总node的个数)
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-10-25 05:00:45 | 显示全部楼层
zzgzzm 发表于 2016-10-24 12:26
这个题可以用post-order traversal将以每个node作为root的subtree sequentialize 成一个可以容易比较的数 ...

您好,用string代替一棵树这个思想很好,但是为什么特别的选用了postorder呢?您能不能给点提示啊

补充内容 (2016-10-25 05:03):
“Note: 关键在于post-order traversal, 因为一个tree的sequentialized string可以很容易用其left/right subtrees推导“这段有点不太理解啊

补充内容 (2016-10-25 05:27):
假设前序遍历,是不是也可以之访问一次各个子树保存的结果 来更新当前节点的结果呢?
回复 支持 反对

使用道具 举报

wsrrzxl 发表于 2016-10-25 05:20:50 | 显示全部楼层
preorder 应该也可以
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-10-25 05:43:43 | 显示全部楼层
wsrrzxl 发表于 2016-10-25 05:20
preorder 应该也可以

我的理解是,从样式上来看,后序遍历是自底向上的过程,的确可以减少重复计算;而先续遍历是自顶向下的过程,看起来似乎会增加重复计算的可能,但是实际运行的时候计算机还是自底向上来实现的,所以感觉先序遍历和后序遍历 在实质上是一样的,您认为我这么说对不对啊
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-25 09:22:19 | 显示全部楼层
WhatsFLAG 发表于 2016-10-25 05:00
您好,用string代替一棵树这个思想很好,但是为什么特别的选用了postorder呢?您能不能给点提示啊. 1point 3acres 璁哄潧

补充 ...

我又想了一下用pre-order traversal的可行性,对于这道题的确也是可以的。可以这样理解:post-order相当于DP,因为是从最简单的情况(leaf nodes)入手;pre-order相当于recursion. DP的特性是时间快但可能用更多的空间需要保存之前的结果;recursion若没有保存中间结果的话就很有可能造成O(2^N)时间复杂度(i.e. f(n)需要至少两个的recusive calls),但如果适当保存就没有问题了。
这道题为了找出所有相同的subtrees,每个node->seq无论用什么方法反正都必须最终保存下来,所以pre-order也可行。只是注意在计算每个seq时要即时保存下来以便parent nodes使用(否则复杂度爆炸)。
关于DP vs Recursion的trade-off可以用Leetcode "斐波那契数列"和“House Robber”系列作为很好的例子。若直接用f(n) = f(n-1) + f(n-2)来求通项的话就是O(2^N)的爆炸,应为所有中间结果都重复计算了,但DP就没有这个问题,但耗费了2个临时变量保存历史。
Pre-Order version of "setSeq" (实际就是recursive calls把两边的处理隔开了):
  1. void setSeq(Node* x) {
  2.   if (!x) return;
  3.   auto xl = x->left, xr = x->right;
  4.   x->seq = to_string(x->val);
  5.   if (!xl && !xr) x->seq += "N,N";
  6.   else {
  7.     setSeq(xl); setSeq(xr); . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.     // xl->seq, xr->seq must be pre-computed
  9.     r->seq += "," + (xl? xl->seq : "N") + "," + (xr? xr->seq : "N");
  10.   }
  11. }
复制代码

补充内容 (2016-10-25 09:23):
Typo at line 9: x->seq += ...
回复 支持 反对

使用道具 举报

 楼主| skye_luobopi 发表于 2016-10-26 07:44:15 | 显示全部楼层
joytostuffratio 发表于 2016-10-23 07:18.1point3acres缃
第三轮什么意思呢?没太明白题意。。。

就是一个html的文件,有好多tag,然后用tag做为子节点,内容是tag包涵的内容,如果里面又有tag就再分出来子节点,是一个recursive生成的树。需要遍历树把body的文本的内容拼出来
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-26 09:56:57 | 显示全部楼层
3. html的tree问题:我不是很懂Html格式。是说每个tree node都有一个tag和content的string,然后还有可能会有subtags吗?
我也用recursion (DFS). 因为Html格式是嵌套的,怎么用BSF呢?  
  1. struct HtmlNode {
  2.   string tag, content;
  3.   vector<HtmlNode*> children;
  4. };
  5. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6. string getBodyString(HtmlNode* r) {
  7.   string body;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  8.   if (!r) return body;
  9.   body = "<" + r->tag + ">" + r->content;
  10.   for (auto x:r->children) body += getBodyString(x);
  11.   body += "</" + r->tag + ">";
  12.   return body;
  13. }
复制代码
回复 支持 反对

使用道具 举报

joytostuffratio 发表于 2016-10-27 02:24:11 | 显示全部楼层
skye_luobopi 发表于 2016-10-26 07:44
就是一个html的文件,有好多tag,然后用tag做为子节点,内容是tag包涵的内容,如果里面又有tag就再分出来 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
所以需要inorder traversal输出是吗?
回复 支持 反对

使用道具 举报

 楼主| skye_luobopi 发表于 2016-10-28 02:22:32 | 显示全部楼层
zzgzzm 发表于 2016-10-26 09:56
3. html的tree问题:我不是很懂Html格式。是说每个tree node都有一个tag和content的string,然后还有可能会 ...

好像就问了bfs的优缺点,没用bfs实现
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 10:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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