一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1325|回复: 18
收起左侧

上周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.

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?.鏈枃鍘熷垱鑷1point3acres璁哄潧
. From 1point 3acres bbs

. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2017-11-13 15:40):. visit 1point3acres.com for more.
是周二,说错了

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

评分

1

查看全部评分

wojiushieyu 发表于 2017-11-28 23:44:25 | 显示全部楼层
        public List<Node> erase(Node root) {
                List<Node> res = new LinkedList<>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                helper(root, res, true);. From 1point 3acres bbs
                return res;
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧

        public Node helper(Node node, List<Node> res, boolean put) {
                if (node == null)
                        return null;
                if (shouldBeErased(node)) {
                        helper(node.left, res, true);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        helper(node.right, res, true);
                        return null;
                } else {
                        if (put) {
                                res.add(node);
                        }
                        node.left = helper(node.left, res, false);
                        node.right = helper(node.right, res, false);
                        return node;
                }

        }

补充内容 (2017-11-29 00:08):
duo xie lou zhu fen xiang, zhan zhan xi qi .
回复 支持 3 反对 0

使用道具 举报

 楼主| freegyp 发表于 2017-11-14 10:28:27 | 显示全部楼层
jason9263 发表于 2017-11-14 03:48
楼主什么解法呢?~
  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). 鍥磋鎴戜滑@1point 3 acres
  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). From 1point 3acres bbs
  17.                                 if shouldBeErased(node.right):
  18.                                         node.right = None

  19.         def solution(self,root):
  20.                 self.ans = []
  21.                 if root:. 1point3acres.com/bbs
  22.                         self.recCheck(root).鐣欏璁哄潧-涓浜-涓夊垎鍦
  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):. more info on 1point3acres.com
我用的Python,不知道你习惯什么语言

咦所以是node可以自己定义呀,有parent确实好做了一些。. visit 1point3acres.com for more.

好奇楼主你的followup思路是啥。有比先拿去hash然后DFS/BFS一遍更好的方法吗?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

Urumic 发表于 2017-11-14 12:21:47 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

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

  1. public static List<TreeNode> deleteNodes(TreeNode root) {-google 1point3acres
  2.     List<TreeNode> res = new ArrayList<>();-google 1point3acres
  3.     Queue<TreeNode> queue = new LinkedList<>();
  4.     Queue<TreeNode> curLevel = new LinkedList<>();
  5.     Map<TreeNode, TreeNode> parentmap = new HashMap<>();
  6.     queue.offer(root);
  7.    
  8.     while (!queue.isEmpty()) {
  9.       TreeNode curNode = queue.poll();
  10.       . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.       . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  12.       TreeNode curParent = map.getOrDefault(curNode, null);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.         .1point3acres缃
  21.         if (curNode.left != null) {
  22.           curLevel.offer(curNode.left);-google 1point3acres
  23.           curNode.left = null;
  24.         }
  25.         .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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) {
  33.           res.add(curNode);
  34.         }
  35.         
  36.         parentmap.remove(curNode);
  37.         
  38.         if (curNode.left != null) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  39.           curLevel.offer(curNode.left);
  40.           parentmap.put(curNode.left, curNode);
  41.         }
  42.         .1point3acres缃
  43.         if (curNode.right != null) {
  44.           curLevel.offer(curNode.right);
  45.           parentmap.put(curNode.right, curNode);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.         }
  47.       }
  48.       
  49.       
  50.       if (queue.isEmpty()) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.         queue = curLevel;
  52.         curLevel = new LinkedList<>();
  53.       }
  54.       
  55.     }
  56.     . 鍥磋鎴戜滑@1point 3 acres
  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);"?.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

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

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

使用道具 举报

LUOLUOLNSH 发表于 2017-12-1 23:20:17 | 显示全部楼层
wojiushieyu 发表于 2017-11-28 23:44
public List erase(Node root) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                List res = new LinkedList();
                helper(root, res, true);

thanks for your code
回复 支持 反对

使用道具 举报

wojiushieyu 发表于 2017-12-2 21:09:23 | 显示全部楼层

不客气 感觉这种non tail recursion 能不能现场想出来写出来全看心情.....手动滑稽
回复 支持 反对

使用道具 举报

huangya2 发表于 2017-12-8 06:39:36 | 显示全部楼层
感谢分享! 楼主好运!
回复 支持 反对

使用道具 举报

mars0 发表于 2018-1-7 08:48:06 | 显示全部楼层
多谢楼主分享~~~~~

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-20 03:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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