脸家5月初昂赛面经

serpheroth1 发表于 2018-6-12 07:25
请问一下楼主第三轮可以跳到之前有跳过的点吗？返回值就是一个int就可以了是吗？

是的，来来回回跳都无所谓。就返回个数值，不需要记录路径。

哈哈哈，最后一句话是彩蛋

小鹿小鹿 发表于 2018-6-12 07:21
请问一下楼主现在fb是不是还要求bug free 才能拿到offer呢？

倾向bug free，小修改也没啥，更看重速度。fb家的算法题实现起来一般都不复杂，行数也是白板能装下的，一轮写两道题算过关，三道题strong。

hh821758 发表于 2018-6-14 00:05
倾向bug free，小修改也没啥，更看重速度。fb家的算法题实现起来一般都不复杂，行数也是白板能装下的，一 ...

谢谢楼主的回复，之前自己有练习在纸上写代码，有时候再自己走test case的时候会发现少写了一个logic，不知道这种fb是要求第一遍写出来的时候就得bug free，还是只要是自己发现改了，也没关系

我是一直没去追求完全bug free，都是边写边调整。一般来说，代码写完了在对面试官表示“我都写完了”之前，能自己找到问题修正，都算ok。

请教一下楼主第三轮是怎么写的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一致。

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

另外有个小技巧，因为你要观察的马走的范围很小，只是手机按键这10个格子，你可以用hashmap记录从一个点能跳到那些点，不需要用你的dir[][]来记录。相似问题参见leetcode上的一个手机滑屏解锁题，不记得题号了。

补充内容 (2018-6-15 06:14):
里口伞武耀

楼主好猛哦。有几年工作经验呢？