7

在 Google 的 45 分钟技术面试中，我被问到一个 Leaper Graph 问题。我编写了工作代码，但后来因为缺乏数据结构知识而被拒绝了工作机会。我想知道我本可以做得更好。

问题如下：“给定一个 N 大小的棋盘，并告诉棋子可以水平跳 i 个位置（左或右）和垂直跳 j 个位置（上或下）（即，有点像国际象棋中的一匹马），可以跳投者能到达棋盘上的每一个位置吗？”

我写了以下算法。它通过标记图上所有被访问的点来递归地确定棋盘上的每个位置是否都可以到达。如果它不可达，那么至少有一个字段为假，该函数将返回假。

      static boolean reachable(int i, int j, int n) {
        boolean grid[][] = new boolean[n][n];
        reachableHelper(0, 0, grid, i, j, n - 1);
        for (int x = 0; x < n; x++) {
          for (int y = 0; y < n; y++) {
            if (!grid[x][y]) {
              return false;
            }
          }
        }
        return true;
      }

      static void reachableHelper(int x, int y, boolean[][] grid, int i, int j, int max) {
        if (x > max || y > max || x < 0 || y < 0 || grid[x][y]) {
          return;
        }
        grid[x][y] = true;
        int i2 = i;
        int j2 = j;
        for (int a = 0; a < 2; a++) {
          for (int b = 0; b < 2; b++) {
            reachableHelper(x + i2, y + j2, grid, i, j, max);
            reachableHelper(x + j2, y + i2, grid, i, j, max);
            i2 = -i2;
          }
          j2 = -j2;
        }
      }

现在，后来有人指出，最佳解决方案是实施 Donald Knuth 的 co-prime 实施： http ://arxiv.org/pdf/math/9411240v1.pdf 这是一个应该能够弄清楚的事情吗？ 45分钟的技术面试？？

除了上述之外，还有什么我可以做得更好的吗？

编辑：
-我询问了起始位置。有人告诉我从 0,0 开始就可以了。

edit2 根据反馈，我写了一个带有队列方法的while循环。当 n = 85 时，递归方法会遇到堆栈溢出。但是，使用下面的队列方法的 while 循环可以达到 ~n = 30,000。（之后它会遇到内存超过 GB 的堆问题）。如果您知道如何进一步优化，请告诉我。

    static boolean isReachableLoop(int i, int j, int n) {
        boolean [][] grid = new boolean [n][n];

        LinkedList<Point> queue = new LinkedList<Point>();
        queue.add(new Point(0,0)); // starting position. 

        int nodesVisited = 0;
        while (queue.size() != 0) {
          Point pos = queue.removeFirst();

          if (pos.x >= 0 &&  pos.y >= 0 && pos.x < n && pos.y < n) {
            if (!grid[pos.x][pos.y]) {
              grid[pos.x][pos.y] = true;
              nodesVisited++;
              int i2 = i;
              int j2 = j;
              for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                  queue.add(new Point(pos.x+i2, pos.y+j2));
                  queue.add(new Point(pos.x+j2, pos.y+i2));
                  i2 = -i2;
                }
                j2 = -j2;
              }
            }
          }
        }
        if (nodesVisited == (n * n)) {
          return true;
        } else {
          return false;
        }
      }
4

2 回答 2

3

我问了很多这样的面试问题。我不认为你会被期望在面试期间弄清楚 coprime 方法，但我会因为使用 O(n^2) 堆栈空间而让你停下来 - 特别是因为你将所有这些参数传递给每个递归调用而不是使用一个对象。

我会问你这个问题，并希望你使用堆上的堆栈或队列来提出 BFS 或 DFS。如果你失败了，我可能会抱怨“缺乏数据结构知识”。

我还会问一些问题，以确保您在分配该 2D 数组时知道自己在做什么。

如果你真的很好，我会问你是否可以使用问题的对称性来减少搜索空间。你真的只需要搜索一个 J*J 大小的网格（假设 J>=i）。

重要的是要记住，面试官不仅仅是在看你的答案。他正在研究您解决问题的方式以及您大脑中可以用来解决问题的工具。

编辑：再想一想，在通往互质方法的路上有很多增量步骤，您可能还会想出。没有人会想到这一点，但它会令人印象深刻！

于 2015-11-21T04:11:47.160 回答
2

对不起，我觉得我错过了什么。

如果你只能向上或向下 i 和 j 向左或向右，那么如果存在整数 m 和 n，则可以从起始案例 (a,b) 到达案例 (x,y) 使得

a + m*i = x

b + n*j = y

也就是说，对于 n > 1 的方板，一切都是错误的。

如果您的意思更像是国际象棋中的骑士，并且您可以通过 i 上/下和 j 左/右或 j 上/下和 i 左/右上/下，您可以使用相同的技术。它只是变成2个方程来解决：

a + m * i + n * j = x

b + o * i + p * j = y

如果没有满足这些方程的整数 m、n、o 和 p，你就无法达到那个点。

于 2015-11-20T23:20:39.163 回答