【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
yzmys000 发表于 2016-7-13 05:01:47 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
LZ 刚开始面试,google算正式的第二家,没见过这道题,又是最不擅长的tree,小哥很nice,感觉不是很难,但是LZ实力太弱了,最后也没写出来。
题目是按位与两个binary tree,每个tree都是满的,比如
  rootA       rootB
  /    \        /     \
0      1     / \     / \
             1   0   1  0
然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是  . 1point3acres.com/bbs
    newRoot
    /          \. 1point 3acres 璁哄潧
  / \         / \
0   1       1  0
说中间层不用管,只有leaf node有值
LZ想的是把A和B的值都求出来,然后按位补齐,再与,再建一个new tree 然后写了一半时间到了,小哥说万一这个树depth是100怎么办,然后我说会溢出,他就笑了,然后就没有然后了。


补充内容 (2016-7-14 06:58):
写错了 结果应该是0010

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 48
poligun 发表于 2016-7-14 04:58:35 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
虽然我也没看懂题意是什么,不过感觉是要用 stack 实现一个 Binary Tree In-order Iterator。
回复 支持 0 反对 1

使用道具 举报

edyyy 发表于 2016-7-13 06:12:45 | 显示全部楼层
关注一亩三分地微博:
Warald
不懂什麼意思啊
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-13 06:13:00 | 显示全部楼层
这个题目有意思
每一层的node个数是 2^n, 所以假设大的那棵树的leaf那一层有 M 个 node, 小的那棵树的leaf那一层有 N 个 node, M 一定是 N 的 2^k 倍数。
所以先对 小的那棵树 做 bfs, 然后存储Leaf 的 n 个Node。 然后再对 大的那颗树做 bfs, 在 leaf 那一层 进行Update 应该就可以了
回复 支持 反对

使用道具 举报

vancexu 发表于 2016-7-13 06:45:18 | 显示全部楼层
lz能用英文解释一下“然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是”是什么意思吗?
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-7-13 07:04:59 | 显示全部楼层
感觉上题目意思是小树的leaf node和大树对应以相同位置node为根的subtree来做XOR吧。用层遍历或者dfs都可以解决。
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-13 14:31:31 | 显示全部楼层
题目不太清楚 楼主能解释下example 的new root tree 怎么找出来的吗?
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-7-14 01:51:33 | 显示全部楼层
Can you explain the question again?
回复 支持 反对

使用道具 举报

todayand 发表于 2016-7-14 05:08:52 | 显示全部楼层
alexanderzjs 发表于 2016-7-13 07:04
感觉上题目意思是小树的leaf node和大树对应以相同位置node为根的subtree来做XOR吧。用层遍历或者dfs都可以 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
应该是这个意思,但是是做&吧
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-7-14 05:16:31 | 显示全部楼层
todayand 发表于 2016-7-14 05:08
应该是这个意思,但是是做&吧

看lz给的例子应该是xor,如果是&那左边子树应该是两个0,不过这个不是重点:-)
回复 支持 反对

使用道具 举报

 楼主| yzmys000 发表于 2016-7-14 06:59:20 | 显示全部楼层
vancexu 发表于 2016-7-13 06:45
lz能用英文解释一下“然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是”是 ...

就是左子树跟左子树and 右子树跟右子树and
回复 支持 反对

使用道具 举报

 楼主| yzmys000 发表于 2016-7-14 07:00:00 | 显示全部楼层
alexanderzjs 发表于 2016-7-14 05:16
看lz给的例子应该是xor,如果是&那左边子树应该是两个0,不过这个不是重点:-)

