一亩三分地论坛

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

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

02/09 F家onsite面经

[复制链接] |试试Instant~ |关注本帖
NR21 发表于 2016-2-19 00:42:07 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Facebook - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
地里的面经帮助很大。面完了onsite来发一个Facebook的面经,回报地里。
一面:给一个board,上面有0 和1,1不可以走,0 可以走。任意给一个start一个end,让输出最短的步数。follow up输出路径。就是BFS
二面:BST的Binary Tree Level Order Traversal。 还有和一面类似,但是每次都是可以纵向两步横向一步,或者横向一步纵向两部,问步数和路径。
三面:Minimum Window Substring和判断一个树是不是另一个树的子树。


. From 1point 3acres bbs

本帖被以下淘专辑推荐:

kidzlike 发表于 2016-2-19 00:49:09 | 显示全部楼层
卧槽。。。妥妥的offer啊
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-19 01:34:31 | 显示全部楼层
lz能稍微说下判断一个树是不是另一个树的子树的那个题吗?是给一个subtree的root然后判断这个root在不在大树的里面,还是要检查大树里面的那个子树和另一个树所有的node都一样才行?
回复 支持 反对

使用道具 举报

 楼主| NR21 发表于 2016-2-19 02:43:30 | 显示全部楼层
iwofr 发表于 2016-2-19 01:34
lz能稍微说下判断一个树是不是另一个树的子树的那个题吗?是给一个subtree的root然后判断这个root在不在大 ...

. 1point 3acres 璁哄潧直接给了一个子树,问这个子树存在于大的数与否。不需要大树要到leaves。
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2016-2-19 02:53:59 | 显示全部楼层
FB又开始招fulltime了嘛
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-19 03:36:22 | 显示全部楼层
NR21 发表于 2016-2-19 02:43. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
直接给了一个子树,问这个子树存在于大的数与否。不需要大树要到leaves。

是在大树里面找到和小树root value一样的node然后check isSameTree吗?
回复 支持 反对

使用道具 举报

 楼主| NR21 发表于 2016-2-19 04:04:35 | 显示全部楼层
iwofr 发表于 2016-2-19 03:36
是在大树里面找到和小树root value一样的node然后check isSameTree吗?

是的字数字数
回复 支持 反对

使用道具 举报

 楼主| NR21 发表于 2016-2-19 04:04:43 | 显示全部楼层
silenceleaf 发表于 2016-2-19 02:53
FB又开始招fulltime了嘛

貌似是的呢. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-19 05:06:34 | 显示全部楼层

谢谢!祝好运啊!我也马上onsite 了!求好运!
回复 支持 反对

使用道具 举报

queeniejing 发表于 2016-2-23 05:48:32 | 显示全部楼层
LZ onsite 只有三轮吗?
回复 支持 反对

使用道具 举报

 楼主| NR21 发表于 2016-2-23 23:57:38 | 显示全部楼层
queeniejing 发表于 2016-2-23 05:48
LZ onsite 只有三轮吗?

是的,貌似new grad都是三轮。
回复 支持 反对

使用道具 举报

新垣瞳澈 发表于 2016-2-24 01:47:28 | 显示全部楼层
LZ是哪天面的啊?已经出结果了?谢谢
回复 支持 反对

使用道具 举报

 楼主| NR21 发表于 2016-2-24 02:10:02 | 显示全部楼层
新垣瞳澈 发表于 2016-2-24 01:47
LZ是哪天面的啊?已经出结果了?谢谢
-google 1point3acres
我是2月9号面的,一周出的结果
回复 支持 反对

使用道具 举报

Wrath 发表于 2016-4-18 04:06:40 | 显示全部楼层
LZ请问第二面的第二题应该怎么做比较好?
回复 支持 反对

使用道具 举报

