脸家5月初昂赛面经

第一轮聊职场聊人生。
第二轮：
1. Union of intervals:

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

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

2. 在grid中找最左侧的1

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

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

第三轮：
手机按键上跑国际象棋的马

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

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

第四轮：
系统设计points of interests

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

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

第五轮：
系统设计design Instagram

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

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

选择了狗家offer。

AnthonyNeu 发表于 2018-6-10 01:02
**** 本内容被作者隐藏 ****

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

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

请教一下楼主第三轮是怎么写的dfs/bfs。 bfs没想到不是exponential cost的方法。只会写地下dp的方法。请楼主指教
public int possibleWays(int[][] chessBoard, int n) {
      int r = chessBoard.length, c = chessBoard[0].length;
      int[][] visited0 = new int[r][c];
      int[][] visited1 = new int[r][c];
      visited0[0][0] = 1;
      int[][] dir = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1}，{-1, -2}, {-2, -1}, {1, -2}, {2, -1}};
      for (int ind = 0; ind < n; ind++) {
          for (int i = 0; i < r; i++) {
              for (int j = 0; j < c; j++) {
                  int cur = 0;
                  for (int[] d : dir) {
                      int x = d[0] + i;
                      int y = d[1] + j;
                      if (x >= 0 && y >= 0 && x < r && y < c) {
                          cur += visited0[x][y];
                      }
                  }
                  visted1[i][j] = cur;
              }
          }
          int[][] tmp = visited0;
          visited0 = visited1;
          visited1 = tmp;
      }
      int tot = 0;
      for (int[] a: visited0) {
          for (int b: b) {
              tot += b;
          }
      }
    return tot;
  }

serpheroth1 发表于 2018-6-14 08:53
请教一下楼主第三轮是怎么写的dfs/bfs。 bfs没想到不是exponential cost的方法。只会写地下dp的方法。请楼 ...

dfs的情况，每个小的subproblem相当于以i为起点跳k步总共有多少种路径，然后recursion下去，返回的结果是每个subproblem的步数。由于这个过程中会有大量重复出现的subproblem，所以其实是可以记录下来的，所以后续的recursion如果遇到相同的subproblem，可以直接读取之前计算的结果。

bfs感觉写这道题比较别扭，k-1步的好几个点在第k步时都可以跳到i点，所以这些能跳到i点的路径信息可以合并，相当于剪枝。合并后总路径的数量相当于之前k-1步各个源分支的数量。

上面dfs和bfs都不是exponential，通过剪枝使得时间复杂度维持在O(c*n)，与dp一致。

感谢分享！

请问楼主第三轮马跳的方向有限制吗？

sw7eets 发表于 2018-6-9 07:00
请问楼主第三轮马跳的方向有限制吗？

方向没有限制，只要你按照日字能跳到的地方都算是能走的路径。

狗家不是号称不考系统设计的嘛

同问，请问楼主是有几年工作经验？不是说5年工作经验以下的不考系统设计吗？

FTD2014 发表于 2018-6-9 07:30
狗家不是号称不考系统设计的嘛

狗家是不考啊。。这篇帖子说的是脸家。。

magiccaicai 发表于 2018-6-9 07:50
同问，请问楼主是有几年工作经验？不是说5年工作经验以下的不考系统设计吗？

这个是脸家的帖子啊。。

hh821758 发表于 2018-6-9 08:01
狗家是不考啊。。这篇帖子说的是脸家。。

sorrysorry, 没看清楚...

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

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