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


一亩三分地论坛

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

Google 电面

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

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

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

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

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 与 输出结果是  
    newRoot
    /          \
  / \         / \
0   1       1  0
说中间层不用管,只有leaf node有值. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
LZ想的是把A和B的值都求出来,然后按位补齐,再与,再建一个new tree 然后写了一半时间到了,小哥说万一这个树depth是100怎么办,然后我说会溢出,他就笑了,然后就没有然后了。. From 1point 3acres bbs


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

本帖被以下淘专辑推荐:

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

使用道具 举报

edyyy 发表于 2016-7-13 06:12:45 | 显示全部楼层
不懂什麼意思啊
回复 支持 反对

使用道具 举报

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都可以 ...

应该是这个意思,但是是做&吧
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-7-14 05:16:31 | 显示全部楼层
todayand 发表于 2016-7-14 05:08
应该是这个意思,但是是做&吧
. from: 1point3acres.com/bbs
看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. From 1point 3acres bbs
看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;">;. 1point 3acres 璁哄潧
  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;
  9. </span><span style="color:#cc7832;">    </span>}. From 1point 3acres bbs
  10.     <span style="color:#cc7832;">else</span>{
  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;">;
  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;">;. 1point 3acres 璁哄潧
  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;">;
  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;-google 1point3acres
  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;">;
  22. </span><span style="color:#cc7832;">    </span>}. visit 1point3acres.com for more.

  23.     <span style="color:#cc7832;">return </span>ret<span style="color:#cc7832;">;
  24. </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;
  5.         else if(b==null) return a;

  6.         TreeNode ret = new TreeNode(a.val & b.val);. more info on 1point3acres.com
  7.         if(a.left==null && b.left==null) {
  8.             ret.left = null;
  9.         }
  10.         else{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  11.             TreeNode leftA = a.left == null ? new TreeNode(a.val) : a.left;
  12.             TreeNode leftB = b.left == null ? new TreeNode(b.val) : b.left;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.             ret.left = bitAnd(leftA, leftB);
  14.         }

  15.         if(a.right==null && b.right==null) {
  16.             ret.right = null;
  17.         }-google 1point3acres
  18.         else {
  19.             TreeNode rightA = a.right == null ? new TreeNode(a.val) : a.right;
  20.             TreeNode rightB = b.right == null ? new TreeNode(b.val) : b.right;
  21.             ret.right = bitAnd(rightA, rightB);. visit 1point3acres.com for more.
  22.         }
  23. . 1point 3acres 璁哄潧
  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. visit 1point3acres.com for more.
结果写错了 是& 不好意思~

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){
  6.             if (t1.val == 0)//0 下面的都是0
  7.                 setToZero(t2);
  8.             return;//1 下面的不用管.鐣欏璁哄潧-涓浜-涓夊垎鍦
  9.         }. from: 1point3acres.com/bbs
  10.         AndTree(t1.left,t2.left);. 1point 3acres 璁哄潧
  11.         AndTree(t1.right,t2.right);
  12.     }

  13.     /**. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.      * set leafs to zero
  15.      * @param node  root
  16.      */. 1point3acres.com/bbs
  17.     public void setToZero(TreeNode node) {
  18.         if (node == null)
  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.     }. more info on 1point3acres.com

  27.     public static void main(String[] args) {. 鍥磋鎴戜滑@1point 3 acres
  28.         TreeNode t1 = new TreeNode(-1);
  29.         t1.left = new TreeNode(0);
  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);
  34.         t2.left.right = new TreeNode(0);
  35.         t2.right = new TreeNode(-1);
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  36.         t2.right.left = new TreeNode(1);. Waral 鍗氬鏈夋洿澶氭枃绔,
  37.         t2.right.right = new TreeNode(0);
  38.         new AndTree().AndTree(t1,t2);
  39.         System.out.println(t2);. 1point3acres.com/bbs
  40.     }. from: 1point3acres.com/bbs
  41. }
复制代码

补充内容 (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-11-20 04:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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