结果写错了 是& 不好意思~
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-7-14 08:47:28 | 显示全部楼层
大概写了下代码,递归做的,跑了几个简单的测试:
  1. <span style="color:#cc7832;">public </span>TreeNode <span style="color:#ffc66d;">bitAnd</span>(TreeNode a<span style="color:#cc7832;">, </span>TreeNode b) {
  2.     <span style="color:#cc7832;">if</span>(a==<span style="color:#cc7832;">null </span>&& b == <span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return null;
  3. </span><span style="color:#cc7832;">    else if</span>(a==<span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return </span>b<span style="color:#cc7832;">;
  4. </span><span style="color:#cc7832;">    else if</span>(b==<span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return </span>a<span style="color:#cc7832;">;
  5. </span><span style="color:#cc7832;">
  6. </span><span style="color:#cc7832;">    </span>TreeNode ret = <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val </span>& b.<span style="color:#9876aa;">val</span>)<span style="color:#cc7832;">;
  7. </span><span style="color:#cc7832;">    if</span>(a.<span style="color:#9876aa;">left</span>==<span style="color:#cc7832;">null </span>&& b.<span style="color:#9876aa;">left</span>==<span style="color:#cc7832;">null</span>) {
  8.         ret.<span style="color:#9876aa;">left </span>= <span style="color:#cc7832;">null;. more info on 1point3acres.com
  9. </span><span style="color:#cc7832;">    </span>}
  10.     <span style="color:#cc7832;">else</span>{. From 1point 3acres bbs
  11.         TreeNode leftA = a.<span style="color:#9876aa;">left </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val</span>) : a.<span style="color:#9876aa;">left</span><span style="color:#cc7832;">;.1point3acres缃
  12. </span><span style="color:#cc7832;">        </span>TreeNode leftB = b.<span style="color:#9876aa;">left </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(b.<span style="color:#9876aa;">val</span>) : b.<span style="color:#9876aa;">left</span><span style="color:#cc7832;">;
  13. </span><span style="color:#cc7832;">        </span>ret.<span style="color:#9876aa;">left </span>= bitAnd(leftA<span style="color:#cc7832;">, </span>leftB)<span style="color:#cc7832;">;. 1point3acres.com/bbs
  14. </span><span style="color:#cc7832;">    </span>}

  15.     <span style="color:#cc7832;">if</span>(a.<span style="color:#9876aa;">right</span>==<span style="color:#cc7832;">null </span>&& b.<span style="color:#9876aa;">right</span>==<span style="color:#cc7832;">null</span>) {
  16.         ret.<span style="color:#9876aa;">right </span>= <span style="color:#cc7832;">null;. from: 1point3acres.com/bbs
  17. </span><span style="color:#cc7832;">    </span>}. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  18.     <span style="color:#cc7832;">else </span>{
  19.         TreeNode rightA = a.<span style="color:#9876aa;">right </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val</span>) : a.<span style="color:#9876aa;">right</span><span style="color:#cc7832;">;
  20. </span><span style="color:#cc7832;">        </span>TreeNode rightB = b.<span style="color:#9876aa;">right </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(b.<span style="color:#9876aa;">val</span>) : b.<span style="color:#9876aa;">right</span><span style="color:#cc7832;">;
  21. </span><span style="color:#cc7832;">        </span>ret.<span style="color:#9876aa;">right </span>= bitAnd(rightA<span style="color:#cc7832;">, </span>rightB)<span style="color:#cc7832;">;. From 1point 3acres bbs
  22. </span><span style="color:#cc7832;">    </span>}
  23. -google 1point3acres
  24.     <span style="color:#cc7832;">return </span>ret<span style="color:#cc7832;">;
  25. </span>}
