一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2522|回复: 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. 1point3acres.com/bbs
Example:
Nodes : (Node1, Node 2)
Tree structre:
   Node1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
/
Node2

In this case, return Node1.-google 1point3acres
Nodes : (Node1, Node 2)
Tree structre:
   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 {
  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.       }.1point3acres缃
  11.     }
  12.     for (TreeNode root : candidate) {
  13.       Set<TreeNode> nodes = new HashSet<>(set);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.       Deque<TreeNode> queue = new ArrayDeque<>();. more info on 1point3acres.com
  15.       queue.offer(root);
  16.       nodes.remove(root);
    . from: 1point3acres.com/bbs
  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.         }
  23.         if (tn.right != null) {
  24.           queue.offer(tn.right);. from: 1point3acres.com/bbs
  25.           nodes.remove(tn.right);
  26.         }
  27.       }
  28.       if (nodes.isEmpty())
  29.         return root;
  30.     }
  31.     return null;.1point3acres缃
  32.   }
  33. . Waral 鍗氬鏈夋洿澶氭枃绔,
  34.   public static void main(String[] args) {
  35.     Solution s = new Solution();
  36.     TreeNode tn1 = new TreeNode(1);
  37.     TreeNode tn2 = new TreeNode(2);
  38.     TreeNode tn3 = new TreeNode(3);
  39.     TreeNode tn4 = new TreeNode(4);. From 1point 3acres bbs
  40.     TreeNode tn5 = new TreeNode(5);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  41.     TreeNode tn6 = new TreeNode(6);. 1point 3acres 璁哄潧
  42.     TreeNode tn7 = new TreeNode(7);
  43.     tn1.left = tn2;
    . visit 1point3acres.com for more.
  44.     tn1.right = tn3;
  45.     tn2.right = tn4;
  46.     tn5.left = tn6;
  47.     tn5.right = tn7;
  48.     Set<TreeNode> set1 = new HashSet<>();. 鍥磋鎴戜滑@1point 3 acres
  49.     set1.add(tn1);
  50.     set1.add(tn2);
  51.     set1.add(tn3);
  52.     set1.add(tn4);
  53.     Set<TreeNode> set2 = new HashSet<>();. visit 1point3acres.com for more.
  54.     set2.add(tn1);
  55.     set2.add(tn2);
  56.     set2.add(tn3);
  57.     set2.add(tn4);.1point3acres缃
  58.     set2.add(tn5);
  59.     set2.add(tn6);
  60.     set2.add(tn7);
  61.     System.out.println(s.onetree(set1).equals(tn1));
  62.     System.out.println(s.onetree(set2) == null);
  63.   }
  64. }
复制代码
回复 支持 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) {.1point3acres缃
        if(set.size() == 0) {
            return null;. from: 1point3acres.com/bbs
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

        // 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) {
                queue.offer(treeNode);
                break;
            }
        }
        .鐣欏璁哄潧-涓浜-涓夊垎鍦
        // bfs traverse
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            node.visited = true;. 鍥磋鎴戜滑@1point 3 acres
            count--;

            if(node.left != null) {. 鍥磋鎴戜滑@1point 3 acres
                if(set.contains(node.left)) {
. 1point3acres.com/bbs                    set.remove(node.left);
                    if(!node.left.visited) {
                        queue.offer(node.left);
                    }
                } else {
                    return null;
                }. 鍥磋鎴戜滑@1point 3 acres
            }
. 鍥磋鎴戜滑@1point 3 acres
            if(node.right != null && !node.right.visited) {
                if(set.contains(node.right)) {
                    set.remove(node.right);. from: 1point3acres.com/bbs
                    if(!node.right.visited) {. visit 1point3acres.com for more.
                        queue.offer(node.right);
                    }. 1point3acres.com/bbs
                } else {. from: 1point3acres.com/bbs
                    return null;
                }
            }
        }

        return findRoot(set, count);
    }. 1point 3acres 璁哄潧
}
回复 支持 反对

使用道具 举报

 楼主| 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颗树的节点组成的集合,顺序是乱的,但是每个节点还是保留原来左右子节点的信息的,让你判断这些节点是不是来自同一颗二叉树,并且也不任何节点,并返还跟节点。
回复 支持 反对

使用道具 举报

 楼主| 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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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()) {. 1point 3acres 璁哄潧
  13.                 TreeNode current = stack.pop();
  14.                 if (current != root) {
  15.                     set.remove(current);
  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. . more info on 1point3acres.com
  27.     if (set.size() > 1) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.         return null;
  29.     }
  30.     return root;
    . From 1point 3acres bbs
  31. }
复制代码
回复 支持 反对

使用道具 举报

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, 2016-12-7 17:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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