02/09 F家onsite面经

queeniejing 发表于 2016-2-23 05:48
LZ onsite 只有三轮吗？

是的，貌似new grad都是三轮。

LZ是哪天面的啊？已经出结果了？谢谢

新垣瞳澈 发表于 2016-2-24 01:47
LZ是哪天面的啊？已经出结果了？谢谢

我是2月9号面的，一周出的结果

LZ请问第二面的第二题应该怎么做比较好？

楼主new grad？感觉题目简单啊。。。。另外楼主面之前有没有收到prep metairial 的pdf？比如告诉你会问哪些东西，algorithm，data structure，design pattern？有提到system design嘛？

一面

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矩阵就有很多情况了。

Wrath 发表于 2016-4-21 06:26
如果只是把directions换成日字形走法的话万一中间走过的点有1怎么办，那样就不能走到那个点了。而且还得 ...

噢噢噢噢是喔是喔

请问LZ第一题可以用DP做么，为什么我第一反应是DP呢……