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


一亩三分地论坛

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

上周G电面,还在等回复

[复制链接] |试试Instant~ |关注本帖
freegyp 发表于 2017-11-13 15:29:30 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Google - Other - 技术电面 |Other在职跳槽

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

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

x
上周电面,题目不难,边说边写code的,还没回复。
Problem:

You are given a binary tree and a function shouldBeErased(node to check whether a node should be erased. Erase all nodes that should be erased in the binary tree and return the resulting forest in the form of an array of every root node.
. 1point3acres.com/bbs
Follow up:
1. Write a test case. Why do you choose this test case?
2. What if this is a Binary Search Tree? (In this case you are given a list of nodes that should be erased instead of the function.) Does it make the problem simpler or more complicated or just the same?-google 1point3acres



补充内容 (2017-11-13 15:40):. from: 1point3acres.com/bbs
是周二,说错了

补充内容 (2017-11-15 07:39):
几分钟前终于收到邮件告诉我过了

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 37, 订阅: 1
 楼主| freegyp 发表于 2017-11-14 10:28:27 | 显示全部楼层
jason9263 发表于 2017-11-14 03:48. 鍥磋鎴戜滑@1point 3 acres
楼主什么解法呢?~
  1. class Solution(object):
  2.         def recCheck(self,node,fromRoot = True):
  3.                 if shouldBeErased(node):
  4.                         if node.left:
  5.                                 self.recCheck(node.left)
  6.                         if node.right:
  7.                                 self.recCheck(node.right)
  8.                 else:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  9.                         if fromRoot:
  10.                                 self.ans.append(node)
  11.                         if node.left:
  12.                                 self.recCheck(node.left,False)
  13.                                 if shouldBeErased(node.left):
  14.                                         node.left = None
  15.                         if node.right:
  16.                                 self.recCheck(node.right,False)
  17.                                 if shouldBeErased(node.right):-google 1point3acres
  18.                                         node.right = None. From 1point 3acres bbs

  19.         def solution(self,root):. Waral 鍗氬鏈夋洿澶氭枃绔,
  20.                 self.ans = []
  21.                 if root:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  22.                         self.recCheck(root). from: 1point3acres.com/bbs
  23.                 return self.ans
复制代码

补充内容 (2017-11-14 10:30):
我用的Python,不知道你习惯什么语言
回复 支持 1 反对 0

使用道具 举报

 楼主| freegyp 发表于 2017-11-13 15:38:59 | 显示全部楼层
说错了。。不是上周,是周二。。
回复 支持 反对

使用道具 举报

lalasparrow 发表于 2017-11-13 16:09:37 | 显示全部楼层
想问下楼主,erase之后它的children怎么办呢..?
谢谢楼主..!
回复 支持 反对

使用道具 举报

 楼主| freegyp 发表于 2017-11-13 16:18:48 | 显示全部楼层
lalasparrow 发表于 2017-11-13 16:09
想问下楼主,erase之后它的children怎么办呢..?
谢谢楼主..!

如果这个node左右两个child都有并且都不能删,那么删了这个node以后左右两个子节点各自变成另外的tree的root,所以最后会形成多个tree的forest
回复 支持 反对

使用道具 举报

lalasparrow 发表于 2017-11-14 00:25:49 | 显示全部楼层
freegyp 发表于 2017-11-13 16:18
如果这个node左右两个child都有并且都不能删,那么删了这个node以后左右两个子节点各自变成另外的tree的r ...

好的,谢谢楼主!
回复 支持 反对

使用道具 举报

jason9263 发表于 2017-11-14 03:48:20 | 显示全部楼层
楼主什么解法呢?~
回复 支持 反对

使用道具 举报

liuchen1701 发表于 2017-11-14 11:25:39 | 显示全部楼层
freegyp 发表于 2017-11-14 10:28
补充内容 (2017-11-14 10:30):
我用的Python,不知道你习惯什么语言

咦所以是node可以自己定义呀,有parent确实好做了一些。
. 鍥磋鎴戜滑@1point 3 acres
好奇楼主你的followup思路是啥。有比先拿去hash然后DFS/BFS一遍更好的方法吗?
回复 支持 反对

使用道具 举报

 楼主| freegyp 发表于 2017-11-14 11:41:45 | 显示全部楼层
liuchen1701 发表于 2017-11-14 11:25
咦所以是node可以自己定义呀,有parent确实好做了一些。

好奇楼主你的followup思路是啥。有比先拿去ha ...

你是说第二个followup吗?我当时说的意思大概是我觉得就算是BST,还是没有办法比这个好,除非这两种情况
1. 要删除的这些node本来就是按照tree里面preorder的顺序排好的,那跟着array里面的顺序走就是了,运气好有的subtree可以完全忽略掉。
2. 要删除的node相对于所有node的数量来说非常少,这样一来几个O(log n)加起来是有可能比O(n)少很多的。
回复 支持 反对

使用道具 举报

Urumic 发表于 2017-11-14 12:21:47 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!.鏈枃鍘熷垱鑷1point3acres璁哄潧
.1point3acres缃
想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

Urumic 发表于 2017-11-14 12:22:41 | 显示全部楼层
我想了一个BFS的做法,不知道对不对,写了一个大概的Java伪代码,大家帮我看看啊:

  1. public static List<TreeNode> deleteNodes(TreeNode root) {
  2.     List<TreeNode> res = new ArrayList<>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.     Queue<TreeNode> queue = new LinkedList<>();
  4.     Queue<TreeNode> curLevel = new LinkedList<>();
  5.     Map<TreeNode, TreeNode> parentmap = new HashMap<>();
  6.     queue.offer(root);. visit 1point3acres.com for more.
  7.    
  8.     while (!queue.isEmpty()) {
  9.       TreeNode curNode = queue.poll();. 鍥磋鎴戜滑@1point 3 acres
  10.       
  11.       
  12.       TreeNode curParent = map.getOrDefault(curNode, null);
  13.       if (shouldDelete(curNode)) {
  14.         if (curParent != null) { // for parent
  15.           curParent.left = curParent.left == curNode ? null : curParent.left;
  16.           curParent.right = curParent.right == curNode ? null : curParent.right;
  17.         }
  18.         
  19.         map.delete(curNode);
  20.         
  21.         if (curNode.left != null) {
  22.           curLevel.offer(curNode.left);
  23.           curNode.left = null;
  24.         }
  25.         
  26.         if (curNode.right != null) {
  27.           curLevel.offer(curNode.right);
  28.           curNode.right = null;
  29.         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  30.       } else {
  31.         // node with no parent is a root
  32.         if (curParent == null) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  33.           res.add(curNode);
  34.         }
  35.         
  36.         parentmap.remove(curNode);
  37.         
  38.         if (curNode.left != null) {
  39.           curLevel.offer(curNode.left);
  40.           parentmap.put(curNode.left, curNode);
  41.         }
  42.         
  43.         if (curNode.right != null) {
  44.           curLevel.offer(curNode.right);
  45.           parentmap.put(curNode.right, curNode);
  46.         }
  47.       }
  48.       
  49.       
  50.       if (queue.isEmpty()) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  51.         queue = curLevel;
  52.         curLevel = new LinkedList<>();
  53.       }
  54.       
  55.     }
  56.     . visit 1point3acres.com for more.
  57.     return res;
  58.   }
复制代码

补充内容 (2017-11-14 15:15):
第十二行手误啊,map -> parentmap
回复 支持 反对

使用道具 举报

Urumic 发表于 2017-11-14 12:26:03 | 显示全部楼层
还有就是,这个数是BST的话会容易做吗?应该一样吧?
回复 支持 反对

使用道具 举报

 楼主| freegyp 发表于 2017-11-14 14:37:48 | 显示全部楼层
Urumic 发表于 2017-11-14 12:22
我想了一个BFS的做法,不知道对不对,写了一个大概的Java伪代码,大家帮我看看啊:

第12行是不是"parentmap.getOrDefault(curNode, null);"?.1point3acres缃

BST的话你看我楼上的回复有没有问题
回复 支持 反对

使用道具 举报

Urumic 发表于 2017-11-14 15:14:32 | 显示全部楼层
freegyp 发表于 2017-11-14 14:37
第12行是不是"parentmap.getOrDefault(curNode, null);"?

BST的话你看我楼上的回复有没有问题

第十二行手误。。。。。。。。

回答应该可以,我也觉得除非和顺序有关系,不然就算是BST也没啥意义啊。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 13:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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