【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 4961|回复: 15
收起左侧

FB跪经,疑似新题,我是没见过

[复制链接] |试试Instant~ |关注本帖
我的人缘0
jialiu54321 发表于 2016-10-18 06:11:02 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩

2016(10-12月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面 在线笔试  | Fail | fresh grad应届毕业生

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

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

x
中国人面的,打了个招呼就开始做题,一共四十五分钟

就一道题:
remove as many edges as possible from a tree and the result trees all have even number of nodes
. Waral 博客有更多文章,
         o
  /    |   |   \
o     o   o    o
|      
o

比如可以删掉一个边变成:
         o
  x    |   |   \
o     o   o    o
|      
o
结果里有两个tree,分别有2个和四个node,符合条件,这就是答案,因为再删就不符合条件了
return是一个list,里面是所有新生成的tree的root

花了三十分钟没搞定,果断挂了
.本文原创自1point3acres论坛
后来想想应该便利两次,
第一次记录所有以当前node为根的subtree的node总数
第二次就可以用这些数据切割树了

当时脑子糊住没想到

评分

参与人数 1大米 +3 收起 理由
dobbin + 3 感谢分享!

查看全部评分


上一篇:IBM Entry Level Front-End Developer OA
下一篇:前几天的bloomberg
我的人缘0
rinto 发表于 2016-10-18 09:12:05 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
修改了一下,可以跑楼主给的例子了。


  1. public class TreeNode{
  2.     int val;. more info on 1point3acres
  3.     List<TreeNode> subtree;-google 1point3acres
  4.     public TreeNode(int val){
  5.         this.val = val;
  6.         subtree = new ArrayList<>();
  7.     }

  8.     public void addChild(TreeNode child){
  9.         subtree.add(child);
  10.     }
  11. }

  12. public class BreakTree {

  13.     public List<TreeNode> breakTree(TreeNode root){
  14.         List<TreeNode> result = new ArrayList<>();
  15.         countAndBreak(result, root);
  16.         return result;
  17.     }
  18. -google 1point3acres
  19.     private int countAndBreak(List<TreeNode> result, TreeNode root){
  20.         if (root == null){
  21.             return 0;. visit 1point3acres for more.
  22.         }

  23.         int count = 1;. 围观我们@1point 3 acres
  24.         Iterator<TreeNode> iter = root.subtree.iterator();.留学论坛-一亩-三分地
  25.         while (iter.hasNext()){
  26.             int childCount = countAndBreak(result, iter.next());
    .留学论坛-一亩-三分地
  27.             if (childCount == 0){
  28.                 iter.remove();
  29.             } else{
  30.                 count += childCount;
  31.             }
  32.         }

  33.         if (count % 2 == 0){ 来源一亩.三分地论坛.
  34.             result.add(root);
  35.             return 0;. 牛人云集,一亩三分地
  36.         } else{
  37.             return count;
  38.         }
  39.     }
  40. . 一亩-三分-地,独家发布

  41.     public static void main(String[] args){
  42.         TreeNode root = new TreeNode(0);
  43. . 围观我们@1point 3 acres
  44.         TreeNode firstChild = new TreeNode(1);
  45.         firstChild.addChild(new TreeNode(2));
  46.         root.addChild(firstChild);. 1point3acres

  47.         root.addChild(new TreeNode(3));
  48.         root.addChild(new TreeNode(4));
    来源一亩.三分地论坛.
  49.         root.addChild(new TreeNode(5));

  50.         BreakTree soln = new BreakTree();
  51.         List<TreeNode> result = soln.breakTree(root);
  52.         System.out.println(result.size());
  53.     }. visit 1point3acres for more.
  54. }
复制代码
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 06:24:33 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
jialiu54321 发表于 2016-10-18 06:23
一个空白的编辑器,所有都要自己写,包括TreeNode,test case等等

楼主运气真好差。。。这国人大哥坑爹呀。。。
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 06:21:08 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
楼主运气好差。。摸摸。。。 来源一亩.三分地论坛.

这题的输入类型是什么?多叉树node吗?
回复

使用道具 举报

我的人缘0
 楼主| jialiu54321 发表于 2016-10-18 06:23:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩
iPhD 发表于 2016-10-18 06:21
楼主运气好差。。摸摸。。。.1point3acres网
. 留学申请论坛-一亩三分地
这题的输入类型是什么?多叉树node吗?
-google 1point3acres
一个空白的编辑器,所有都要自己写,包括TreeNode,test case等等

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
yingy4 发表于 2016-10-18 06:44:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (201)
 
 
6% (13)  踩
这貌似是hackerrank的原题,https://www.hackerrank.com/challenges/even-tree
回复

使用道具 举报

我的人缘0
yuanxiehuang 发表于 2016-10-18 07:13:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  78% (229)
 
 
21% (64)  踩
public class TreeNode {
    public List<TreeNode> children;
    int count;//This variable means how many children node including itself under this node.

} 来源一亩.三分地论坛.
public List<TreeNode> removeEdges(TreeNode root) {. from: 1point3acres
        List<TreeNode> result = new ArrayList<>();
        if (root == null) {
            return result;.本文原创自1point3acres论坛
        }
        recursiveRemvoe(root, result);
        return result;
    }

    private void recursiveRemvoe(TreeNode root, List<TreeNode> list) {
        if (root.children.size() == 0) {
            return;
        }
        for (int i = 0; i < root.children.size(); i++) {
            TreeNode cur = root.children.get(i);
            if ((root.count - cur.count) % 2 == 0) {
                list.add(cur);
                root.count -= cur.count;
                recursiveRemvoe(cur, list);. 留学申请论坛-一亩三分地
            }
        }
    }

大家看看这样可以吗? 我自己粗略写了一下,请大家轻喷...
回复

使用道具 举报

我的人缘0
rinto 发表于 2016-10-18 08:41:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (5)
 
 
0% (0)  踩
确实没见过这种题,很tricky啊,开始还以为要先把树转化成图来做,仔细看了一下输出要求仍然是树,估计面试遇到这个题往这个方向一想就崩了。。。patpat楼主
来源一亩.三分地论坛.
我是这么想的,对于一个root的每个子结点,可以递归的边count边把偶数个node的枝给切了(切掉的不算在count里),所以这个返回值肯定是奇数,如果所有这些剩下的点加上root正好是偶数个,root可以单独成树。大概的code如下
-google 1point3acres
code现在有个bug,parent.subtree.remove(root); 会影响上一层recursive里面的 for (TreeNode node : root.subtree),可能扔出个concurrentmodificationexception。。可能mark一下再修改或者传个iterator把自己删了会好点. 围观我们@1point 3 acres


  1. public class BreakTree {
  2.     class TreeNode{
  3.         int val;. visit 1point3acres for more.
  4.         List<TreeNode> subtree;
  5.         TreeNode(int val){
  6.             this.val = val;
  7.             subtree = new ArrayList<>();
  8.         }
  9.     }
  10.     -google 1point3acres
  11.    
  12.     public List<TreeNode> breakTree(TreeNode root){
  13.         List<TreeNode> result = new ArrayList<>();
  14.         countAndBreak(result, root, null);
  15.         return result;. 牛人云集,一亩三分地
  16.     }
  17.    
  18.     private int countAndBreak(List<TreeNode> result, TreeNode root, TreeNode parent){
  19.         if (root == null){. 留学申请论坛-一亩三分地
  20.             return 0;
  21.         }
  22.         
  23.         int count = 1;
  24.         for (TreeNode node : root.subtree){
  25.             count += countAndBreak(result, node, root);. from: 1point3acres
  26.         }
  27.         
  28.         if (count % 2 == 0){
  29.             if (parent != null){
  30.                 parent.subtree.remove(root);
  31.             }. from: 1point3acres
  32.             result.add(root);.本文原创自1point3acres论坛
  33.             return 0;.留学论坛-一亩-三分地
  34.         } else{
    . Waral 博客有更多文章,
  35.             return count;. 牛人云集,一亩三分地
  36.         }. 围观我们@1point 3 acres
  37.     } 来源一亩.三分地论坛.
  38. }
复制代码

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 08:53:42 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
rinto 发表于 2016-10-18 08:41
确实没见过这种题,很tricky啊,开始还以为要先把树转化成图来做,仔细看了一下输出要求仍然是树,估计面试 ...
  1. public class EvenTree {

  2.     private Set<Integer>[] adj;
  3.     private boolean[] visited;
  4.     private int E;. 围观我们@1point 3 acres
  5.     private int V;
  6.     private int count;
  7.     private List<Integer> nodes;

  8.     public EvenTree(int E, int V) {
  9.         adj = new (HashSet<Integer>) Object[V];-google 1point3acres
  10.         visited = new boolean[V];
  11.         this.E = E;
  12.         this.V = V;
  13.         count = 0;
  14.         nodes = new ArrayList<Integer>();      . Waral 博客有更多文章,
  15.     }. 围观我们@1point 3 acres

  16.     public int dfs(int node) {
  17.         visit[node] = true;
  18.         int children = 0;

  19.         for (Integer v : adj[node]) {
  20.             if (!visit[v]) {.1point3acres网
  21.                 int num = dfs(v);
  22.                 if (num % 2 == 0) {
  23.                     count++;
  24.                 } else {
  25.                     children += num;. 1point 3acres 论坛
  26.                 }
  27.             }
  28.         }

  29.         if (children % 2 == 1) {
  30.             nodes.add(node);
  31.         }
  32.         
  33.         return children + 1;
  34.     }.留学论坛-一亩-三分地

  35.     public static void main(String[] args) {
  36.         EvenTree et = new EvenTree(E, V);
  37.         for (int i = 0; i < E; i++) {
  38.             et.adj[v1].add(v2);
  39.             et.adj[v2].add(v1);
  40.         }

  41.         et.dfs(0);
  42.     }

  43. }
复制代码
回复

使用道具 举报

我的人缘0
yhatl 发表于 2016-10-18 09:26:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
遍历一遍 只要children有even个 就cut加入forest
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 09:27:20 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
yhatl 发表于 2016-10-18 09:26
遍历一遍 只要children有even个 就cut加入forest
. 一亩-三分-地,独家发布
你能帮忙看下我贴的那个代码对不?

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
yhatl 发表于 2016-10-18 09:38:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
iPhD 发表于 2016-10-18 09:27
你能帮忙看下我贴的那个代码对不?

不好意思,我用c++的,java看着太费劲了
不过这题和LC366差不多,所以便利一遍是够了
回复

使用道具 举报

我的人缘0
whyvic13 发表于 2016-10-18 11:16:49 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (68)
 
 
0% (0)  踩
rinto 发表于 2016-10-18 09:12
修改了一下,可以跑楼主给的例子了。
.本文原创自1point3acres论坛
        root
      /   |    \. 牛人云集,一亩三分地
    1     3    5
    |      |     |. 1point 3acres 论坛
    2      4    6

我也差不多这样写的,可是如果总node总数是奇数的话, 比如上面这种情况root就会变成一个单独的node并且怎么删都没法保证所有的子树是even number,所以这题的前提是node总数为偶数?
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-18 11:20:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (346)
 
 
38% (215)  踩
rinto 发表于 2016-10-18 09:12
修改了一下,可以跑楼主给的例子了。

请问为啥 iter.remove(); 是remove的edge 而不是 node本身?

补充内容 (2016-10-18 11:36):
懂了 层主简直是大牛
回复

使用道具 举报

我的人缘0
iwantanintern 发表于 2018-1-13 13:32:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  72% (57)
 
 
27% (22)  踩
国人大哥还故意出这么难的题 看地里好几次偏题怪题都是国人大哥
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-19 23:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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