During a 45 minute technical interview with Google, I was asked a Leaper Graph problem. I wrote working code, but later was declined the job offer because I lacked Data structure knowledge. I'm wondering what I could have done better.
The problem was as following: "Given an N sized board, and told that a piece can jump i positions horizontally (left or right) and j positions vertically (up or down) (I.e, sort of like a horse in chess), can the leaper reach every spot on the board?"
I wrote the following algorithm. It recursively finds out if every position on the board is reachable by marking all spots on the graph that were visited. If it was not reachable, then at least one field was false and the function would 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, later it was pointed out that the optimal solution would be to implement Donald Knuth's co-prime implementation: http://arxiv.org/pdf/math/9411240v1.pdf Is this something that one should be able to figure out on a 45 minute technical interview??
Besides the above, is there anything I could have done better?
edit:
- I enquired about starting position. I was told starting at 0,0 is fine.
edit2 Based on feedback, I wrote a while-loop with queue approach. The recursive approach runs into a stack-overflow when n = 85. However, the while loop with queue method below works up to ~n = 30,000. (after that it runs into heap-issues with memory exceeding GB's). 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;
}
}
I ask a lot of interview questions like this. I don't think you would be expected to figure out the coprime method during the interview, but I would have docked you for using O(n^2) stack space -- especially since you passed all those parameters to each recursive call instead of using an object.
I would have asked you about that, and expected you to come up with a BFS or DFS using a stack or queue on the heap. If you failed on that, I might have a complaint like "lacked data structure knowledge".
I would also have asked questions to make sure you knew what you were doing when you allocated that 2D array.
If you were really good, I would ask you if you can use the symmetry of the problem to reduce your search space. You really only have to search a J*J-sized grid (assuming J>=i).
It's important to remember that the interviewer isn't just looking at your answer. He's looking at the way you solve problems and what tools you have in your brain that you can bring to bear on a solution.
Edit: thinking about this some more, there are lots of incremental steps on the way to the coprime method that you might also come up with. Nobody will expect that, but it would be impressive!