Ottimizza algoritmo Leaper Graph?

Question

Durante un colloquio tecnico di 45 minuti con Google, mi è stato chiesto un problema con Leaper Graph. Ho scritto codice di lavoro, ma in seguito ho rifiutato l'offerta di lavoro perché mi mancava la conoscenza della struttura dei dati. Mi sto chiedendo cosa avrei potuto fare meglio.

Il problema era come segue: "Dato un bordo di dimensioni N, e ha detto che un pezzo può saltare i posizioni orizzontale posizioni j (sinistra o destra) e verticalmente (su o giù) (Vale a dire, un po 'come un cavallo negli scacchi), il saltatore può raggiungere ogni punto del tabellone? "

Ho scritto il seguente algoritmo. Trova ricorsivamente se ogni posizione sulla scacchiera è raggiungibile segnando tutti i punti sul grafico che sono stati visitati. Se non era raggiungibile, almeno un campo era falso e la funzione restituiva 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; 
     } 
     } 

Ora, in seguito è stato sottolineato che la soluzione ottimale sarebbe quella di implementare co-prime implementazione di Donald Knuth: http://arxiv.org/pdf/math/9411240v1.pdf E 'questo qualcosa che si dovrebbe essere in grado di capire da 45 minuti di colloquio tecnico? ?

Oltre a quanto sopra, c'è qualcosa che avrei potuto fare meglio?

modifica:
- Ho chiesto informazioni sulla posizione di partenza. Mi è stato detto che partire da 0,0 va bene.

edit2 In base al feedback, ho scritto un ciclo while con approccio in coda. L'approccio ricorsivo viene eseguito in un overflow dello stack quando n = 85. Tuttavia, il ciclo while con il metodo code in basso funziona fino a ~ n = 30.000. (dopo di ciò si verificano problemi di heap con memoria superiore a quella di GB). Se sai come ottimizzare ulteriormente, faccelo sapere.

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

Ho fatto un sacco di domande di intervista come questa. Non penso che ci si aspetterebbe di capire il metodo coprime durante l'intervista, ma mi sarei agganciato per l'utilizzo dello spazio di stack di O (n^2) - specialmente dal momento che hai passato tutti quei parametri a ciascuna chiamata ricorsiva invece di usando un oggetto.

Ti avrei chiesto di questo, e mi aspettavo che tu arrivassi con un BFS o DFS usando uno stack o una coda nell'heap. Se non ci riuscissi, potrei avere un reclamo come "mancata conoscenza della struttura dei dati".

Avrei anche fatto delle domande per assicurarmi che tu sapessi cosa stavi facendo quando hai assegnato quell'array 2D.

Se fossi davvero bravo, ti chiederei se puoi utilizzare la simmetria del problema per ridurre lo spazio di ricerca. Devi solo cercare una griglia di dimensioni J * J (assumendo J> = i).

È importante ricordare che l'intervistatore non sta solo guardando la risposta. Sta esaminando il modo in cui risolvi i problemi e quali strumenti hai nel cervello per poter attuare una soluzione.

Modifica: pensandoci ancora, ci sono molti passaggi incrementali sulla via del metodo coprime che potresti anche trovare. Nessuno se lo aspetta, ma sarebbe impressionante!

Answer 2

Mi dispiace, mi sento come se mi mancasse qualcosa.

Se si può solo andare verso l'alto o verso il basso per ie a sinistra oa destra di j, poi un caso (x, y) è raggiungibile da un caso di partenza (a, b) se ci sono interi m e n in modo che

a + m * i = x

b + n * j = y

Cioè, tutto è falso per una tavola quadrata dove n> 1.

Se significava più come un cavaliere in c hess, e puoi andare su/giù di i e left/right di j OR su/giù per j e sinistra/destra per i, puoi usare la stessa tecnica. Diventa solo 2 equazioni da risolvere:

A + M * i + n * j = x

b + o * i + p * j = y

Se non vi gli interi m, n, oep che soddisfano tali equazioni, non puoi raggiungere quel punto.