回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

google面试 扫地机器人

全局:

2019(1-3月) 码农类General 硕士 全职@google - 网上海投 - 技术电面  | | Other | 应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
下周狗家店面,这两天就在地里刷面经,这道扫地机器人看到了好几次,就在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. public void turnL(){
  15.                 dir = (dir + 3) % 4;
  16. }
  17.        
  18. public void turnR(){
  19.                 dir = (dir + 1) % 4;
  20. }
  21. }


  22.        
  23. public Roomba(){
  24.                 direction = new Direction();
  25.                 seen = new HashSet<>();
  26.                 x = 0; y = 0;
  27.                 clean();
  28.                 seen.add(x+”,”+y);
  29.                 sensor = new Sensor();
  30.         }

  31.         boolean move(){
  32.                 x += direction.dirs[direction.dir][0];
  33.                 y += direction.dirs[direction.dir][1];
  34.                 seen.add(x+”,”+y);
  35.                 if(sensor.detect()){
  36.                         /*code to move the roomba physically move forward*/
  37. clean();
  38.                         return true;
  39. }else return false;
  40. }

  41. public void moveBack(){
  42.         TurnRight(2);
  43.         move();
  44.         TurnRight(2);
  45. }


  46. void TurnLeft(int k){
  47.         for(int i = 0; i < k; i++)
  48.                 direction.turnL();
  49. }

  50.         void TurnRight(int k){
  51.                 for(int i = 0; i < k; i++)
  52.                 direction.turnL();
  53. }

  54. void Clean(){
  55.         /*code to call the robot physically clean the current area */
  56. }

  57. public void sweep(){
  58.         Direction prevDir = direction;
  59.                 for(int i = 0; i < 4; i++){
  60. TurnRight(1);
  61.         int nextx = x + direction.dirs[direction.dir][0];
  62.                         int nexty = y + direction.dirs[direction.dir][1];
  63.                         if(seen.contains(nextx+”,”+nexty)) continue;
  64.                         if(move()){
  65.                                 sweep();
  66. }
  67. }
  68. direction = prevDir;
  69. moveBack();
  70. }
  71. }
复制代码




评分

参与人数 3大米 +18 收起 理由
financeFree + 5 很有用的信息!
Killua1222 + 3 感激~~
sizem + 10 高頻

查看全部评分


上一篇:图森实习电面面经
下一篇:lyft level5 实习电面

本帖被以下淘专辑推荐:

推荐
Nooneknows 2018-11-6 13:10:40 | 只看该作者
全局:
为什么我觉得楼主的意思和蠡口不一样的。
原题是给了API的的方法,要扫整个屋子。楼主是说要直接去implement这些方法。。。
回复

使用道具 举报

推荐
cszhazha 2018-11-2 10:22:54 | 只看该作者
全局:
蠡口已经有原题了吧
回复

使用道具 举报

推荐
 楼主| 清水河醋鱼1995 2018-11-2 10:17:12 | 只看该作者
全局:
代码块排版有点乱,我再贴一下吧。。。

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();
}
}

评分

参与人数 1大米 +3 收起 理由
Killua1222 + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
 楼主| 清水河醋鱼1995 2018-11-2 10:41:20 | 只看该作者
全局:
cszhazha 发表于 2018-11-2 10:22
蠡口已经有原题了吧

才找到。。。谢谢了
回复

使用道具 举报

🔗
PepePls 2018-11-2 10:43:56 | 只看该作者
全局:
感觉这道题已经flop了...
回复

使用道具 举报

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

flop什么意思
回复

使用道具 举报

🔗
 楼主| 清水河醋鱼1995 2018-11-2 12:49:59 | 只看该作者
全局:
znyjose 发表于 2018-11-2 12:37
提个follow-up:如果地图没边界,或者没有足够空间存hashmap呢?

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

使用道具 举报

全局:
leetcode第几题啊
回复

使用道具 举报

🔗
hername 2018-11-2 17:20:33 | 只看该作者
全局:

蠡口 四八九
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表