复制代码
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-7-14 08:51:54 | 显示全部楼层
代码贴歪了,再试一下
  1.    
  2. public TreeNode bitAnd(TreeNode a, TreeNode b) {
  3.         if(a==null && b == null) return null;
  4.         else if(a==null) return b;. From 1point 3acres bbs
  5.         else if(b==null) return a;

  6.         TreeNode ret = new TreeNode(a.val & b.val);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  7.         if(a.left==null && b.left==null) {-google 1point3acres
  8.             ret.left = null;. 鍥磋鎴戜滑@1point 3 acres
  9.         }
  10.         else{
  11.             TreeNode leftA = a.left == null ? new TreeNode(a.val) : a.left;. 鍥磋鎴戜滑@1point 3 acres
  12.             TreeNode leftB = b.left == null ? new TreeNode(b.val) : b.left;
  13.             ret.left = bitAnd(leftA, leftB);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  16.         if(a.right==null && b.right==null) {
  17.             ret.right = null;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  18.         }
  19.         else {
  20.             TreeNode rightA = a.right == null ? new TreeNode(a.val) : a.right;
  21.             TreeNode rightB = b.right == null ? new TreeNode(b.val) : b.right;
  22.             ret.right = bitAnd(rightA, rightB);
  23.         }

  24.         return ret;
  25.     }
复制代码
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-14 08:57:24 | 显示全部楼层
muybienw 发表于 2016-7-14 08:51
代码贴歪了,再试一下

觉得有点 overkill 了, 因为题目说明, 中间层的Node不需要考虑 &  的
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-14 09:44:22 | 显示全部楼层
yzmys000 发表于 2016-7-14 07:00
结果写错了 是& 不好意思~
. 1point3acres.com/bbs
lz你能解释一下如果两棵树不一样高的时候按位补齐是怎么补的吗?
比如你例子里:0 1是补成0 0 1 1再跟root B叶节点&,还是补成0 0 0 1再跟叶节点&?  

以及这个题似乎in place比较方便,小哥规定你输出一定要建一棵新树吗?
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-14 10:16:51 | 显示全部楼层
这题跟旁边的那个题...剪枝天壤之别的难度....
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-14 10:48:23 | 显示全部楼层
  1. public class AndTree {
  2.     public void AndTree(TreeNode t1, TreeNode t2) {
  3.         if (t1 == null && t2 == null). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  4.                 return;
  5.         if (t1.left == null && t1.right == null){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  6.             if (t1.val == 0)//0 下面的都是0
  7.                 setToZero(t2);
  8.             return;//1 下面的不用管
  9.         }
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.         AndTree(t1.left,t2.left);
  11.         AndTree(t1.right,t2.right);
  12.     }

  13.     /**.鏈枃鍘熷垱鑷1point3acres璁哄潧
  14.      * set leafs to zero
  15.      * @param node  root
  16.      */
  17.     public void setToZero(TreeNode node) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18.         if (node == null). visit 1point3acres.com for more.
  19.             return;
  20.         if (node.left == null && node.right == null){
  21.             node.val = 0;
  22.             return;
  23.         }
  24.         setToZero(node.left);
  25.         setToZero(node.right);
  26.     }

  27.     public static void main(String[] args) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  28.         TreeNode t1 = new TreeNode(-1);
  29.         t1.left = new TreeNode(0);. 1point 3acres 璁哄潧
  30.         t1.right = new TreeNode(1);
  31.         TreeNode t2 = new TreeNode(-1);
  32.         t2.left = new TreeNode(-1);
  33.         t2.left.left = new TreeNode(1);. 鍥磋鎴戜滑@1point 3 acres
  34.         t2.left.right = new TreeNode(0); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  35.         t2.right = new TreeNode(-1);
  36.         t2.right.left = new TreeNode(1);
  37.         t2.right.right = new TreeNode(0);
  38.         new AndTree().AndTree(t1,t2);
  39.         System.out.println(t2);
  40.     }
  41. }
复制代码
. visit 1point3acres.com for more.
补充内容 (2016-7-14 10:49): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就是same tree原题改的, 0的下面都是0, 需要改一下, 1 的下面不用管, 直接跳出
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-7-15 04:39:53 | 显示全部楼层
readman 发表于 2016-7-14 10:48
补充内容 (2016-7-14 10:49):
就是same tree原题改的, 0的下面都是0, 需要改一下, 1 的下面不用管, 直接 ...

请问follow up怎么做呢?
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-7-15 04:42:21 | 显示全部楼层
根据楼主的例子,题目要求是这样做and. roota (01) and rootb (1010), 注意是左对齐,结果是0010. 两个树可能高度不同。

在前面的帖子中,hyj143已经把思路说的很清楚了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-22 11:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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