到底为啥那么多人转Data Science

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
[Google级团队]
实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5408|回复: 21
收起左侧

02/09 F家onsite面经

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

2015(1-3月) 码农类General 硕士 全职@Facebook - 内推 - Onsite  | Other | fresh 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和判断一个树是不是另一个树的子树。
.1point3acres缃

本帖被以下淘专辑推荐:

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吗?

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

使用道具 举报

 楼主| 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. 鍥磋鎴戜滑@1point 3 acres
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) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.     int level = 0;. 1point 3acres 璁哄潧
  11.     while (!queue.isEmpty()) {
  12.       level++;
  13.       int count = queue.size();
  14.       for (int i = 0; i < count; i++) {. more info on 1point3acres.com
  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});. from: 1point3acres.com/bbs
  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) {.1point3acres缃
  32.     int dirs[][] = new int[][] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};. Waral 鍗氬鏈夋洿澶氭枃绔,
  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. . visit 1point3acres.com for more.
  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++) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  44.         int[] node = queue.poll();
  45.         for (int[] dir : dirs) {
  46.           int x = node[0] + dir[0];
  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]);
  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);
  57.                 x = p / n;
  58.                 y = p % n;
  59.               }
  60.               return ret;
  61.             }
  62.           }
  63.         }
  64.       }
  65.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  66.     return null;
  67.   }
  68. . from: 1point3acres.com/bbs
  69.   public static void main(String[] args) {. from: 1point3acres.com/bbs
  70.     Solution s = new Solution();
  71.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));
  72.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1));
    . 1point 3acres 璁哄潧
  73.     System.out.println(s.minsteps(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2));. From 1point 3acres bbs
  74.     System.out.println();

  75.     System.out.println(s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 1, 1));
  76.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 1))
  77.       System.out.print("(" + t[0] + "," + t[1] + ") ");
  78.     System.out.println();
  79.     for (int[] t : s.minpath(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 1, 2, 2))
  80.       System.out.print("(" + t[0] + "," + t[1] + ") ");
  81.     System.out.println();
  82.   }
  83. }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
复制代码

补充内容 (2016-4-18 15:55):
二面,. more info on 1point3acres.com
    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);.1point3acres缃
  8.     }
  9.     return false;
  10.   }
  11. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.       }
  25.     }
  26.     return false;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.   }


  28.   public static void main(String[] args) {
  29.     Solution s = new Solution();
  30.     TreeNode tn1 = new TreeNode(1);
  31.     TreeNode tn2 = new TreeNode(2);
  32.     TreeNode tn3 = new TreeNode(3);
  33.     TreeNode tn4 = new TreeNode(4);
  34.     TreeNode tn5 = new TreeNode(5);
  35.     tn1.left = tn2;. 1point3acres.com/bbs
  36.     tn1.right = tn3;
  37.     tn4.left = tn5;-google 1point3acres
  38.     System.out.println(s.issubtree(tn1, tn2));. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  39.     System.out.println(s.issubtree(tn1, tn4));
  40.   }
  41. }
复制代码
回复 支持 反对

使用道具 举报

Wrath 发表于 2016-4-21 06:26:15 | 显示全部楼层
. 1point3acres.com/bbs
如果只是把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呢……
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-26 00:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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