logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
请教onsite一道题
avatar
请教onsite一道题# JobHunting - 待字闺中
P*c
1 楼
没做出来，挂了。
一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
（e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
M, N)要经过多少个坐标点，不一定要最优路径。
avatar
h*7
2 楼
leetcode unique path II

K
到(

【在 P*********c 的大作中提到】
: 没做出来，挂了。
: 一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
: 个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
: （e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
: robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
: 考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
: M, N)要经过多少个坐标点，不一定要最优路径。
avatar
h*n
3 楼
递归吧
avatar
N*6
4 楼
个人觉得既然正负都无所谓的话，四个象限的情形都可以
映射到第一象限，应该可以证明从其他象限绕的valid path
都可以通过在第一象限走到目的地，而且path相对比较短
所以只考虑第一象限的情形，四个方向可以简化为只能往右
和往上走，这样就和经典的robot moving problem 一样了
用dp可以找出总共有多少条路径，backtracking可以打印或者
计算总共的路径，这道题不需要算总数和打印，只需要算其
中一条valid path的长度，相对简单一些
参见
http://prpds.blogspot.com/2011/07/robot-in-nxn-grid_18.html
以及career cup里面的moving robot 例子

K
到(

【在 P*********c 的大作中提到】
: 没做出来，挂了。
: 一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
: 个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
: （e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
: robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
: 考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
: M, N)要经过多少个坐标点，不一定要最优路径。
avatar
t*g
5 楼
BFS?
Use a queue to keep the list of nodes to be visited.
Use a set to keep track of nodes visited.
Push (0,0) to queue first.
Check each node in queue to see where it can go.Push these nodes into the
queue if it is not visited yet.
When we reached the destination, it can stop. If the queue becomes empty,
there is no path to the destination.
avatar
P*c
6 楼
只能两个方向的题我也做过。
也有可能是我想复杂了，说说我的疑惑
首先这个障碍条件很奇怪，会不会出现走到一个点，两个方向都是障碍，必须要用到另
外两个方向。
其次，这是个无穷大的坐标平面，递归的时候边界条件是否跟长方形矩阵一样，会不会
目标点所在位置只能从矩阵外面到达。
谢谢大家贡献思路。

【在 N*********6 的大作中提到】
: 个人觉得既然正负都无所谓的话，四个象限的情形都可以
: 映射到第一象限，应该可以证明从其他象限绕的valid path
: 都可以通过在第一象限走到目的地，而且path相对比较短
: 所以只考虑第一象限的情形，四个方向可以简化为只能往右
: 和往上走，这样就和经典的robot moving problem 一样了
: 用dp可以找出总共有多少条路径，backtracking可以打印或者
: 计算总共的路径，这道题不需要算总数和打印，只需要算其
: 中一条valid path的长度，相对简单一些
: 参见
: http://prpds.blogspot.com/2011/07/robot-in-nxn-grid_18.html
avatar
p*2
7 楼
感觉DFS，BFS都行吧？
avatar
e*e
8 楼
void walk(int m, int n, int K) {
m = Math.abs( m );
n = Math.abs( n );
walkCore( 0, 0, 0, m, n, K );
}
void walkCore(int i, int j, int count, int m, int n, int K) {
if (i == m && j == n) {
System.out.println( count );
return;
}

if (i > m || j > n)
return;
if ( digitSum( j ) <= K )
walkCore( i, j + 1, count + 1, m, n, K );

if ( digitSum( i ) <= K )
walkCore( i + 1, j, count + 1, m, n, K );
}
int digitSum(int integer) {
int sum = 0;
while ( integer > 0 ) {
sum += integer % 10;
integer /= 10;;
}
return sum;
}
avatar
g*9
9 楼
M+N（包括目标点） 或者到不了？
要么就是题意没搞清
avatar
w*o
10 楼
我把20X20的横竖坐标的个位数相加的结果打印了出来，挺有意思，大家看看，很有规
律。
10 11 12 13 14 15 16 17 18 19 11 12 13 14 15 16 17 18 19
20
9 10 11 12 13 14 15 16 17 18 10 11 12 13 14 15 16 17 18
19
8 9 10 11 12 13 14 15 16 17 9 10 11 12 13 14 15 16 17
18
7 8 9 10 11 12 13 14 15 16 8 9 10 11 12 13 14 15 16
17
6 7 8 9 10 11 12 13 14 15 7 8 9 10 11 12 13 14 15
16
5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14
15
4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13
14
3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12
13
2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11
12
1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10
11
9 10 11 12 13 14 15 16 17 18 10 11 12 13 14 15 16 17 18
19
8 9 10 11 12 13 14 15 16 17 9 10 11 12 13 14 15 16 17
18
7 8 9 10 11 12 13 14 15 16 8 9 10 11 12 13 14 15 16
17
6 7 8 9 10 11 12 13 14 15 7 8 9 10 11 12 13 14 15
16
5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14
15
4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13
14
3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12
13
2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11
12
1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10
11
0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
10
avatar
w*o
11 楼
好像就是M＋N，如果M和N的各位相加小于K的话。否则不能到。
走法是先沿X轴向右走到 (M - (M % 10))，再向上做到N，再向右走到M。
avatar
N*6
12 楼
一个test case，目的地(100, 50) K = 10
我的程序运行了几个小时也没走到，应该是走不到了
我是在第一象限里面向右向上
最近的两个点(99, 50), (100, 49)都不valid

