During a 45-minute technical interview with Google, I was asked about the Leaper Graph issue. I wrote working code, but a job offer was later rejected because I lacked data on the data structure. I wonder what I could do better.
The problem was this: “Given the size board N, and said that I can jump horizontally (left or right) and j vertically (up or down) (ie, like a horse in chess), the leader can reach every place on the board? "
I wrote the following algorithm. It recursively discovers that each position on the board is reachable, marking all the points on the chart that have been visited. If this failed, then at least one field was false and the function will return 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; } }
Now, it was later indicated that the best solution would be to implement a joint implementation of Donald Knuth: http://arxiv.org/pdf/math/9411240v1.pdf Is this what you need to be able to find out in a 45-minute technical interview?
Other than the above, is there anything I could do better?
change
- I asked about the starting position. I was told that starting with 0.0 is good.
edit2 Based on the feedback, I wrote a while loop with the approach to the queue. A recursive approach is performed when the stack overflows at n = 85. However, the while loop with the queue method is lower to ~ n = 30,000. (After that, it encounters heap problems with more than GB memory). If you know how to optimize further, please let me know.
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; } }