10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 5185|回复: 21
收起左侧

02/09 F家onsite面经

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

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

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

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

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


本帖被以下淘专辑推荐:

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在不在大 ...

直接给了一个子树,问这个子树存在于大的数与否。不需要大树要到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吗?
. more info on 1point3acres.com
是的字数字数
回复 支持 反对

使用道具 举报

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

貌似是的呢
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-19 05:06:34 | 显示全部楼层
NR21 发表于 2016-2-19 04:04-google 1point3acres
是的字数字数
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
谢谢!祝好运啊!我也马上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是哪天面的啊?已经出结果了?谢谢

我是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;
  10. . visit 1point3acres.com for more.
  11.     int level = 0;
  12.     while (!queue.isEmpty()) {. from: 1point3acres.com/bbs
  13.       level++;
  14.       int count = queue.size();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  15.       for (int i = 0; i < count; i++) {
  16.         int[] node = queue.poll();. From 1point 3acres bbs
  17.         for (int[] dir : dirs) {
  18.           int x = node[0] + dir[0];. 鍥磋鎴戜滑@1point 3 acres
  19.           int y = node[1] + dir[1];
  20.           if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != 1 && !visited[x][y]) {
  21.             if (x == endi && y == endj) {
  22.               return level;
  23.             }
  24.             queue.offer(new int[] {x, y});
  25.             visited[x][y] = true;
  26.           }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.         }
  28.       }-google 1point3acres
  29.     }
  30.     return -1;
  31.   }

  32.   public List<int[]> minpath(int board[][], int starti, int startj, int endi, int endj) {. more info on 1point3acres.com
  33.     int dirs[][] = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  34.     int m = board.length;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.     int n = board[0].length;
  36. . From 1point 3acres bbs
  37.     Map<Integer, Integer> parent = new HashMap<>(); // int[] cannot equals. visit 1point3acres.com for more.
  38.     boolean visited[][] = new boolean[m][n];
  39.     Deque<int[]> queue = new ArrayDeque<>(); // bfs

  40. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  41.     queue.offer(new int[] {starti, startj});
  42.     visited[starti][startj] = true;

  43.     while (!queue.isEmpty()) {
  44.       int count = queue.size();
  45.       for (int i = 0; i < count; i++) {
  46.         int[] node = queue.poll();
  47.         for (int[] dir : dirs) {
  48.           int x = node[0] + dir[0];
  49.           int y = node[1] + dir[1];
  50.           if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != 1 && !visited[x][y]) {
  51.             queue.offer(new int[] {x, y});
  52.             visited[x][y] = true;
  53.             parent.put(x * n + y, node[0] * n + node[1]);
  54.             if (x == endi && y == endj) {
  55.               LinkedList<int[]> ret = new LinkedList<>();
  56.               while (x * n + y != starti * n + startj) {
  57.                 ret.offerFirst(new int[] {x, y});
  58.                 int p = parent.get(x * n + y);
  59.                 x = p / n;. From 1point 3acres bbs
  60.                 y = p % n;
  61.               }
  62.               return ret;
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  63.             }
  64.           }
  65.         }
  66.       }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  67.     }
  68.     return null;
  69.   }

  70.   public static void main(String[] args) {. 1point 3acres 璁哄潧
  71.     Solution s = new Solution();
  72.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));. 1point3acres.com/bbs
  73.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1));
  74.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2));
  75.     System.out.println();

  76.     System.out.println(s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));
  77.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1))
  78.       System.out.print("(" + t[0] + "," + t[1] + ") ");
  79.     System.out.println();
  80.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2))
  81.       System.out.print("(" + t[0] + "," + t[1] + ") ");
  82.     System.out.println();
  83.   }
  84. }
复制代码

补充内容 (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).鐣欏璁哄潧-涓浜-涓夊垎鍦
  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.   public boolean issubtree(TreeNode big, TreeNode small) {
  12.     if (big != null && small != null) {
  13.       if (big.val == small.val) {. 鍥磋鎴戜滑@1point 3 acres
  14.         if (issametree(big, small)). 1point 3acres 璁哄潧
  15.           return true;
  16.       } else {
  17.         if (big.left != null && issubtree(big.left, small)) {
  18.           return true;. 1point 3acres 璁哄潧
  19.         }
  20.         if (big.right != null && issubtree(big.right, small)) {
  21.           return true;
  22.         }
  23.       }
  24.     }
  25.     return false;
  26.   }

  27. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  28.   public static void main(String[] args) {
  29.     Solution s = new Solution();. Waral 鍗氬鏈夋洿澶氭枃绔,
  30.     TreeNode tn1 = new TreeNode(1);
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  31.     TreeNode tn2 = new TreeNode(2);
  32.     TreeNode tn3 = new TreeNode(3);
    .1point3acres缃
  33.     TreeNode tn4 = new TreeNode(4);
  34.     TreeNode tn5 = new TreeNode(5);
  35.     tn1.left = tn2;
  36.     tn1.right = tn3;
  37.     tn4.left = tn5;
  38.     System.out.println(s.issubtree(tn1, tn2));
  39.     System.out.println(s.issubtree(tn1, tn4));
  40.   }
  41. }-google 1point3acres
复制代码
回复 支持 反对

使用道具 举报

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呢……
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-18 19:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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