Groupon Interview Question SDE1s
Country: India
@algos: what will happen if we reach the top most row or right most column i.e. when robot goes to the end of the grid?
Well question doesn't mention that but probably the interviewer wanted to know how to handle those cases otherwise this question looks pretty simple doesn't it?
that is corner case as question doesn't mention... here tricky part is to write efficient code for move M (move forward step)... otherwise it is easy.
when command is M? where does robot move? what is ch in your algorithm? how about forward[when it stops if say 1 position move]?
No matter what is the sequence of N, S, W< E, the net vertical movement will be number of(north) - number of (south), and similar for horizontal movement. So count number of f(N), f(S), f(E), and f(W). Final answer ( cur_x + f(N) - f(S)), cur_y + (f(E) - f(W) ).
Please note that i am assuming, bottom left slot is grid[0][0] and top right is grid[N][N]. The above formula may change a bit if this assumption is changed.
Net Vertical Movement = No Of Ns- No Of Ss
Net Horizontal Movement = No Of Es- No Of Ws
So its a simple array summation problem. Only thing to take care is at every summation the
horizontal sum <= (Right Edge-Current X Position)
and >=Left Edge-Current X Position
vertical sum <= (Top Edge-Current Y Position)
and >=Bottom Edge-Current Y Position
#include <stdio.h>
#include <conio.h>
#include <string.h>
int doAction(char, char *, int *, int *);
void main(){
int X=0,Y=0;
char command[20];
printf("Enter command: ");
gets(command);
int i=0, isActionPerformed = 1;
char currDrn = 'E';
while(command[i]){
isActionPerformed = doAction(command[i], &currDrn, &X,&Y);
if(!isActionPerformed){
printf("\nYou have entered wronge command.."); break;
}
i++;
}
if(isActionPerformed)
printf("\nFinal position of Robot is: (%d, %d).", X, Y);
getch();
}
int doAction(char ch, char *currDrn, int *X, int *Y){
switch(ch){
case 'E': *currDrn = ch; printf("\nTurned to East.."); break;
case 'W': *currDrn = ch; printf("\nTurned to West.."); break;
case 'N': *currDrn = ch; printf("\nTurned to North.."); break;
case 'S': *currDrn = ch; printf("\nTurned to South.."); break;
case 'M': if(*currDrn == 'N'){
if((*Y)-1 >= 0){
(*Y)--; printf("\n Moved one step towards North.");
}else{
printf("\n You have crossed top boundry limit..");
return 0;
}
}
else if(*currDrn == 'S'){
if((*Y)+1 < 10){
(*Y)++; printf("\n Moved one step towards South.");
}else{
printf("\n You have crossed bottom boundry limit..");
return 0;
}
}
else if(*currDrn == 'E'){
if((*X)+1 < 10){
(*X)++; printf("\n Moved one step towards East.");
}else{
printf("\n You have crossed left boundry limit..");
return 0;
}
}
else if(*currDrn == 'W'){
if((*X)-1 >= 0){
(*X)--; printf("\n Moved one step towards West.");
}else{
printf("\n You have crossed right boundry limit..");
return 0;
}
}
break;
default: return 0;
}
return 1;
def robot_move(position, sequence):
move_map = {
'N': (0, -1),
'S': (0, 1),
'E': (1, 0),
'W': (-1, 0),
}
def make_move(current, command):
pos, facing = current
if command == 'M':
h, v = move_map[facing]
return ((pos[0] + h, pos[1] + v), facing)
else:
return (pos, command)
# have to set arbitrary initial facing since problem doesn't mention it
return reduce(make_move, sequence, (position, 'N'))[0]
Questions isn't clear, NEWS are not going to change position, they just make the robot turn to face that direction or are they? If so how many directions ever are beside each other, only the last one makes sense. ex: NEWS, robot turns to face north, then east, then west and then south, finally robot faces south there is no effect of NEW.
public static void position(char[] arr, int row, int col) {
int currPos = 0;
for (int i = 1; i < arr.length; i++) {
switch (arr[i]) {
case 'N':
currPos = 1;
break;
case 'S':
currPos = 2;
break;
case 'W':
currPos = 3;
break;
case 'E':
currPos = 4;
break;
case 'M':
switch (currPos) {
case 1:
row--;
break;
case 2:
row++;
break;
case 3:
col--;
break;
case 4:
col++;
break;
}
break;
}
}
System.out.println("Current Position : [" + row + ", " + col + "]");
}
Point Move(int x,int y,int m,int n,List<Character> list) {
Point cur=new Point(x,y);
char direction;
for(char c:list) {
switch (c) {
case 'N' : direction='N'; break;
case 'S' : direction='S';break;
case 'E' : direction='E';break;
case 'W': direction='W';break;
case 'M': cur=getNext(cur,direction,m,n); if(cur==null) return null; break;
default: break;
}
}
}
Point getNext(Point p,char direction,int m,int n) {
switch (direction) {
case 'N' : if(p.x-1>=0) { p.x--; return p; }
else return null;
break;
case 'S' :...
}
}
Here is simple js solution
I'm nor sure is it correct, but I choose beginning of coordinates as [0, 0] in left bottom side
In this case robot goes out of screen with directions from example
/**
* Abstraction of grid
*
* @param {Number} width
* @param {Number} height
*
* @constructor
*/
var Grid = function(width, height) {
/**
* Grid width
*
* @type {Number}
*/
this.width = width;
/**
* Grid height
*
* @type {Number}
*/
this.height = height;
/**
*
* @type {null|Robot}
*/
this.robot = null;
};
/**
* Add robot to grid
*
* @param {Robot} robot
*/
Grid.prototype.addRobot = function(robot) {
this.robot = robot;
if (!this._isFit()) {
throw new Error('Robot not fit');
}
};
/**
*
*
*/
Grid.prototype.update = function() {
if (!this._isFit()) {
throw new Error('Robot not fit');
}
};
/**
* Checks is robot fit in grid
*
* @returns {boolean}
* @private
*/
Grid.prototype._isFit = function() {
return this.robot.x>=0
&& this.robot.y >=0
&& this.robot.x < this.width
&& this.robot.y < this.height;
};
/**
*
* Abstraction of robot
*
* @param {Number} x
* @param {Number} y
* @param {string} direction
* @constructor
*/
var Robot = function(x, y, direction) {
/**
* X coordinate
*
* @type {Number}
*/
this.x = x;
/**
* X coordinate
*
* @type {Number}
*/
this.y = y;
/**
* Current direction
*
* @type {string}
*/
this.direction = direction || 'N';
/**
* Available directions
*
* @type {string[]}
* @private
*/
this._directions = [
'N',
'S',
'E',
'W'
];
};
/**
* Make step - move or change direction
*
* @param step
*/
Robot.prototype.step = function (step) {
if (this._isDirection(step)) {
this.direction = step;
} else {
this._move();
}
};
/**
* Check is step direction
*
* @param step
* @returns {boolean}
* @private
*/
Robot.prototype._isDirection = function (step) {
return this._directions.indexOf(step) !== -1;
};
/**
* Move robot to direction
*
* @private
*/
Robot.prototype._move = function () {
switch(this.direction){
case 'N':
this.y++;
break;
case 'S':
this.y--;
case 'W':
this.x++;
break;
case 'E':
this.x--;
};
};
var grid = new Grid(100, 500);
var robot = new Robot(5, 3);
grid.addRobot(robot);
['N','S', 'M', 'M', 'E', 'W', 'E', 'S' , 'M', 'S', 'M'].forEach(function(step){
robot.step(step);
grid.update();
});
console.log(robot);
package test;
import java.util.HashMap;
import java.util.Scanner;
public class Solution {
private static HashMap<String, Integer[]> map = new HashMap<String,Integer[]>();
static {
map.put("N", new Integer[]{0, -1});
map.put("S", new Integer[]{0, 1});
map.put("E", new Integer[]{1, 0});
map.put("W", new Integer[]{-1, 0});
}
public static void main(String[] args) {
// TODO Auto-generated method stub
@SuppressWarnings("resource")
Scanner input = new Scanner(System.in);
String command = input.next();
String currdir = "N";
int currXPos = 0;
int currYPos = 0;
while(!command.equals("X")){
switch(command){
case "N" :
case "S" :
case "E" :
case "W" :
currdir = command;
break;
case "M" :
currXPos += map.get(currdir)[0]; System.out.println("Move in X direction" + currXPos);
currYPos += map.get(currdir)[1];System.out.println("Move in Y direction" + currYPos);
break;
default:
break;
}
System.out.println("Current direction is " + currdir);
command = input.next();
}
}
}
- algos April 03, 2013initial position is at (row, col), int ch=0 if(a[i] == 'N' || (a[i] == 'M' && ch == 1)) { row--; ch = 1; } else if(a[i] == 'S' || (a[i] == 'M' && ch == 2)) { row++; ch = 2; } else if(a[i] == 'E' || (a[i] == 'M' && ch == 3)) { col++; ch = 3; } else if(a[i] == 'W' || (a[i] == 'M' && ch == 4)) { col--; ch = 4; } final position will be at (row, col)