Google_SweepingRobot [source code]
public class Google_SweepingRobot {
/* Global toggles for debugging and configuration */
/* Toggle this to see the DFS trace */
static boolean DEBUG = false;
/* Used to toggle the initialization settings for Robot, indicate difficulty of task */
static boolean HARD_MODE = false;
static Random rd = new Random ();
/* What Google gives you: an interface */
static interface Robot {
boolean move ();
// In harder versions of the problem, parameterized move is not allowed, so try not to use that
// 0 up 1 right 2 down 3 left
boolean move (int direction);
//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 ();
}
/* A class that implements the Robot interface
You do not need to read or understand this class, but might be helpful to help see what's happening */
static class MyRobot implements Robot {
// 0 empty, 1 dirty, 2 obstacle
int[][] grid;
int x, y, face;
static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public MyRobot (int[][] _grid) {
this.grid = _grid;
if (!HARD_MODE) {
// In easy mode Clean knows Robot starts at (0,0) facing 0(UP)
this.x = 0;
this.y = 0;
this.face = 0;
} else {
// In hard mode Clean does not know where Robot's starting position and face
while (true) {
this.x = rd.nextInt (this.grid.length);
this.y = rd.nextInt (this.grid[0].length);
if (this.grid[this.x][this.y] < 2)
break;
}
this.face = rd.nextInt (4);
}
}
/* Naive implementation of Robot interface below */
public boolean move () {
return move (this.face);
}
public boolean move (int d) {
assert d >= 0 && d <= 3;
int nx = this.x + dirs[d][0], ny = this.y + dirs[d][1];
if (!canMove (nx, ny))
return false;
this.x = nx;
this.y = ny;
return true;
}
boolean canMove (int x, int y) {
return x >= 0 && y >= 0 && x < this.grid.length && y < this.grid[0].length
&& this.grid[x][y] < 2;
}
public void turnLeft (int k) {
assert k >= 0;
this.face = (this.face - k + 4) % 4;
}
public void turnRight (int k) {
assert k >= 0;
this.face = (this.face + k) % 4;
}
public void clean () {
assert this.grid[this.x][this.y] < 2;
this.grid[this.x][this.y] = 0;
}
}
/* Util functions for development, esp. for debugging */
static class Util {
/* Print out a grid */
static String printGrid (int[][] grid) {
StringBuilder sb = new StringBuilder ();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
sb.append (grid[i][j] + " ");
}
if (i < grid.length - 1)
sb.append ("\n");
}
return sb.toString ();
}
/* Use color printing to trace the status of the grid during printing */
static String traceGrid (int[][] grid, boolean[][] visited, int x, int y, int in_direction) {
StringBuilder sb = new StringBuilder ();
sb.append (String.format ("(%d, %d) direction: (%d)\n", x, y, in_direction));
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
sb.append (Util.wrap (grid[i][j] + "", i == x && y == j ? 95 : (visited[i][j] ? 95 : 0)) + " ");
}
if (i < grid.length - 1)
sb.append ("\n");
}
return sb.toString ();
}
static String traceGrid (int[][] grid, Set<String> visited, int x, int y, int in_direction) {
StringBuilder sb = new StringBuilder ();
sb.append (String.format ("(%d, %d) direction: (%d)\n", x, y, in_direction));
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
sb.append (Util.wrap (grid[i][j] + "", i == x && y == j ? 95 :
(visited.contains (MyClean.key (i, j)) ? 95 : 0)) + " ");
}
if (i < grid.length - 1)
sb.append ("\n");
}
return sb.toString ();
}
static String wrap (String s, int code) {
return (char) 27 + "[" + code + "m" + s + (char) 27 + "[0m";
}
static String separator () {
return (char) 27 + "[36m" + "========================" + (char) 27 + "[0m";
}
}
/****************************************************************************/
/* Real solutions in this segment: what you are expected to write in an actual interview */
/* Easy version of the solution: you can assign the start position/face of the robot
For convenience, I chose (0,0) and 0 here. */
static class MyCleanEasy {
Robot r;
int[][] grid;
boolean[][] visited;
static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
MyCleanEasy (int[][] _grid) {
this.grid = _grid;
this.r = new MyRobot (_grid);
cleanGrid ();
}
void cleanGrid () {
this.visited = new boolean[this.grid.length][this.grid[0].length];
dfs (0, 0, 0);
}
/* in_direction is the direction that we entered this cell with */
void dfs (int x, int y, int in_direction) {
visited[x][y] = true;
r.clean ();
if (DEBUG) System.out.println ("\n" + Util.traceGrid (this.grid, this.visited, x, y, in_direction) + "\n");
for (int i = 0; i < 4; i++) {
if (i > 0)
r.turnRight (1);
// subtle but critical: you can't use i directly
int nedir = (in_direction + i) % 4;
int nx = x + dirs[nedir][0], ny = y + dirs[nedir][1];
if (inBound (nx, ny) && !visited[nx][ny] && r.move ()) {
dfs (nx, ny, nedir);
}
}
r.turnRight (1);
r.turnRight (2);
r.move ();
r.turnRight (2);
}
boolean inBound (int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length;
}
}
/* Hard mode: Cleaner does not Robot's starting position and face */
static class MyClean {
Robot r;
int[][] grid;
/* Records coordinates in RELATIVE coordinate space! can contain negative
values or out-of-bound values thus string is safer than hashed int. */
Set<String> visited;
static int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
MyClean (int[][] _grid) {
this.grid = _grid;
this.r = new MyRobot (_grid);
cleanGrid ();
}
void cleanGrid () {
this.visited = new HashSet<> ();
/* In RELATIVE space, we still start at (0,0) facing 0: it does not affect what the
robot actually do in ABSOLUTE space */
dfs (0, 0, 0);
}
void dfs (int x, int y, int in_direction) {
visited.add (key (x, y));
r.clean ();
if (DEBUG) System.out.println ("\n" + Util.traceGrid (this.grid, this.visited, x, y, in_direction) + "\n");
for (int i = 0; i < 4; i++) {
if (i > 0)
r.turnRight (1);
int nedir = (in_direction + i) % 4;
int nx = x + dirs[nedir][0], ny = y + dirs[nedir][1];
// If you have not visited it in RELATIVE coordinate space, then you can go there in ABSOLUTE coordinate space
if (!visited.contains (key (nx, ny)) && r.move ()) {
dfs (nx, ny, nedir);
}
}
r.turnRight (1);
r.turnRight (2);
r.move ();
r.turnRight (2);
}
static String key (int x, int y) {
return (new StringBuilder ()).append (x).append (",").append (y).toString ();
}
}
/****************************************************************************/
public static void main(String[] args) {
int[][][] inputs = {
{
{1, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 2, 0, 0, 0, 0, 1, 0},
{2, 2, 2, 0, 2, 2, 2, 2},
{0, 1, 0, 0, 0, 1, 0, 1},
},
{
{0, 0, 0, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 2, 0, 0, 0, 0, 0, 0},
{2, 2, 2, 0, 2, 2, 2, 2},
{0, 0, 1, 0, 0, 0, 1, 0},
},
{
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 2, 0, 0, 0},
{1, 2, 0, 0, 2, 1, 0, 0},
{2, 2, 2, 0, 2, 2, 2, 2},
{1, 0, 0, 0, 0, 0, 0, 0},
},
{
{1, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 0},
{0, 2, 0, 0, 0, 0, 1, 0},
{2, 2, 2, 0, 2, 2, 2, 2},
{0, 1, 0, 0, 0, 1, 0, 1},
},
{
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 1, 2, 0, 0, 0},
{0, 2, 0, 0, 2, 1, 0, 0},
{2, 2, 2, 1, 2, 2, 2, 2},
{0, 1, 0, 0, 1, 0, 0, 1},
},
};
for (int i = 0; i < inputs.length; i++) {
System.out.println (Util.separator ());
int[][] grid = inputs[i];
int[][] easy_grid = new int[grid.length][grid[0].length];
for (int r = 0; r < grid.length; r++) for (int c = 0; c < grid[0].length; c++)
easy_grid[r][c] = grid[r][c];
HARD_MODE = false;
System.out.printf ("Task Difficulty: %s\n", HARD_MODE ? "HARD" : "EASY");
System.out.printf ("before sweeping: \n%s\n\n", Util.printGrid (easy_grid));
new MyCleanEasy (easy_grid);
System.out.printf ("after sweeping: \n%s\n\n", Util.printGrid (easy_grid));
HARD_MODE = true;
System.out.printf ("Task Difficulty: %s\n", HARD_MODE ? "HARD" : "EASY");
System.out.printf ("before sweeping: \n%s\n\n", Util.printGrid (grid));
new MyClean (grid);
System.out.printf ("after sweeping: \n%s\n\n", Util.printGrid (grid));
}
}
}
当时看的那个python的帖子, 他的写法是board和robot之间也有完全的隔离的; 意思就是robot其实不维护自己的坐标, 坐标怎么保存呢? 他的board里面除了0,1,2三种cell之外, 还有一种cell就是3, 代表robot的位置;
真正为了面试的需求, 我就不做这个了, 直接就认为robot可以维护自己的坐标就行了;
写的过程中不断理解这个问题的难点;
这个问题的一个最大的难点原因就是你作为robot的client, 你实际上是无法知道robot的坐标的; 这个后面有看到一个帖子里面, 当面试人表示做不出来的时候, 面试官主动降低难度, 说你可以直接get robot的坐标, 那么那个就很简单了, 一个暴力DFS搞定;
我作为一个robot的驾驶员, 我希望能够维护我现在所走过的位置和方向; 但是这个很难, 因为我驾驶的这个robot, 没有窗户, 我不知道我的绝对方向, 也不知道我的绝对位置;
这个就是这道题的设定;
那个Python解法最后的解决方案是, 虽然我不知道我的绝对方向和位置, 但是我, 作为驾驶员, 维护自己的一套相对方向和位置, 参照系就是机器人本身一开始的绝对方向和位置;
只要我能够保证我在这个相对空间里面, 把所有的位置都扫一遍, 那么绝对空间也肯定已经扫完整了;
感觉下面第一个帖子里面的那个讲法不是很准确啊; DFS怎么还能带xy参数的; 或许他当时做的就是一个相对参数的概念?
自己实现的时候想到的另外一个难题, 就是我们驾驶员究竟能不能设定这个robot的起点; 如果可以设置, 最后实际上题目就简单不少: 虽然说我们没有办法明确的query出来robot的坐标和face, 但是因为我们知道他的起点, 而且他的所有动作都是我们控制的, 所以最后我们的平行的相对坐标维护的就跟robot自己实际维护的坐标是一模一样的;
这个时候我们对于坐标的控制也可以更加的精确, 比如, visited就可以直接用一个boolean matrix来做就行了;
但是如果我们的相对坐标跟robot自己实际的绝对坐标不一致, 那么问题就复杂很多, 比如说, 绝对坐标(0,0)对应的相对坐标可能是(-1,0)这种有负数的超界的, 那么最起码你visited就只能用set来做了(用matrix也能做, 要算offset麻烦一些);
而且clean这一层, 也没有办法直接query一个(x,y)是否in bound, 因为你手上抓的是一个相对位置, 你判断这个相对位置有没有超界根本没有用;
这个时候, 超界判断也只能完全借助于robot自己的move函数的返回值才能知道; 你可能觉得这个挺无所谓的, 但是一个小问题就是, robot虽然不会走出界或者走进obstacle, 但是他可能走进已经visited过的cell, 而且这个move会返回true, 而且这个时候robot已经成功进入这个重复的cell, 你怎么办? undo往往是一件很麻烦的事情;
为了题目简单, 我先做一个简单版本的, 也就是我可以指定robot的绝对起点位置的, 这个真的是简单很多;
即使是这个简单版本的, 实际上写起来也很麻烦, 因为你debug的时候就知道了, 脑子里要维护两套recursive trace, 一个是你的cleaner在相对坐标空间的trace, 一个是robot里面存的绝对坐标的trace; 写代码的时候稍微有点不小心, 这两个trace就不同步了;
最后稍微磕磕绊绊的把easy版本的写出来了(可以给robot指定起始位置), 一个稍微tricky的地方是, 这个in_direction的参数, 我一开始以为是没有用的(我只是为了用来debug的时候观察DFS的朝向的), 实际上完全是有用的;
每一个下一个recursive的位置, 必须用nedir = (in_direction + i) % 4计算出来这个, 也就是说i是一个offset, 然后用nedir去index dirs, 才对, 而不能直接用i去index, 因为i并没有和robot本身的face进行完美同步; i只是一个offset, 只有i和当前iteration开始的起点direction, 也就是in_direction组合, 才能保证你始终和robot的实际绝对方向进行了同步;
讲的有点乱, 但是这个点真的是有点subtle;
那么来实现hard版本;
hard模式这个的一个重要难点就是你在驾驶员的角度, 你已经无法帮助你的robot去判断, 前方是否出界, 能不能走了; 只能等robot告诉你;
如果你驾驶员手动用inBound这种操作来告诉robot前面不能走之类的信息, 最后robot会漏掉很多cell;
注意, 这个不会导致robot报错, 比如一个地方你认为能走, 但是实际上绝对坐标空间里面是不能走的, 那么robot会不会走出界呢? 不会的, 因为robot的move有自己的保护系统, 当你给了robot一个不合理的前进位置之后, robot自己会走动无视你的这个指令, 只不过你自己不知道而已;
总结下来, DFS的过程中, 前方能不能走, 必须完全依赖于robot的move给的返回值;
这个看起来不是很难, 但是要在这个限制下面实现visited, 困难不少;
一个思路就是, 相对坐标空间肯定要允许超界坐标(负数或者过大的), 然后这些坐标维持一个去重, 我感觉应该能够保证绝对坐标也能够做到去重;
或许可以用hash的方法来做这个set, 但是我们先用string写, 保险一点: 简单升级.
如果是用string也可以加一点memo之类的(我的key函数这里), 不过这个也是小问题, 先不管;
没想到很轻松的结束了? 基本把inBound函数给删除之后, 然后visited改成set(但是还是得用visited来短路move), 就直接就过了?
那这个题目基本就过了, 反正还是很有意思的;
!visited.contains (key (nx, ny)) && r.move ()这一句应该是一个看起来简单, 但是是这个问题的核心难点, 用相对坐标空间的去重来保护绝对坐标空间的move;
最后我的实现我感觉跟他们的描述还是有点区别的, 但是我自认为我这个实现还是很简洁的;
board和robot的组合关系其实无所谓, 反正面试也不让你写这个, 不过如果真的自己设计, 按照之前那个Python帖子的方法去decouple也是一个不错的思路;
与那个Python帖子不同的地方在于, 这题我最后也没有特意跟他那样去写PostOrder, 所以这个应该是细节取舍问题, 关键是设计整体完整一致就行;
唯一的一点草稿, 没啥大用处:
Problem Description
Google的经典面试题, 自己写一下看看, 不追求太多骚操作, 能够用基本的DFS写完就行了;
先收集一下描述这个题目的帖子:
1
http://www.1point3acres.com/bbs/thread-345555-1-1.html
Robot Clearner
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.
意思就是如果无法移动, 那么指令作废;
The control API:
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 (); boolean move (Direction d); //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 (); }
下面回复:
我面试面了这道题最后过了。我是dfs，用一个set记录visited。设定起点是原点，dfs helper函数要传机器人当前方向，用0123表示就可以。每一个helper函数用for循环走四次。每一次按照顺时针或者逆时针转一下。把走过的坐标和cannot move的点都放进visited。最重要的是走完发现无路可走之后要再转向后方走一步再转向后，也就是返回上级helper函数时机器人所在的位置和面朝的方向
这个人的回复是赞同最多的, 只看了他的解答, 是这些:
我面试的时候小哥说我是他面过的第一个把这道题题和followup都做完的candidate。难点在于一是包了api进去要手动控制方向，二是要参数具体化这个房间。
所以这题其实真的是很难的;
一个人问他:
差不多是这个意思？
void dfs(x, y, back_direction) { if(visited(x, y)) return; visited.add(x,y); if(move(UP)) dfs(x, y - 1, DOWN); if(move(LEFT)) dfs(x - 1, y, RIGHT); if(move(DOWN)) dfs(x, y + 1, UP); if(move(RIGHT)) dfs(x + 1, y, LEFT); move(back_direction); }
大牛回复:
差不多。但是api给的是顺时针转逆时针转。所以四个if里面应该是转0次1次2次3次。然后cannot move的点是房间边界或者障碍物。也要加进visited
追问:
在dfs当前层，假如机器人朝向north，那么上左下右4个方向，在进入下一层递归之前，也要调整机器人方向，使其始终朝向north？ 比如moveLeft，就是turn left(1), move one step, turn right(1)，机器人还是朝向north？
回答:
不需要。下一层helper时机器人的方向无所谓。但是无路可走时需要返回上一步的位置和方向。比如说现在在原点。现在执行这层helper的第（1/2/3/4）次loop。需要turn（0/1/2/3次）再move。现在在新点。从这个点再执行helper。发现无路可走就需要回到原点。因为你原点的helper要执行forloop四次。有可能没执行完全部四次。这就需要控制机器人回到原点并朝向刚来原点时候的方向。这样再执行下一个loop的时候turn的次数才和loop数相关。
下面其他人继续讨论:
这题需要注意的点 楼里有人已经说得很详细了 就是dfs+自己定义一种方式hash已经走过的格子+手动在递归函数结束时调整机器人的方向的位置
重点就是自己写一遍 然后跑test case 光看别人的代码 很容易忽略里面的细节
我记得难点就是递归的时候方向转换的问题
我重新回想了一下我自己原来对这个题目理解的误区, 你看他这里给的题目描述, robot本身最后给你的实际上是一个interface! 这个是什么意思? 你不能指望robot记录所有的类似visited coordinates这样的state的, 没有这些API给你用; 知道这个, 这题就很难了;
现在反正还是在继续思考阶段, 在构建怎么设计这个东西; again, 因为robot本身就是一个interface, 所以思考的方向有点改变; 我现在的想法就是, robot的constructor直接把board, which就用一个int matrix来表示算了, 扔给robot; 然后robot里面有其他的各种自己的函数, 比如canMove这种, 撞墙的讨论, 就是需要有一个读取board的操作的过程才能知道这个;
我第一次看这个robot题的时候就是看的下面的那个帖子, 不过我不准备跟他一样给board一个单独的class; 直接一个int matrix扔给robot, 然后自己做去了;
毕竟是以面试为中心的, 主要集中在Clean的实现逻辑上面, 而且面试的时候其实不用你写robot这个类的; 知道怎么用就行;
不过自己写的玩的时候, 最好还是实现一个具体的robot;
大牛上面说的时候, 有一句
设定起点是原点
这个是什么意思? 我记得下面那个帖子里面那个人写的函数, 是无视robot的初始化条件(起点位置和起始方向)的; 那么这个或许是可以在面试的时候跟面试官沟通的一个地方?
自己现在写的玩最好还是写的general一点;
看上面那个人的回复, 感觉是允许记录绝对坐标的样子? 他的DFS函数也是带(x,y)参数的, 既然这样, 为什么不允许记录坐标? 你没有办法给robot指定坐标, 但是可以给DFS函数指定坐标?
感觉也不是很靠谱的样子, 你就算给DFS指定了绝对坐标, robot无法知道, 又有什么用呢?
既然下一个帖子那个OP都知道可以用相对坐标的方法做出来, 那么我就尝试一下就好了;
DFS函数从parent过来的时候要传一个回头的back_direction, 或许是一个好办法; 感觉这个是一个关键点啊, 脑子里跑一下, 确实是, 知道怎么回头, 类似于DFS的上行, 是很重要的; 注意了, 这个题目为什么难, 比如你可能认为, 不就是一个DFS吗? 关键是你平时写DFS的时候, 你的recursion tree这些上行下行, 其实都是系统自动帮你维护好的;
现在你有点类似说自己要维护一个robot这个类似PC的东西, 自动的在整个recursion tree上面走动;
当然, 这个比真正维护recursion Stack是要简单一些的, 因为这题实际上是允许重复走一个格子的;
上面那个人给的snippet看起来有点像是什么order? 他没写clean函数的调用; 也没什么order;
大牛最后的那个描述, 讲的不是特别清晰, 但是大概懂一个意思了; 写写看;
2
这个帖子更加的详细:
http://www.1point3acres.com/bbs/thread-403845-1-1.html
Given a robot cleaner in a room modeled as a grid.
Each cell in the grid can be empty or blocked.
The robot cleaner with 4 given APIs 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.The 4 APIs are:
clean(): clean the current location.
turnleft(k=1): turn leftk*90degrees.
turnrigt(k=1): turn rightk*90degrees.
move(direction=None): move forward for 1 position, return False if that’s not possible.
题目描述差不多;
3
一个在电面的时候就碰到这题的人:
http://www.1point3acres.com/bbs/thread-289514-1-1.html
可能因为是电面, 所以面试官给了一个降低难度:
于是面试官简化
简化1：robot自己可以知道自己当前的位置。就是两个新API：robot.x(), robot.y()
虽然说这个我也不需要, 但是可以看出来, 绝对空间和相对空间的isolation基本可以实锤是这题的核心难点了;