在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 3952|回复: 13
收起左侧

FB 电面

[复制链接] |试试Instant~ |关注本帖
lotustree86 发表于 2016-3-2 05:12:40 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Other | 在职跳槽

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

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

x
刚刚结束的FB 电面
Problem 1: check if a BT is a BST 来源一亩.三分地论坛.
Problem 2: Given a set of Tree Nodes, find if they form a single valid BST, if so return the root
Example:
Nodes : (Node1, Node 2)
Tree structre:
   Node1
/
Node2
. Waral 博客有更多文章,
In this case, return Node1.. more info on 1point3acres
Nodes : (Node1, Node 2)
Tree structre:. 1point3acres
   Node1
/
Node3

In this case, return null。
. 1point3acres
第二题我的做法就是把所有的nodes放到一个Set里面,随便用其中的一个node做root, 然后BFS/DFS traverse, 遍历时,将所有被visited 的 child node从Set中remove掉,并且用一个变量记住当前visited的node的总数,做递归,一直到set里只有一个node,这就是想要的结果;或者所有的node都被Visited,但是set里的node数量仍然大于一,这说明有两个BT, return null。最后针对返回的节点做bst validation.


补充内容 (2016-3-2 09:36):
代码贴在下面了,我后来自己又写了一遍,面试的时候只是说了思路,代码大体写了一下,bug遍地跑,目不忍睹呀 ! :) Bless 拿到onsite !

评分

1

查看全部评分

duduhaha 发表于 2016-3-2 14:19:45 | 显示全部楼层
lotustree86 发表于 2016-3-2 11:37
你可以这么认为,输入是某一颗或者N颗树的节点组成的集合,顺序是乱的,但是每个节点还是保留原来左右子节 ...

这题首先可以判断有多少个node的indegree 为 0 吧。如果多于一个,肯定返回false.
如果只有一个,从这个节点出发做dfs构建二叉树,然后再判断是bst or not.
回复 支持 2 反对 0

使用道具 举报

sealove999 发表于 2016-4-18 10:22:44 | 显示全部楼层
lotustree86 发表于 2016-3-2 15:24
你这个方法不错,先找到根节点,再遍历
  1. public class Solution {.本文原创自1point3acres论坛
  2.   public TreeNode onetree(Set<TreeNode> set) {
  3.     Set<TreeNode> candidate = new HashSet<>(set);
  4.     for (TreeNode tn : set) {
  5.       if (tn.left != null) {
  6.         candidate.remove(tn.left);
  7.       }
  8.       if (tn.right != null) {
  9.         candidate.remove(tn.right);
  10.       }
  11.     }
  12.     for (TreeNode root : candidate) {
  13.       Set<TreeNode> nodes = new HashSet<>(set);. 1point3acres
  14.       Deque<TreeNode> queue = new ArrayDeque<>(); 来源一亩.三分地论坛.
  15.       queue.offer(root);.1point3acres网
  16.       nodes.remove(root);
  17.       while (!queue.isEmpty()) {. 牛人云集,一亩三分地
  18.         TreeNode tn = queue.poll();
  19.         if (tn.left != null) {. 留学申请论坛-一亩三分地
  20.           queue.offer(tn.left);
  21.           nodes.remove(tn.left);-google 1point3acres
  22.         }
  23.         if (tn.right != null) {
  24.           queue.offer(tn.right);
  25.           nodes.remove(tn.right);
  26.         }
  27.       }. 1point 3acres 论坛
  28.       if (nodes.isEmpty())
  29.         return root;
  30.     }
  31.     return null;. From 1point 3acres bbs
  32.   }

  33.   public static void main(String[] args) {
  34.     Solution s = new Solution();
  35.     TreeNode tn1 = new TreeNode(1);
  36.     TreeNode tn2 = new TreeNode(2);
  37.     TreeNode tn3 = new TreeNode(3);
  38.     TreeNode tn4 = new TreeNode(4);
  39.     TreeNode tn5 = new TreeNode(5);
  40.     TreeNode tn6 = new TreeNode(6);
  41.     TreeNode tn7 = new TreeNode(7);
  42.     tn1.left = tn2;
  43.     tn1.right = tn3;-google 1point3acres
  44.     tn2.right = tn4;.留学论坛-一亩-三分地
  45.     tn5.left = tn6;
  46.     tn5.right = tn7;
  47.     Set<TreeNode> set1 = new HashSet<>();. more info on 1point3acres
  48.     set1.add(tn1);
  49.     set1.add(tn2);
  50.     set1.add(tn3);
  51.     set1.add(tn4);. 一亩-三分-地,独家发布
  52.     Set<TreeNode> set2 = new HashSet<>();
  53.     set2.add(tn1);
  54.     set2.add(tn2);. 牛人云集,一亩三分地
  55.     set2.add(tn3);
  56.     set2.add(tn4);
  57.     set2.add(tn5);
  58.     set2.add(tn6);
  59.     set2.add(tn7);
  60.     System.out.println(s.onetree(set1).equals(tn1));
  61.     System.out.println(s.onetree(set2) == null);
  62.   }
  63. }
复制代码
回复 支持 1 反对 0

使用道具 举报

singku 发表于 2016-3-2 09:07:09 | 显示全部楼层
第二题,楼主 如果第一个找到的就是叶子节点,或者在遍历的时候,找到的一个节点,其下层的节点都被处理完了。怎么处理?判断是否合法的BST,应该判断节点及左右两个子节点是否满足BST的特性吧?对于找到的一个下层已被处理完的节点,这时只能找到他的父节点啊?
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 09:34:28 | 显示全部楼层
import java.util.*;. more info on 1point3acres
import common.*;. 留学申请论坛-一亩三分地

