latest interview questions - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

latest interview questions

latest interview questions# JobHunting - 待字闺中

l*c2012-03-22 07:03

1 楼

There is a monkey which can walk around on a planar grid. The monkey can
move one space at a time left, right, up or down. That is, from (x, y) the
monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where
the sum of the digits of the absolute value of the x coordinate plus the sum
of the digits of the absolute value of the y coordinate are lesser than or
equal to 19 are accessible to the monkey. For example, the point (59, 79) is
inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another
example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7
= 12, which is less than 19. How many points can the monkey access if it
starts at (0, 0), including (0, 0) itself? There is no input for this
program.
Print out the how many points can the monkey access. (The number should be
printed as an integer whole number eg. if the answer is 10 (its not !!),
print out 10, not 10.0 or 10.00 etc)
==================================================
My comment, if you use recursive method, very slow and stack overflow.
Also, if replace 19 with 25, what's the result?

p*22012-03-22 07:03

2 楼

BFS不行吗？

l*c2012-03-22 07:03

3 楼

apparentely, points (0, 298), (298, 0) (0, -298) (-298, 0) are the corner
value.
how to BFS?

【在 p*****2 的大作中提到】

: BFS不行吗？

p*22012-03-22 07:03

4 楼

从（0,0）开始，一层一层往外走不行吗。

【在 l******c 的大作中提到】

: apparentely, points (0, 298), (298, 0) (0, -298) (-298, 0) are the corner
: value.
: how to BFS?

l*c2012-03-22 07:03

5 楼

there are two directions, x & y,
some points will be visited twice

【在 p*****2 的大作中提到】

:
: 从（0,0）开始，一层一层往外走不行吗。

c*p2012-03-22 07:03

6 楼

在y=0和x-y=0，并x>=0的区间搜索。搜完了*8再扣掉重复计算过的点。
搜索是一层一层地搜【在 lclclclc (home) 的大作中提到: 】
sum
or
is
Another
7

g*y2012-03-22 07:03

7 楼

就是简单的BFS, 运行很快，对N=25, 16ms。f(19)=299, f(25)=899
public class MonkeyWalk {
public final static void main(String[] args) {
new MonkeyWalk().run(25);
}

private void run(int N) {
ArrayDeque queue = new ArrayDeque();
queue.add(new Point(0, 0));
HashSet visited = new HashSet();
visited.add("0 0");

while (!queue.isEmpty()) {
Point p = queue.pop();
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
}

System.out.println(visited.size());
}

private void visit(int x, int y, ArrayDeque queue, HashSet> visited, int N) {
String key = x + " " + y;
if (visited.contains(key) || sum(x)+sum(y)>N) return;
queue.add(new Point(x, y));
visited.add(key);
}
private int sum(int x) {
if (x < 0) return sum(-x);
int sum = 0;
while (x > 0) {
sum += x%10;
x /= 10;
}
return sum;
}

private class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}

l*e2012-03-22 07:03

8 楼

和我的结果不一样
f(19) = 102485
f(25) = 1033841

【在 g**********y 的大作中提到】

: 就是简单的BFS, 运行很快，对N=25, 16ms。f(19)=299, f(25)=899
: public class MonkeyWalk {
: public final static void main(String[] args) {
: new MonkeyWalk().run(25);
: }
:
: private void run(int N) {
: ArrayDeque queue = new ArrayDeque();
: queue.add(new Point(0, 0));
: HashSet visited = new HashSet();

g*y2012-03-22 07:03

9 楼

是每个点都可以走到的？你计算的是valid的点吧？

【在 l******e 的大作中提到】

: 和我的结果不一样
: f(19) = 102485
: f(25) = 1033841

l*e2012-03-22 07:03

10 楼

你程序里这段是什么意思？
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);
visit(p.x+1, p.y, queue, visited, N);

【在 g**********y 的大作中提到】

g*y2012-03-22 07:03

11 楼

汗死，你是对的，我copy-paste之后，忘改了 :)

【在 l******e 的大作中提到】

: 你程序里这段是什么意思？
: visit(p.x+1, p.y, queue, visited, N);
: visit(p.x+1, p.y, queue, visited, N);
: visit(p.x+1, p.y, queue, visited, N);
: visit(p.x+1, p.y, queue, visited, N);

g*y2012-03-22 07:03

12 楼

把HashSet换成boolean的话，对N=25, 速度可以从2.8秒提到0.2秒。
对N=25, x/y = +/-899 就是边界，所以二维数组[2000][2000]就足够存储所有访问过的点。
程序：
public class MonkeyWalk {
public final static void main(String[] args) {
long t0 = System.currentTimeMillis();
new MonkeyWalk().run(25);
long t1 = System.currentTimeMillis();
System.out.println(t1 - t0);
}

private ArrayDeque queue;
private boolean[][] visited;
private int count = 0;

private void run(int N) {
queue = new ArrayDeque();
queue.add(new Point(0, 0));
visited = new boolean[2000][2000];
visited[1000][1000] = true;
count++;

while (!queue.isEmpty()) {
Point p = queue.remove();
visit(p.x+1, p.y, N);
visit(p.x-1, p.y, N);
visit(p.x, p.y+1, N);
visit(p.x, p.y-1, N);
}

System.out.println(count);
}

private void visit(int x, int y, int N) {
if (visited[1000+x][1000+y] || sum(x)+sum(y)>N) return;
queue.add(new Point(x, y));
count++;
visited[1000+x][1000+y] = true;
}
private int sum(int x) {
if (x < 0) return sum(-x);
int sum = 0;
while (x > 0) {
sum += x%10;
x /= 10;
}
return sum;
}

private class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}