jiebour 发表于 2016-4-18 05:40:04 | 显示全部楼层
楼主new grad?感觉题目简单啊。。。。另外楼主面之前有没有收到prep metairial 的pdf?比如告诉你会问哪些东西,algorithm,data structure,design pattern?有提到system design嘛?
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-4-18 15:51:54 | 显示全部楼层
一面
  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.     boolean visited[][] = new boolean[m][n];
  7.     Deque<int[]> queue = new ArrayDeque<>(); // bfs

  8.     queue.offer(new int[] {starti, startj});
  9.     visited[starti][startj] = true;. more info on 1point3acres.com

  10.     int level = 0;
  11.     while (!queue.isEmpty()) {
  12.       level++;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  13.       int count = queue.size();
  14.       for (int i = 0; i < count; i++) {
  15.         int[] node = queue.poll();
  16.         for (int[] dir : dirs) {
  17.           int x = node[0] + dir[0];
  18.           int y = node[1] + dir[1];
  19.           if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != 1 && !visited[x][y]) {
  20.             if (x == endi && y == endj) {
  21.               return level;
  22.             }
  23.             queue.offer(new int[] {x, y});
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.             visited[x][y] = true;
  25.           } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  26.         }
  27.       }
  28.     } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  29.     return -1;
  30.   }

  31.   public List<int[]> minpath(int board[][], int starti, int startj, int endi, int endj) {
  32.     int dirs[][] = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  33.     int m = board.length;
  34.     int n = board[0].length;

  35.     Map<Integer, Integer> parent = new HashMap<>(); // int[] cannot equals
  36.     boolean visited[][] = new boolean[m][n];
  37.     Deque<int[]> queue = new ArrayDeque<>(); // bfs
  38. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  39.     queue.offer(new int[] {starti, startj});
  40.     visited[starti][startj] = true;

  41.     while (!queue.isEmpty()) {
  42.       int count = queue.size();
  43.       for (int i = 0; i < count; i++) {
  44.         int[] node = queue.poll();
  45.         for (int[] dir : dirs) {
  46.           int x = node[0] + dir[0];. more info on 1point3acres.com
  47.           int y = node[1] + dir[1];
  48.           if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != 1 && !visited[x][y]) {
  49.             queue.offer(new int[] {x, y});
  50.             visited[x][y] = true;
  51.             parent.put(x * n + y, node[0] * n + node[1]);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  52.             if (x == endi && y == endj) {
  53.               LinkedList<int[]> ret = new LinkedList<>();
  54.               while (x * n + y != starti * n + startj) {
  55.                 ret.offerFirst(new int[] {x, y});
  56.                 int p = parent.get(x * n + y);
    -google 1point3acres
  57.                 x = p / n;. visit 1point3acres.com for more.
  58.                 y = p % n;
  59.               }
  60.               return ret;
  61.             }
  62.           }
  63.         }. visit 1point3acres.com for more.
  64.       }
  65.     }
  66.     return null;
  67.   }

  68.   public static void main(String[] args) {
  69.     Solution s = new Solution();
  70.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  71.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1));. more info on 1point3acres.com
  72.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2));. 鍥磋鎴戜滑@1point 3 acres
  73.     System.out.println();

  74.     System.out.println(s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  75.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1))
  76.       System.out.print("(" + t[0] + "," + t[1] + ") ");. 1point3acres.com/bbs
  77.     System.out.println();
  78.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2))
  79.       System.out.print("(" + t[0] + "," + t[1] + ") ");
    . from: 1point3acres.com/bbs
  80.     System.out.println();
  81.   }
  82. }
复制代码

补充内容 (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}};
回复 支持 反对

使用道具 举报

sealove999 发表于 2016-4-18 16:06:20 | 显示全部楼层
三面
  1. public class Solution {
  2.   boolean issametree(TreeNode root1, TreeNode root2) {
  3.     if (root1 == null && root2 == null). 1point3acres.com/bbs
  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);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  8.     }
  9.     return false;
  10.   }

  11.   public boolean issubtree(TreeNode big, TreeNode small) {
  12.     if (big != null && small != null) {
  13.       if (big.val == small.val) {
  14.         if (issametree(big, small))
  15.           return true;
  16.       } else {
  17.         if (big.left != null && issubtree(big.left, small)) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  18.           return true;
  19.         }
  20.         if (big.right != null && issubtree(big.right, small)) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.           return true;
  22.         }
  23.       }
  24.     }
  25.     return false;
  26.   }


  27.   public static void main(String[] args) {
  28.     Solution s = new Solution();
  29.     TreeNode tn1 = new TreeNode(1);. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  30.     TreeNode tn2 = new TreeNode(2);
  31.     TreeNode tn3 = new TreeNode(3);
  32.     TreeNode tn4 = new TreeNode(4);
  33.     TreeNode tn5 = new TreeNode(5);
  34.     tn1.left = tn2;
  35.     tn1.right = tn3;
  36.     tn4.left = tn5;
  37.     System.out.println(s.issubtree(tn1, tn2));
  38.     System.out.println(s.issubtree(tn1, tn4)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  39.   }. more info on 1point3acres.com
  40. }
复制代码
回复 支持 反对

使用道具 举报

Wrath 发表于 2016-4-21 06:26:15 | 显示全部楼层

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

使用道具 举报

sealove999 发表于 2016-4-23 07:31:08 | 显示全部楼层
Wrath 发表于 2016-4-21 06:26
如果只是把directions换成日字形走法的话万一中间走过的点有1怎么办,那样就不能走到那个点了。而且还得 ...

噢噢噢噢是喔是喔
回复 支持 反对

使用道具 举报

zzx04025 发表于 2016-4-24 18:27:02 | 显示全部楼层
请问LZ第一题可以用DP做么,为什么我第一反应是DP呢……
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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