【在 w***o 的大作中提到】
: 好像就是M＋N，如果M和N的各位相加小于K的话。否则不能到。
: 走法是先沿X轴向右走到 (M - (M % 10))，再向上做到N，再向右走到M。
avatar
C*U
13 楼
这题啥公司的?

K
到(

【在 P*********c 的大作中提到】
: 没做出来，挂了。
: 一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
: 个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
: （e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
: robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
: 考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
: M, N)要经过多少个坐标点，不一定要最优路径。
avatar
P*c
14 楼
因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
老印面的，技不如人不能怪种族。
NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
到达，我就是递归的边界条件没写出来。
avatar
S*w
15 楼
NDA就是shit

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
d*e
16 楼
公司名字也不知，怎么争气？

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
y*g
17 楼
中文写的怕什么。

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
S*w
18 楼
什么技不如人啊
要是一个老印面 老印们出的题都爆简单
再说了 几个破面试题做不上有啥的

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
P*c
19 楼
做到了相同的题目就知道了，呵呵。
avatar
P*c
20 楼
没做出来，挂了。
一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
（e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
M, N)要经过多少个坐标点，不一定要最优路径。
avatar
h*7
21 楼
leetcode unique path II

K
到(

【在 P*********c 的大作中提到】
: 没做出来，挂了。
: 一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
: 个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
: （e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
: robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
: 考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
: M, N)要经过多少个坐标点，不一定要最优路径。
avatar
h*n
22 楼
递归吧
avatar
N*6
23 楼
个人觉得既然正负都无所谓的话，四个象限的情形都可以
映射到第一象限，应该可以证明从其他象限绕的valid path
都可以通过在第一象限走到目的地，而且path相对比较短
所以只考虑第一象限的情形，四个方向可以简化为只能往右
和往上走，这样就和经典的robot moving problem 一样了
用dp可以找出总共有多少条路径，backtracking可以打印或者
计算总共的路径，这道题不需要算总数和打印，只需要算其
中一条valid path的长度，相对简单一些
参见
http://prpds.blogspot.com/2011/07/robot-in-nxn-grid_18.html
以及career cup里面的moving robot 例子

