一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2687|回复: 13
收起左侧

FB 电面

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

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

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

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

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

In this case, return Node1.
Nodes : (Node1, Node 2)
Tree structre:. more info on 1point3acres.com
   Node1
/
Node3

In this case, return null。

第二题我的做法就是把所有的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. From 1point 3acres bbs
你这个方法不错,先找到根节点,再遍历
  1. public class Solution {
  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);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.       Deque<TreeNode> queue = new ArrayDeque<>();
  15.       queue.offer(root);
  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);
  22.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.         if (tn.right != null) {
  24.           queue.offer(tn.right);
  25.           nodes.remove(tn.right);
  26.         }. 1point 3acres 璁哄潧
  27.       }
  28.       if (nodes.isEmpty())
  29.         return root;
    . 1point 3acres 璁哄潧
  30.     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.     return null;
  32.   }

  33.   public static void main(String[] args) {. From 1point 3acres bbs
  34.     Solution s = new Solution();. From 1point 3acres bbs
  35.     TreeNode tn1 = new TreeNode(1);
  36.     TreeNode tn2 = new TreeNode(2);. From 1point 3acres bbs
  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;
    .1point3acres缃
  44.     tn2.right = tn4;
  45.     tn5.left = tn6;
  46.     tn5.right = tn7;
  47.     Set<TreeNode> set1 = new HashSet<>();
  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);. From 1point 3acres bbs
  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. }
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 09:34:28 | 显示全部楼层
import java.util.*;
import common.*;

public class Solution {
    public static TreeNode findRoot(Set<TreeNode> set, int count) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        if(set.size() == 0) {
            return null;
        }
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        // If there are only one TreeNode left, return it
        if(set.size() == 1) {
            return set.iterator().next();
        }. 1point 3acres 璁哄潧

        // 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<>();. Waral 鍗氬鏈夋洿澶氭枃绔,
        for (TreeNode treeNode : set) {
            if(!treeNode.visited) {
                queue.offer(treeNode);
                break;
            }
        }
        
        // bfs traverse
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();.鐣欏璁哄潧-涓浜-涓夊垎鍦
            node.visited = true;
            count--;.1point3acres缃

            if(node.left != null) {
                if(set.contains(node.left)) {
                    set.remove(node.left);
                    if(!node.left.visited) {
                        queue.offer(node.left);
                    }
                } else {
                    return null;
                }
            }
-google 1point3acres
            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;
                }
            }
        }

        return findRoot(set, count);
    }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}
回复 支持 反对

使用道具 举报

 楼主| lotustree86 发表于 2016-3-2 09:34:45 | 显示全部楼层
singku 发表于 2016-3-2 09:07
第二题,楼主 如果第一个找到的就是叶子节点,或者在遍历的时候,找到的一个节点,其下层的节点都被处理完 ...
. 1point3acres.com/bbs
我把代码贴出来了
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

 楼主| 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.
如果只有一个,从这个 ...

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

使用道具 举报

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;
  6.     for (TreeNode node : new HashSet<>(set)) {
  7.         if (set.contains(node)) {
  8.             root = node;
  9.             // dfs
  10.             Stack<TreeNode> stack = new Stack<>();
  11.             stack.push(root);
  12.             while (!stack.isEmpty()) {
  13.                 TreeNode current = stack.pop();. visit 1point3acres.com for more.
  14.                 if (current != root) {
  15.                     set.remove(current);. more info on 1point3acres.com
  16.                 }
  17.                 if (current.left != null) {
  18.                     stack.push(current.left);
  19.                 }
  20.                 if (current.right != null) {. 1point 3acres 璁哄潧
  21.                     stack.push(current.right);. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                 }
  23.             }
  24.         }
  25.     }

  26.     if (set.size() > 1) {
  27.         return null;
  28.     }
  29.     return root;
  30. }
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

sjph 发表于 2016-7-31 17:44:02 | 显示全部楼层
tldxk 发表于 2016-3-12 10:26
楼主为什么要用count呢?还是说给定的参数就有count?求检查下我的代码:

请问楼上做法,这个没有判断是否为BST吧?包括大家的做法,都没看出在哪里判断是BST了。抱歉,求讲解!
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-24 05:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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