Leaper Graphアルゴリズムを最適化しますか？

Question

Googleとの45分間のテクニカルインタビューで、私はLeaper Graphの問題を尋ねられました。 私は作業コードを書いていましたが、データ構造に関する知識が不足していたため、後で求人が拒否されました。私は何ができたのだろうと思っています。

は、問題は、次の通りであった： 「Nサイズのボードを考えると、ピース、すなわち、一種の馬のように（（アップまたはダウン）、垂直（左または右）とjの位置を水平I位置をジャンプすることができると言われボード上のすべての場所に達することができますか？ "

私は以下のアルゴリズムを書いています。訪問されたグラフ上のすべての点をマーキングすることによって、ボード上のすべての位置に到達可能かどうかを再帰的に調べる。到達可能でない場合、少なくとも1つのフィールドがfalseであり、関数はfalseを返します。 http://arxiv.org/pdf/math/9411240v1.pdf は1が45分技術的なインタビューに把握することができる必要があり、このものです：

 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; 
     } 
     } 

今、後でそれが最適解はドナルド・クヌースの互いに素な実装を実装するだろうと指摘したのですか？ ？

上記以外にも、私がうまくできたことはありますか？

編集：
- 私は開始位置について尋ね。私は0,0で始まるといいといいました。

edit2 フィードバックに基づいて、whileループとキュー方式を書きました。 n = 85の場合、再帰的アプローチはスタックオーバーフローになります。 ただし、以下のwhileループを持つ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を思いつくことを期待しました。あなたがそれに失敗した場合は、「データ構造の知識が不足しています」などの苦情があります。

また、2D配列を割り当てたときに行っていたことを知っているかどうかを確認するための質問もあります。

本当にうまくいけば、問題の対称性を使って検索スペースを減らすことができるかどうか尋ねます。実際にはJ * Jサイズのグリッドを検索するだけです（J> = iと仮定します）。

インタビュアーはあなたの答えを見るだけではないことを覚えておくことが重要です。彼はあなたが問題を解決する方法と、あなたがソリューションに耐えることができるあなたの脳にどのようなツールを持っているかを見ています。

編集：このことについてもう少し考えてみましょう。あなたが思い付くかもしれないcoprimeメソッドへの道には、多くの段階的なステップがあります。誰もそれを期待しませんが、それは印象的です！

Answer 2

申し訳ありませんが、私は何かが不足しているように感じます。

jで左または右にしか移動できない場合、整数mとnがある場合は、開始ケース（a、b）からcase（x、y）に到達できます。

ある

+ mの* I = X

B + N * J = Y

は、すべてがあなたの場合はn>は1

平方ボードのための偽でありますcの騎士のようなものヘス、あなたはiで左/右、jで上下、jで上/下、iで左/右、同じテクニックを使うことができます。 iは、n個の*はJ = X

B +

+ M *が+ O * IがP * J = Y

ある場合は何を+：それだけで解決しないように2次方程式となりますこれらの式を満たす整数m、n、o、pは、その点に到達することはできません。