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这些方法。。。

蠡口已经有原题了吧

代码块排版有点乱，我再贴一下吧。。。

Public class Roomba implements Robot{

        Direction direction;

        Set<String>  seen;

        int x; int y;

        Sensor sensor; //Sensor API to detect obstacle;

       

        class Direction{

                final int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

                int dir;

       

                public Direction(){

            int dir = 0;

    }

    public void turnL(){

            dir = (dir + 3) % 4;

    }

    public void turnR(){

            dir = (dir + 1) % 4;

    }

}

public Roomba(){

                direction = new Direction();

                seen = new HashSet<>();

                x = 0; y = 0;

                clean();

                seen.add(x+”,”+y);

                sensor = new Sensor();

            }

            boolean move(){

                x += direction.dirs[direction.dir][0];

                y += direction.dirs[direction.dir][1];

                seen.add(x+”,”+y);

                if(sensor.detect()){

                        /*code to move the roomba physically move forward*/

                        clean();

                        return true;

                }else return false;

}

public void moveBack(){

        TurnRight(2);

        move();

        TurnRight(2);

}

void TurnLeft(int k){

        for(int i = 0; i < k; i++)

                direction.turnL();

}

            void TurnRight(int k){

                for(int i = 0; i < k; i++)

                direction.turnL();

}

void Clean(){

        /*code to call the robot physically clean the current area */

}

public void sweep(){

        Direction prevDir = direction;

                    for(int i = 0; i < 4; i++){

                        TurnRight(1);

int nextx = x + direction.dirs[direction.dir][0];

                        int nexty = y + direction.dirs[direction.dir][1];

                        if(seen.contains(nextx+”,”+nexty)) continue;

                        if(move()){

                                sweep();

                        }

                    }

                    direction = prevDir;

                    moveBack();

}

}

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

才找到。。。谢谢了

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

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

flop什么意思

znyjose 发表于 2018-11-2 12:37
提个follow-up：如果地图没边界，或者没有足够空间存hashmap呢？

我感觉这个命题不是很make sense。。
首先地图要是没有边界也不用怎么办啊，机器人就一路向北了。
其次java里hashmap达到最大容量之后会依然会用链表或者红黑树处理冲突，所以理论上还可以继续往里加键值对。
另外我感觉在hashmap装满之前递归的栈会先爆掉。

leetcode第几题啊

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

蠡口 四八九