一道面试题 - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 一道面试题

相关主题
● 问一道少见的微软面试题。	● 感慨下找工作中的运气成分
● 请教一道面试题，判断迷宫有没有解	● 贡献一道面试题.
● 问个google的面试题。	● 目前系统的刷题，题目分类化，求咨询。
● 贴点面试题, ms和google的	● 一道 Java 面试题
● 讨论一道面试题	● 你们工作中究竟用没用上刷题得到的经验？
● 面试题总结(7) - Tree	● 一道狗家面试题。infinite matrix search
● 求牛人指点a家面试题	● 请教一道onsite面试题
● 我的面试题总结	● Amazon电面经

相关话题的讨论汇总
话题: int话题: sum话题: std话题: cords

进入JobHunting版参与讨论

1

(共1页)

f*******l 发帖数: 66	1 A robot is initially in coordinate (0,0), and could move in four directions (1,0) (0,1) (-1,0),(0,-1). It can not reach (x,y) where sum of digits(x,y) larger than 28(or to generalize, k). For example, (279,89) 2+7+9+8+9 > 28, ( -279,89) the same. Question: print out all the points the robot can reach.
H***e 发帖数: 476	2 backtracking 吧 directions ( 【在 f*******l 的大作中提到】 : A robot is initially in coordinate (0,0), and could move in four directions : (1,0) (0,1) (-1,0),(0,-1). It can not reach (x,y) where sum of digits(x,y) : larger than 28(or to generalize, k). For example, (279,89) 2+7+9+8+9 > 28, ( : -279,89) the same. : Question: print out all the points the robot can reach. : :
z******w 发帖数: 36	3 use DFS start from 0,0 to find all the points it can reach
c*****e 发帖数: 737	4 find:9006221 points. 1 #include 2 #include 3 #include 4 #include 5 6 typedef std::pair Cord; 7 typedef std::map Cords; 8 9 Cords cords; 10 int total = 0; 11 12 bool findCord(int x_, int y_) 13 { 14 if (cords.find(std::make_pair(x_, y_)) != cords.end()) return true; 15 return false; 16 } 17 18 int count(int x_) 19 { 20 int x = abs(x_); 21 22 int c = 0; 23 24 while (x > 0) 25 { 26 c += x % 10; 27 x /= 10; 28 } 29 30 return c; 31 } 32 33 void findNextPoint(int x_, int y_) 34 { 35 if (findCord(x_, y_)) return; 36 37 int sum = count(x_) + count (y_); 38 if (sum > 28) return; 39 // std::cout << "(" << x_ << ", " << y_ << ") sum:" << sum << "\n"; 40 total++; 41 42 cords[std::make_pair(x_, y_)] = 1; 43 44 findNextPoint(x_ - 1, y_); 45 findNextPoint(x_ + 1, y_); 46 findNextPoint(x_, y_ - 1); 47 findNextPoint(x_, y_ +1); 48 } 49 int main() 50 { 51 findNextPoint(0,0); 52 std::cout << "find:" << total << " points." << "\n"; 53 return 0; 54 } directions ( 【在 f*******l 的大作中提到】 : A robot is initially in coordinate (0,0), and could move in four directions : (1,0) (0,1) (-1,0),(0,-1). It can not reach (x,y) where sum of digits(x,y) : larger than 28(or to generalize, k). For example, (279,89) 2+7+9+8+9 > 28, ( : -279,89) the same. : Question: print out all the points the robot can reach. : :
f*******l 发帖数: 66	5 Is there a boundary between reachable and unreachable? How is the shape look like? is it possible to use hash to replace bool findCord(int x_, int y_)? 【在 c*****e 的大作中提到】 : find:9006221 points. : 1 #include : 2 #include : 3 #include : 4 #include : 5 : 6 typedef std::pair Cord; : 7 typedef std::map Cords; : 8 : 9 Cords cords;
p*****2 发帖数: 21240	6 这题就是数学题吧？4个方向都能走。就是看x和y的digits是不是sum大于k。如果没有boundary的话，不是可以很大吗？比如1000000000000........, 100000000000000.......
k****e 发帖数: 297	7 如果每次只能移一格的话，肯定是会碰到边界的。到不了很大【在 p*****2 的大作中提到】 : 这题就是数学题吧？4个方向都能走。就是看x和y的digits是不是sum大于k。 : 如果没有boundary的话，不是可以很大吗？ : 比如1000000000000........, 100000000000000.......
p*****2 发帖数: 21240	8 明白了。一会儿想想。【在 k****e 的大作中提到】 : 如果每次只能移一格的话，肯定是会碰到边界的。到不了很大
c*****e 发帖数: 737	9 当然有边界的，不会走到无穷远的。 look 【在 f*******l 的大作中提到】 : Is there a boundary between reachable and unreachable? How is the shape look : like? : is it possible to use hash to replace : bool findCord(int x_, int y_)?
C***U 发帖数: 2406	10 我觉得这办法不错哎稍微修改一下BFS的code就可以了【在 z******w 的大作中提到】 : use DFS start from 0,0 to find all the points it can reach

1

(共1页)

进入JobHunting版参与讨论

相关主题
● Amazon电面经	● 讨论一道面试题
● 贡献A家面经	● 面试题总结(7) - Tree
● 请教一下，leetcode surrounded regions这题为什么我的代码会超时	● 求牛人指点a家面试题
● 一个图的面试题目	● 我的面试题总结
● 问一道少见的微软面试题。	● 感慨下找工作中的运气成分
● 请教一道面试题，判断迷宫有没有解	● 贡献一道面试题.
● 问个google的面试题。	● 目前系统的刷题，题目分类化，求咨询。
● 贴点面试题, ms和google的	● 一道 Java 面试题

相关话题的讨论汇总
话题: int话题: sum话题: std话题: cords

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)