Алгоритм оптимизации алгоритма?

Question

Во время 45-минутного технического интервью с Google мне задали проблему с графиком Leaper. Я написал рабочий код, но позже был отклонен предложение о работе, потому что мне не хватало данных о структуре данных. Мне интересно, что я мог бы сделать лучше.

Проблема была следующая: «Учитывая размерную доску N, и сказал, что кусок может прыгать i позиционируется горизонтально (влево или вправо) и j позиционируется вертикально (вверх или вниз) (Т.е., вроде как лошадь в шахматы), может ли лебедь дойти до каждого места на доске?

Я написал следующий алгоритм. Он рекурсивно обнаруживает, что каждая позиция на доске достижима, отмечая все точки на графике, которые были посещены. Если это невозможно, то по крайней мере одно поле было ложным, и функция вернет 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; 
     } 
     } 

Теперь, позже было отмечено, что оптимальным решением было бы реализовать сотрудничество премьер реализации Дональда Кнута: http://arxiv.org/pdf/math/9411240v1.pdf это то, что один должен быть в состоянии выяснить, на 45-й минуте технического интервью? ?

Помимо вышеизложенного, есть ли что-нибудь, что я мог бы сделать лучше?

Редактировать:
- Я задал вопрос о стартовой позиции. Мне сказали, что начинать с 0,0 хорошо.

edit2 Основываясь на обратной связи, я написал цикл while с подходом к очереди. Рекурсивный подход работает в переполнении стека при n = 85. Однако цикл while с методом очереди ниже ~ n = 30 000. (после этого он сталкивается с проблемами кучи с памятью, превышающей ГБ). Если вы знаете, как оптимизировать дальше, пожалуйста, дайте мне знать.

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

Я задаю много вопросов для интервью, подобных этому. Я не думаю, что вы ожидали, что в ходе собеседования выясните метод взаимного использования, но я бы закрепил вас за использование пространства стека O (n^2) - тем более, что вы передали все эти параметры для каждого рекурсивного вызова вместо используя объект.

Я бы спросил вас об этом и ожидал, что вы придумаете BFS или DFS, используя стек или очередь в куче. Если вы потерпите неудачу в этом, у меня может появиться такая жалоба, как «отсутствие знаний о структуре данных».

Я также задал бы вопросы, чтобы убедиться, что вы знали, что делаете, когда вы выделили этот 2D-массив.

Если бы вы были действительно хороши, я бы спросил вас, можете ли вы использовать симметрию проблемы, чтобы сократить пространство поиска. Вам действительно нужно только искать сетку размера J * J (при условии, что J> = i).

Важно помнить, что интервьюер не просто смотрит на ваш ответ. Он смотрит на то, как вы решаете проблемы и какие инструменты у вас в мозгу, которые вы можете принести на решение.

Редактировать: думая об этом еще немного, есть много дополнительных шагов на пути к совместному методу, который вы также можете придумать. Никто не будет этого ожидать, но это будет впечатляюще!

Answer 2

Извините, я чувствую, что у меня что-то не хватает.

Если вы можете двигаться вверх или вниз по i, а слева или справа - j, тогда случай (x, y) возможен из стартового примера (a, b), если существуют целые числа m и n, так что

а + т * я = х

б + п * у = у

То есть, все ложно для квадратной доске, где п> 1.

Если вы означало больше как рыцарь в c hess, и вы можете перейти вверх/вниз на i и влево/вправо на j OR вверх/вниз на j и слева/справа на i, вы можете использовать ту же технику. Он просто становится 2 уравнений, чтобы решить:

а + т * г + п * у = х

б + о * я + р * у = у

Если есть нет целые числа m, n, o и p, которые удовлетворяют этим уравнениям, вы не можете достичь этого.