优化Leaper图算法？

Question

在与Google进行的45分钟技术访谈中,我被问到了Leaper Graph问题.我编写了工作代码,但后来拒绝了工作机会,因为我缺乏数据结构知识.我想知道我能做得更好.

问题如下:"给定一个N尺寸的板,并告诉一件可以水平(左或右)和j垂直(向上或向下)的位置(即,有点像国际象棋中的马),可以电路板上的每个地方到达哪个？"

我写了以下算法.它递归地通过标记图表上访问过的所有点来查明板上的每个位置是否可达.如果无法访问,则至少有一个字段为false,该函数将返回false.

      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的联合实施: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;
        }
      }

Answer 1

我问了很多这样的面试问题。我不认为你会在面试过程中弄清楚 coprime 方法，但我会因为你使用 O(n^2) 堆栈空间而对你进行对接——特别是因为你将所有这些参数传递给每个递归调用而不是使用一个对象。

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

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

如果你真的很优秀，我会问你是否可以利用问题的对称性来减少你的搜索空间。您实际上只需要搜索 J*J 大小的网格（假设 J>=i）。

重要的是要记住，面试官不仅仅看你的答案。他关注的是你解决问题的方式，以及你大脑中拥有哪些可以用来解决问题的工具。

编辑：再考虑一下，在实现 coprime 方法的过程中，您可能还会想到很多增量步骤。没有人会想到这一点，但这将令人印象深刻！