public class Solution {-google 1point3acres
    public static TreeNode findRoot(Set<TreeNode> set, int count) {
        if(set.size() == 0) {
            return null;
        }
-google 1point3acres
        // If there are only one TreeNode left, return it
        if(set.size() == 1) {
            return set.iterator().next();
        }

        // check if all TreeNodes are already visited, if so, return null
        if(count == 0) {
            return null;
        }

        // get any node that has not been visited yet
        Queue<TreeNode> queue = new ArrayDeque<>();
        for (TreeNode treeNode : set) {
            if(!treeNode.visited) {. From 1point 3acres bbs
                queue.offer(treeNode);
                break;
来源一亩.三分地论坛.             }
        }-google 1point3acres
        
        // bfs traverse
        while(!queue.isEmpty()) {.1point3acres网
            TreeNode node = queue.poll();
            node.visited = true;. 1point 3acres 论坛
            count--;

            if(node.left != null) {
                if(set.contains(node.left)) {
                    set.remove(node.left);. 围观我们@1point 3 acres
                    if(!node.left.visited) {
. 1point3acres                        queue.offer(node.left);
                    } 来源一亩.三分地论坛.
                } else {
                    return null;
                }
            }

            if(node.right != null && !node.right.visited) {
                if(set.contains(node.right)) {
                    set.remove(node.right);
                    if(!node.right.visited) {.留学论坛-一亩-三分地
                        queue.offer(node.right);
                    }
                } else {
                    return null;. 1point3acres
                }
            }
        }

        return findRoot(set, count);
    }
}
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 09:34:45 | 显示全部楼层
singku 发表于 2016-3-2 09:07
第二题,楼主 如果第一个找到的就是叶子节点,或者在遍历的时候,找到的一个节点,其下层的节点都被处理完 ...

我把代码贴出来了
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-3-2 09:48:25 | 显示全部楼层
第二题看不懂题意啊。。树的结构提前给定了嘛?
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 11:37:02 | 显示全部楼层
你可以这么认为,输入是某一颗或者N颗树的节点组成的集合,顺序是乱的,但是每个节点还是保留原来左右子节点的信息的,让你判断这些节点是不是来自同一颗二叉树,并且也不任何节点,并返还跟节点。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 11:37:39 | 显示全部楼层
也不缺任何节点
回复 支持 反对

使用道具 举报

singku 发表于 2016-3-2 14:38:14 | 显示全部楼层
我觉得可以做一个自底向上的广度收缩,看能不能找到一个符合BST条件的根节点。因为每个点的左右孩子都有,一遍遍历可以建立起每个节点的父子关系,丢到哈希表中,建立的时候如果有多个节点没有父节点,则返回false,否则这个节点是根节点。然后除根节点外的所有节点进入一个set. 对set中的每个节点,从哈西表中找到父节点,判断这三个或者两个节点是否满足BST特性。不满足,则函数返回false。满足则孩子出set. 当整个set中没有节点时,返回true. 自底向上的BST已经建好了。
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 15:24:15 | 显示全部楼层
duduhaha 发表于 2016-3-2 14:19
这题首先可以判断有多少个node的indegree 为 0 吧。如果多于一个,肯定返回false.. more info on 1point3acres
如果只有一个,从这个 ...

你这个方法不错,先找到根节点,再遍历
回复 支持 反对

使用道具 举报

tldxk 发表于 2016-3-12 10:26:18 | 显示全部楼层
楼主为什么要用count呢?还是说给定的参数就有count?求检查下我的代码:
  1. public TreeNode findSingleBST(Set<TreeNode> set) {
  2.     if (set == null) {
  3.         return null;
  4.     }

  5.     TreeNode root = null;. more info on 1point3acres
  6.     for (TreeNode node : new HashSet<>(set)) {
  7.         if (set.contains(node)) {. more info on 1point3acres
  8.             root = node;
  9.             // dfs
  10.             Stack<TreeNode> stack = new Stack<>();
  11.             stack.push(root);
  12.             while (!stack.isEmpty()) {
  13.                 TreeNode current = stack.pop(); 来源一亩.三分地论坛.
  14.                 if (current != root) {
  15.                     set.remove(current);.1point3acres网
  16.                 } 来源一亩.三分地论坛.
  17.                 if (current.left != null) {
  18.                     stack.push(current.left);
  19.                 }
  20.                 if (current.right != null) {
    . Waral 博客有更多文章,
  21.                     stack.push(current.right);
  22.                 }
  23.             }
  24.         }
  25.     }

  26.     if (set.size() > 1) {
  27.         return null;. 1point 3acres 论坛
  28.     }
  29.     return root;
  30. }
复制代码
回复 支持 反对

使用道具 举报

sjph 发表于 2016-7-31 17:44:02 | 显示全部楼层
tldxk 发表于 2016-3-12 10:26. visit 1point3acres for more.
楼主为什么要用count呢?还是说给定的参数就有count?求检查下我的代码:
来源一亩.三分地论坛.
请问楼上做法,这个没有判断是否为BST吧?包括大家的做法,都没看出在哪里判断是BST了。抱歉,求讲解!
回复 支持 反对

使用道具 举报

qesss 发表于 2016-9-29 01:54:51 | 显示全部楼层
第二题应该用拓扑排序的思想。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-23 01:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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