K
到(

【在 P*********c 的大作中提到】
: 没做出来，挂了。
: 一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
: 个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
: （e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
: robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
: 考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
: M, N)要经过多少个坐标点，不一定要最优路径。
avatar
t*g
24 楼
BFS?
Use a queue to keep the list of nodes to be visited.
Use a set to keep track of nodes visited.
Push (0,0) to queue first.
Check each node in queue to see where it can go.Push these nodes into the
queue if it is not visited yet.
When we reached the destination, it can stop. If the queue becomes empty,
there is no path to the destination.
avatar
P*c
25 楼
只能两个方向的题我也做过。
也有可能是我想复杂了，说说我的疑惑
首先这个障碍条件很奇怪，会不会出现走到一个点，两个方向都是障碍，必须要用到另
外两个方向。
其次，这是个无穷大的坐标平面，递归的时候边界条件是否跟长方形矩阵一样，会不会
目标点所在位置只能从矩阵外面到达。
谢谢大家贡献思路。

【在 N*********6 的大作中提到】
: 个人觉得既然正负都无所谓的话，四个象限的情形都可以
: 映射到第一象限，应该可以证明从其他象限绕的valid path
: 都可以通过在第一象限走到目的地，而且path相对比较短
: 所以只考虑第一象限的情形，四个方向可以简化为只能往右
: 和往上走，这样就和经典的robot moving problem 一样了
: 用dp可以找出总共有多少条路径，backtracking可以打印或者
: 计算总共的路径，这道题不需要算总数和打印，只需要算其
: 中一条valid path的长度，相对简单一些
: 参见
: http://prpds.blogspot.com/2011/07/robot-in-nxn-grid_18.html
avatar
p*2
26 楼
感觉DFS，BFS都行吧？
avatar
e*e
27 楼
void walk(int m, int n, int K) {
m = Math.abs( m );
n = Math.abs( n );
walkCore( 0, 0, 0, m, n, K );
}
void walkCore(int i, int j, int count, int m, int n, int K) {
if (i == m && j == n) {
System.out.println( count );
return;
}

if (i > m || j > n)
return;
if ( digitSum( j ) <= K )
walkCore( i, j + 1, count + 1, m, n, K );

if ( digitSum( i ) <= K )
walkCore( i + 1, j, count + 1, m, n, K );
}
int digitSum(int integer) {
int sum = 0;
while ( integer > 0 ) {
sum += integer % 10;
integer /= 10;;
}
return sum;
}
avatar
g*9
28 楼
M+N（包括目标点） 或者到不了？
要么就是题意没搞清
avatar
w*o
29 楼
我把20X20的横竖坐标的个位数相加的结果打印了出来，挺有意思，大家看看，很有规
律。
10 11 12 13 14 15 16 17 18 19 11 12 13 14 15 16 17 18 19
20
9 10 11 12 13 14 15 16 17 18 10 11 12 13 14 15 16 17 18
19
8 9 10 11 12 13 14 15 16 17 9 10 11 12 13 14 15 16 17
18
7 8 9 10 11 12 13 14 15 16 8 9 10 11 12 13 14 15 16
17
6 7 8 9 10 11 12 13 14 15 7 8 9 10 11 12 13 14 15
16
5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14
15
4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13
14
3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12
13
2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11
12
1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10
11
9 10 11 12 13 14 15 16 17 18 10 11 12 13 14 15 16 17 18
19
8 9 10 11 12 13 14 15 16 17 9 10 11 12 13 14 15 16 17
18
7 8 9 10 11 12 13 14 15 16 8 9 10 11 12 13 14 15 16
17
6 7 8 9 10 11 12 13 14 15 7 8 9 10 11 12 13 14 15
16
5 6 7 8 9 10 11 12 13 14 6 7 8 9 10 11 12 13 14
15
4 5 6 7 8 9 10 11 12 13 5 6 7 8 9 10 11 12 13
14
3 4 5 6 7 8 9 10 11 12 4 5 6 7 8 9 10 11 12
13
2 3 4 5 6 7 8 9 10 11 3 4 5 6 7 8 9 10 11
12
1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10
11
0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
10
avatar
w*o
30 楼
好像就是M＋N，如果M和N的各位相加小于K的话。否则不能到。
走法是先沿X轴向右走到 (M - (M % 10))，再向上做到N，再向右走到M。
avatar
N*6
31 楼
一个test case，目的地(100, 50) K = 10
我的程序运行了几个小时也没走到，应该是走不到了
我是在第一象限里面向右向上
最近的两个点(99, 50), (100, 49)都不valid

