Trong một cuộc phỏng vấn kỹ thuật 45 phút với Google, tôi đã được hỏi một vấn đề về đồ thị Leaper. Tôi đã viết mã làm việc, nhưng sau đó đã bị từ chối lời mời làm việc vì tôi thiếu kiến thức về cấu trúc dữ liệu. Tôi tự hỏi những gì tôi có thể làm tốt hơn.Thuật toán tối ưu hóa đồ thị Leaper?
Vấn đề là như sau: "Cho một bảng có kích thước N, và nói rằng một mảnh có thể nhảy tôi vị trí theo chiều ngang (trái hoặc phải) và j vị trí theo chiều dọc (lên hoặc xuống) (Tức là, giống như một con ngựa trong cờ vua), người chơi có thể tiếp cận mọi vị trí trên bảng không? "
Tôi đã viết thuật toán sau. Nó đệ quy tìm hiểu xem mọi vị trí trên bảng có thể truy cập được bằng cách đánh dấu tất cả các điểm trên biểu đồ đã được truy cập hay không. Nếu nó không thể truy cập được, thì ít nhất một trường sai và hàm sẽ trả về 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;
}
}
Bây giờ, sau đó được chỉ ra rằng giải pháp tối ưu sẽ được thực hiện Donald Knuth đồng thủ thực hiện: http://arxiv.org/pdf/math/9411240v1.pdf Liệu đó có phải ta nên có thể hình dung ra trên một cuộc phỏng vấn kỹ thuật 45 phút? ?
Bên cạnh đó, có bất kỳ điều gì tôi có thể làm tốt hơn không?
chỉnh sửa:
- Tôi hỏi về vị trí bắt đầu. Tôi đã nói bắt đầu từ 0,0 là tốt.
edit2 Dựa trên phản hồi, tôi đã viết một vòng lặp while với phương thức xếp hàng. Cách tiếp cận đệ quy chạy vào tràn ngăn xếp khi n = 85. Tuy nhiên, vòng lặp while với phương thức xếp hàng bên dưới hoạt động tối đa ~ n = 30.000. (sau đó nó chạy vào đống vấn đề với bộ nhớ vượt quá GB). Nếu bạn biết cách tối ưu hóa thêm, vui lòng cho tôi biết.
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;
}
}
Bạn có được vị trí bắt đầu không? Hay bạn phải tự khám phá vị trí tối ưu? – smac89
Tôi hỏi người phỏng vấn về điều đó. Tôi được cho biết 0x0 là một vị trí hợp pháp. –
Nếu bạn có thể tiếp cận mọi nơi trên bảng từ vị trí * any *, bạn có thể tiếp cận mọi nơi trên bảng từ vị trí * mọi *, vì vậy vị trí bắt đầu không quan trọng –