02/09 F家onsite面经

地里的面经帮助很大。面完了onsite来发一个Facebook的面经，回报地里。
一面：给一个board，上面有0 和1，1不

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

#05580">和判断一个树是不是另一个树的子树。

一面

1. public class Solution {
   
2.   public int minsteps(int board[][], int starti, int startj, int endi, int endj) {
   
3.     int dirs[][] = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
   
4.     int m = board.length;
   
5.     int n = board[0].length;
   
6. 
   
7.     boolean visited[][] = new boolean[m][n];
   
8.     Deque<int[]> queue = new ArrayDeque<>(); // bfs
   
9. 
   
10.     queue.offer(new int[] {starti, startj});
    
11.     visited[starti][startj] = true;
    
12. 
    
13.     int level = 0;
    
14.     while (!queue.isEmpty()) {
    
15.       level++;
    
16.       int count = queue.size();
    
17.       for (int i = 0; i < count; i++) {
    
18.         int[] node = queue.poll();
    
19.         for (int[] dir : dirs) {
    
20.           int x = node[0] + dir[0];
    
21.           int y = node[1] + dir[1];
    
22.           if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != 1 && !visited[x][y]) {
    
23.             if (x == endi && y == endj) {
    
24.               return level;
    
25.             }
    
26.             queue.offer(new int[] {x, y});
    
27.             visited[x][y] = true;
    
28.           }
    
29.         }
    
30.       }
    
31.     }
    
32.     return -1;
    
33.   }
    
34. 
    
35.   public List<int[]> minpath(int board[][], int starti, int startj, int endi, int endj) {
    
36.     int dirs[][] = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
37.     int m = board.length;
    
38.     int n = board[0].length;
    
39. 
    
40.     Map<Integer, Integer> parent = new HashMap<>(); // int[] cannot equals
    
41.     boolean visited[][] = new boolean[m][n];
    
42.     Deque<int[]> queue = new ArrayDeque<>(); // bfs
    
43. 
    
44.     queue.offer(new int[] {starti, startj});
    
45.     visited[starti][startj] = true;
    
46. 
    
47.     while (!queue.isEmpty()) {
    
48.       int count = queue.size();
    
49.       for (int i = 0; i < count; i++) {
    
50.         int[] node = queue.poll();
    
51.         for (int[] dir : dirs) {
    
52.           int x = node[0] + dir[0];
    
53.           int y = node[1] + dir[1];
    
54.           if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != 1 && !visited[x][y]) {
    
55.             queue.offer(new int[] {x, y});
    
56.             visited[x][y] = true;
    
57.             parent.put(x * n + y, node[0] * n + node[1]);
    
58.             if (x == endi && y == endj) {
    
59.               LinkedList<int[]> ret = new LinkedList<>();
    
60.               while (x * n + y != starti * n + startj) {
    
61.                 ret.offerFirst(new int[] {x, y});
    
62.                 int p = parent.get(x * n + y);
    
63.                 x = p / n;
    
64.                 y = p % n;
    
65.               }
    
66.               return ret;
    
67.             }
    
68.           }
    
69.         }
    
70.       }
    
71.     }
    
72.     return null;
    
73.   }
    
74. 
    
75.   public static void main(String[] args) {
    
76.     Solution s = new Solution();
    
77.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));
    
78.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1));
    
79.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2));
    
80.     System.out.println();
    
81. 
    
82.     System.out.println(s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));
    
83.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1))
    
84.       System.out.print("(" + t[0] + "," + t[1] + ") ");
    
85.     System.out.println();
    
86.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2))
    
87.       System.out.print("(" + t[0] + "," + t[1] + ") ");
    
88.     System.out.println();
    
89.   }
    
90. }
    

复制代码

补充内容 (2016-4-18 15:55):
二面，
    int dirs[][] = // 马走日
        new int[][] {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};

三面

1. public class Solution {
   
2.   boolean issametree(TreeNode root1, TreeNode root2) {
   
3.     if (root1 == null && root2 == null)
   
4.       return true;
   
5.     if (root1 != null && root2 != null) {
   
6.       return root1.val == root2.val && issametree(root1.left, root2.left)
   
7.           && issametree(root1.right, root2.right);
   
8.     }
   
9.     return false;
   
10.   }
    
11. 
    
12.   public boolean issubtree(TreeNode big, TreeNode small) {
    
13.     if (big != null && small != null) {
    
14.       if (big.val == small.val) {
    
15.         if (issametree(big, small))
    
16.           return true;
    
17.       } else {
    
18.         if (big.left != null && issubtree(big.left, small)) {
    
19.           return true;
    
20.         }
    
21.         if (big.right != null && issubtree(big.right, small)) {
    
22.           return true;
    
23.         }
    
24.       }
    
25.     }
    
26.     return false;
    
27.   }
    
28. 
    
29. 
    
30.   public static void main(String[] args) {
    
31.     Solution s = new Solution();
    
32.     TreeNode tn1 = new TreeNode(1);
    
33.     TreeNode tn2 = new TreeNode(2);
    
34.     TreeNode tn3 = new TreeNode(3);
    
35.     TreeNode tn4 = new TreeNode(4);
    
36.     TreeNode tn5 = new TreeNode(5);
    
37.     tn1.left = tn2;
    
38.     tn1.right = tn3;
    
39.     tn4.left = tn5;
    
40.     System.out.println(s.issubtree(tn1, tn2));
    
41.     System.out.println(s.issubtree(tn1, tn4));
    
42.   }
    
43. }
    

复制代码

sealove999 发表于 2016-4-18 15:51
一面

如果只是把directions换成日字形走法的话万一中间走过的点有1怎么办，那样就不能走到那个点了。而且还得考虑[-1, 0]这种横向走一步，纵向来回走两步的情况，那样directions矩阵就有很多情况了。

卧槽。。。妥妥的offer啊

lz能稍微说下判断一个树是不是另一个树的子树的那个题吗？是给一个subtree的root然后判断这个root在不在大树的里面，还是要检查大树里面的那个子树和另一个树所有的node都一样才行？

iwofr 发表于 2016-2-19 01:34
lz能稍微说下判断一个树是不是另一个树的子树的那个题吗？是给一个subtree的root然后判断这个root在不在大 ...

直接给了一个子树，问这个子树存在于大的数与否。不需要大树要到leaves。

FB又开始招fulltime了嘛

NR21 发表于 2016-2-19 02:43
直接给了一个子树，问这个子树存在于大的数与否。不需要大树要到leaves。

是在大树里面找到和小树root value一样的node然后check isSameTree吗？

iwofr 发表于 2016-2-19 03:36
是在大树里面找到和小树root value一样的node然后check isSameTree吗？

是的字数字数

silenceleaf 发表于 2016-2-19 02:53
FB又开始招fulltime了嘛

貌似是的呢

NR21 发表于 2016-2-19 04:04
是的字数字数

谢谢！祝好运啊！我也马上onsite 了！求好运！

LZ onsite 只有三轮吗？