【在 w***o 的大作中提到】
: 好像就是M＋N，如果M和N的各位相加小于K的话。否则不能到。
: 走法是先沿X轴向右走到 (M - (M % 10))，再向上做到N，再向右走到M。
avatar
C*U
32 楼
这题啥公司的?

K
到(

【在 P*********c 的大作中提到】
: 没做出来，挂了。
: 一个robot在二维坐标平面的(0,0)点，robot可以上下左右移动到相邻整数坐标点，一
: 个整数坐标点如果满足条件：该点横坐标和纵坐标所有位数加起来不大于某个指定的K
: （e.g. given a constant number K and coordinate (23, 43), 2+3+4+3 <= K），
: robot就可以访问，否则视该点为障碍（负数坐标时，不考虑负号，比如(-23,-43)，只
: 考察2+3+4+3 <= K是否满足）。现在给定一个目标坐标点(M, N)，求robot从(0, 0)到(
: M, N)要经过多少个坐标点，不一定要最优路径。
avatar
P*c
33 楼
因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
老印面的，技不如人不能怪种族。
NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
到达，我就是递归的边界条件没写出来。
avatar
S*w
34 楼
NDA就是shit

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
d*e
35 楼
公司名字也不知，怎么争气？

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
y*g
36 楼
中文写的怕什么。

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
S*w
37 楼
什么技不如人啊
要是一个老印面 老印们出的题都爆简单
再说了 几个破面试题做不上有啥的

【在 P*********c 的大作中提到】
: 因为签了NDA，公司名字就不透露了。希望以后有兄弟面到这家公司帮咱争口气，一个
: 老印面的，技不如人不能怪种族。
: NancyHarry6的test case证实了这题还真不能只考虑两个方向，某些点只能从矩阵外面
: 到达，我就是递归的边界条件没写出来。
avatar
P*c
38 楼
做到了相同的题目就知道了，呵呵。
avatar
r*n
39 楼
DFS may proceed in the wrong direction indefinitely. BFS, on the other hand,
can be used to flood the plane, starting at the origin, and will terminate
definitely.

【在 p*****2 的大作中提到】
: 感觉DFS，BFS都行吧？
avatar
r*n
40 楼
DFS may proceed in the wrong direction indefinitely. BFS, on the other hand,
can be used to flood the plane, starting at the origin, and will terminate
definitely.

【在 p*****2 的大作中提到】
: 感觉DFS，BFS都行吧？
avatar
b*r
41 楼
i may understand what LZ is speaking, personally i really don't like LZ is
doing. i really don't understand why the company name is so important,
though majority of people may guess this is G. wake up my fellow Chinese,
fuck off the damn NDA, the only statement i want to share with you is "fair
play should postponed" ... to make US a better place for all Chinese, don't
just follow the rule, make the rule
it will be different story though if you don't want other fellow Chinese who
is preparing for the company do do some research on this q!

【在 P*********c 的大作中提到】
: 做到了相同的题目就知道了，呵呵。
avatar
g*s
42 楼
这问题让我首先想到的是A*, 其次是Dijkstra（类似BFS）
不过当场让我任意一个我估计都得挂。。。。。
相关阅读
G家电面面经怎么做题？I-94上的expiration date应该是身份过期时间还是visa过期时间？这种情况怎么办？OPT：有工作offer，还没EAD卡能回国吗？印度学者：印度英语世界最纯正 (转载)H1B Approve 但是没收到hard copyG家SRE店面国内一线城市40wrmb和美国二线城市10w刀哪个生活好有在tumblr的吗？发现一个职位很matchquestion about MATLAB matrix squaring (转载)谁有兴趣做一做，看看是否准确请问关于database architect面试，这几个问题怎么回答比较好？大家说的cc150指的是什么？回馈本版，面试经历加个人体会Leetcode 的 Surrounded Regions 好难过大OJ (in JAVA)你们都不喜欢M，可是我最喜欢Mcc150 4.7 一问请教一个算法offer求比较
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。