google面试 扫地机器人

下周狗家店面，这两天就在地里刷面经，这道扫地机器人看到了好几次，就在google doc上写了一下。原题是这样的：

Given a robot cleaner in a room modeled as a grid. Each cell in the grid can be empty or blocked. The robot cleaner can move forward, turn left or turn right. When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

interface Robot {

  // returns true if next cell is open and robot moves into the cell.

  // returns false if next cell is obstacle and robot stays on the current cell.

  boolean Move();

  // Robot will stay on the same cell after calling Turn*. k indicates how

  // many turns to perform.

  void TurnLeft(int k);

  void TurnRight(int k);

  // Clean the current cell.

  void Clean();

  boolean Move(Direction d);

}

我理解这道题应该是让你写一个类去实现这个interface，也就是通过重写里面的方法来让机器人扫遍整个屋子。因为不知道起始位置在哪，我就用了一个HashSet来记录检测过的位置，然后用DFS + backtracking来扫描。我感觉这里还涉及到了一些跟硬件有关的API面试官没有写出来，比如说在物理上移动机器人，转向，检测障碍等等，这个没有给写不了，所以只能在相应位置标注一下了。 下面是我写的代码，没有实测，也不知道哪里有bug，贴出来大家提提问题。

1. Public class Roomba implements Robot{
   
2.         Direction direction;
   
3.         Set<String>  seen;
   
4.         int x; int y;
   
5.         Sensor sensor; //Sensor API to detect obstacle;
   
6.        
   
7.         class Direction{
   
8.                 final int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
   
9.                 int dir;
   
10.        
    
11.                 public Direction(){
    
12.                 int dir = 0;
    
13. }
    
14. 
    
15. public void turnL(){
    
16.                 dir = (dir + 3) % 4;
    
17. }
    
18.        
    
19. public void turnR(){
    
20.                 dir = (dir + 1) % 4;
    
21. }
    
22. }
    
23. 
    
24. 
    
25.        
    
26. public Roomba(){
    
27.                 direction = new Direction();
    
28.                 seen = new HashSet<>();
    
29.                 x = 0; y = 0;
    
30.                 clean();
    
31.                 seen.add(x+”,”+y);
    
32.                 sensor = new Sensor();
    
33.         }
    
34. 
    
35.         boolean move(){
    
36.                 x += direction.dirs[direction.dir][0];
    
37.                 y += direction.dirs[direction.dir][1];
    
38.                 seen.add(x+”,”+y);
    
39.                 if(sensor.detect()){
    
40.                         /*code to move the roomba physically move forward*/
    
41. clean();
    
42.                         return true;
    
43. }else return false;
    
44. }
    
45. 
    
46. public void moveBack(){
    
47.         TurnRight(2);
    
48.         move();
    
49.         TurnRight(2);
    
50. }
    
51. 
    
52. 
    
53. void TurnLeft(int k){
    
54.         for(int i = 0; i < k; i++)
    
55.                 direction.turnL();
    
56. }
    
57. 
    
58.         void TurnRight(int k){
    
59.                 for(int i = 0; i < k; i++)
    
60.                 direction.turnL();
    
61. }
    
62. 
    
63. void Clean(){
    
64.         /*code to call the robot physically clean the current area */
    
65. }
    
66. 
    
67. public void sweep(){
    
68.         Direction prevDir = direction;
    
69.                 for(int i = 0; i < 4; i++){
    
70. TurnRight(1);
    
71.         int nextx = x + direction.dirs[direction.dir][0];
    
72.                         int nexty = y + direction.dirs[direction.dir][1];
    
73.                         if(seen.contains(nextx+”,”+nexty)) continue;
    
74.                         if(move()){
    
75.                                 sweep();
    
76. }
    
77. }
    
78. direction = prevDir;
    
79. moveBack();
    
80. }
    
81. }
    

复制代码

为什么我觉得楼主的意思和蠡口不一样的。
原题是给了API的的方法，要扫整个屋子。楼主是说要直接去implement这些方法。。。

蠡口已经有原题了吧

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

cszhazha 发表于 2018-11-2 10:22
蠡口已经有原题了吧

才找到。。。谢谢了

感觉这道题已经flop了...

czcbangkai 发表于 2018/11/02 10:43:56
感觉这道题已经flop了...

flop什么意思

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

leetcode第几题啊

zfrancica 发表于 2018-11-2 15:42
leetcode第几题啊

蠡口 四八九