谈谈面试官在面试coding题目时的考察终点与心理活动, 求大米

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1988|回复: 21
收起左侧

上周G电面,还在等回复

[复制链接] |试试Instant~ |关注本帖
我的人缘0
freegyp 发表于 2017-11-13 15:29:30 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩

2017(10-12月) 码农类General 硕士 全职@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?



补充内容 (2017-11-13 15:40):
是周二,说错了
. Waral 博客有更多文章,
补充内容 (2017-11-15 07:39):
几分钟前终于收到邮件告诉我过了

评分

参与人数 1大米 +5 收起 理由
lalasparrow + 5 给你点个赞!

查看全部评分


上一篇:Twitter 今日OA
下一篇:Wish 电面面经 11/10/2017
我的人缘0
wojiushieyu 发表于 2017-11-28 23:44:25 | 显示全部楼层
本楼: 【顶】   100% (3)
 
 
0% (0)   【踩】
全局: 顶  96% (29)
 
 
3% (1)  踩
        public List<Node> erase(Node root) {
                List<Node> res = new LinkedList<>();
                helper(root, res, true);
                return res;
        }
-google 1point3acres
        public Node helper(Node node, List<Node> res, boolean put) {
                if (node == null)
                        return null;
                if (shouldBeErased(node)) {
                        helper(node.left, res, true);
                        helper(node.right, res, true);
                        return null;. 1point3acres
                } else {
                        if (put) {
                                res.add(node);
                        }
                        node.left = helper(node.left, res, false);
                        node.right = helper(node.right, res, false);
                        return node;
                }.本文原创自1point3acres论坛

        }

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

使用道具 举报

我的人缘0
 楼主| freegyp 发表于 2017-11-14 10:28:27 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
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:. more info on 1point3acres
  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:. From 1point 3acres bbs
  16.                                 self.recCheck(node.right,False). visit 1point3acres for more.
  17.                                 if shouldBeErased(node.right):
  18.                                         node.right = None

  19.         def solution(self,root):
  20.                 self.ans = []
  21.                 if root:
  22.                         self.recCheck(root).本文原创自1point3acres论坛
  23.                 return self.ans
复制代码

补充内容 (2017-11-14 10:30):. Waral 博客有更多文章,
我用的Python,不知道你习惯什么语言
回复

使用道具 举报

我的人缘0
 楼主| freegyp 发表于 2017-11-13 15:38:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
说错了。。不是上周,是周二。。
回复

使用道具 举报

我的人缘0
lalasparrow 发表于 2017-11-13 16:09:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (36)
 
 
2% (1)  踩
想问下楼主,erase之后它的children怎么办呢..?
谢谢楼主..!
回复

使用道具 举报

我的人缘0
 楼主| freegyp 发表于 2017-11-13 16:18:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
lalasparrow 发表于 2017-11-13 16:09
想问下楼主,erase之后它的children怎么办呢..?
谢谢楼主..!

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

使用道具 举报

我的人缘0
lalasparrow 发表于 2017-11-14 00:25:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (36)
 
 
2% (1)  踩
freegyp 发表于 2017-11-13 16:18
如果这个node左右两个child都有并且都不能删,那么删了这个node以后左右两个子节点各自变成另外的tree的r ...

好的,谢谢楼主!
回复

使用道具 举报

我的人缘0
jason9263 发表于 2017-11-14 03:48:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  80% (28)
 
 
20% (7)  踩
楼主什么解法呢?~
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
liuchen1701 发表于 2017-11-14 11:25:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  50% (1)
 
 
50% (1)  踩
freegyp 发表于 2017-11-14 10:28. 围观我们@1point 3 acres
补充内容 (2017-11-14 10:30):
我用的Python,不知道你习惯什么语言

咦所以是node可以自己定义呀,有parent确实好做了一些。

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

使用道具 举报

我的人缘0
 楼主| freegyp 发表于 2017-11-14 11:41:45 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
liuchen1701 发表于 2017-11-14 11:25
咦所以是node可以自己定义呀,有parent确实好做了一些。

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

使用道具 举报

我的人缘0
Urumic 发表于 2017-11-14 12:21:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

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

使用道具 举报

我的人缘0
Urumic 发表于 2017-11-14 12:22:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
我想了一个BFS的做法,不知道对不对,写了一个大概的Java伪代码,大家帮我看看啊: 来源一亩.三分地论坛.
. 一亩-三分-地,独家发布
  1. public static List<TreeNode> deleteNodes(TreeNode root) {. Waral 博客有更多文章,
  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);
  7.    
  8.     while (!queue.isEmpty()) {
  9.       TreeNode curNode = queue.poll();
  10.       
  11.       
  12.       TreeNode curParent = map.getOrDefault(curNode, null);
  13.       if (shouldDelete(curNode)) {. From 1point 3acres bbs
  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.         . 1point 3acres 论坛
  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) {
  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.         }.本文原创自1point3acres论坛
  42.         
    -google 1point3acres
  43.         if (curNode.right != null) {
  44.           curLevel.offer(curNode.right); 来源一亩.三分地论坛.
  45.           parentmap.put(curNode.right, curNode);-google 1point3acres
  46.         }
  47.       }
  48.       
  49.       
  50.       if (queue.isEmpty()) {
  51.         queue = curLevel;
  52.         curLevel = new LinkedList<>();
  53.       }
  54.       . visit 1point3acres for more.
  55.     }
  56.    
  57.     return res;
  58.   }
复制代码

补充内容 (2017-11-14 15:15):.本文原创自1point3acres论坛
第十二行手误啊,map -> parentmap
回复

使用道具 举报

我的人缘0
Urumic 发表于 2017-11-14 12:26:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
还有就是,这个数是BST的话会容易做吗?应该一样吧?
回复

使用道具 举报

我的人缘0
 楼主| freegyp 发表于 2017-11-14 14:37:48 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
Urumic 发表于 2017-11-14 12:22
我想了一个BFS的做法,不知道对不对,写了一个大概的Java伪代码,大家帮我看看啊:

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

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

使用道具 举报

我的人缘0
Urumic 发表于 2017-11-14 15:14:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (39)
 
 
0% (0)  踩
freegyp 发表于 2017-11-14 14:37
第12行是不是"parentmap.getOrDefault(curNode, null);"?

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

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

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

使用道具 举报

我的人缘0
LUOLUOLNSH 发表于 2017-12-1 23:20:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
wojiushieyu 发表于 2017-11-28 23:44
public List erase(Node root) {
                List res = new LinkedList();
                helper(root, res, true);

thanks for your code
回复

使用道具 举报

我的人缘0
wojiushieyu 发表于 2017-12-2 21:09:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (29)
 
 
3% (1)  踩

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

使用道具 举报

我的人缘0
huangya2 发表于 2017-12-8 06:39:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
感谢分享! 楼主好运!
回复

使用道具 举报

我的人缘0
mars0 发表于 2018-1-7 08:48:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (72)
 
 
0% (0)  踩
多谢楼主分享~~~~~

评分

参与人数 1大米 +5 收起 理由
lctc432 + 5 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

我的人缘0
lavender41 发表于 2018-1-26 12:06:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (55)
 
 
3% (2)  踩
freegyp 发表于 2017-11-14 11:41.1point3acres网
你是说第二个followup吗?我当时说的意思大概是我觉得就算是BST,还是没有办法比这个好,除非这两种情况.本文原创自1point3acres论坛
...

求问楼主,如果按preorder排好了有什么好处么?如果是BST的话,我们找每个要删除的node难道不是用大小关系么?
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

custom counter

GMT+8, 2018-7-23 12:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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