Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
this will not work if
char [][] maze = {{'a','b','c','d','e'},
{'f','g','h','i','j'},
{'k','l','m','n','o'},
{'p','q','r','s','t'},
{'u','v','w','x','y'},
{'z'}};
I think just change the print order a little bit, then it will work:
yMove<0
=> xMove<0
=> yMove>0
=>xMove<0
assume its a graph as links to element on left, right, top and bottom. use bellman ford or any other algorithms to find shortest path between all nodes. Then its just about searching the start and end points in a 26x26 array.
In general and random set, that would work just fine. Here we have ordered set so we have good understanding if we need to go up or down or left or right.
BTW, in order to avoid 'z' problem, if preference is always given to go up or down then... there is no 'z' problem because we always go up from 'z'.
C++ solution.
void Remote(string word)
{
// Start at top left
int cur_x = 0;
int cur_y = 0;
cout << "Starting at: a" << endl << endl;
for(size_t i=0; i < word.size(); i++) {
cout << word[i] << ": ";
int idx = word[i] - 'a';
// 6x5 grid
int dst_y = idx / 5;
int dst_x = idx % 5;
if(word[i] == 'z') { // special case: dest is 'z', can reach always with left + down
int left = cur_x;
int down = dst_y - cur_x;
for(int j=0; j < left; j++)
cout << "Left ";
for(int j=0; j < down; j++)
cout << "Down ";
}
else { // can reach any letter with up/down + left/right
int dx = dst_x - cur_x;
int dy = dst_y - cur_y;
for(int j=0; j < abs(dy); j++) {
if(dy > 0)
cout << "Down ";
else
cout << "Up ";
}
for(int j=0; j < abs(dx); j++) {
if(dx > 0)
cout << "Right ";
else
cout << "Left ";
}
}
cout << "OK" << endl;
cur_x = dst_x;
cur_y = dst_y;
}
}
int main()
{
Remote("zoosi");
}
Starting at: a
z: Down Down Down Down Down OK
o: Up Up Up Right Right Right Right OK
o: OK
s: Left Down OK
i: Up Up OK
Why would you have a special case for Z? If you switch the order so that it processes y first before x, then it would always go up then right if original position is at z
But did you really test the code? You only have the special case when destination is 'z'. What if you are currently at 'z' and destination is 'c'. Your code would go to the else case and then try to process the x direction first, which results in going to right before going up. It doesnt look like it will output what you show.
#include "stdio.h"
#include "conio.h"
#include "string.h"
#define kColumnCount 5
char maze[6][kColumnCount] ={
{'a','b','c','d','e'},
{'f','g','h','i','j'},
{'k','l','m','n','o'},
{'p','q','r','s','t'},
{'u','v','w','x','y'},
{'z',' ',' ',' ',' '}};
int xp = 0, yp = 0;
void printStepsForMessage(char *mess)
{
for(int i=0;i<strlen(mess);i++)
{
int asciVal = mess[i]-'a';
if(asciVal<0||asciVal>25)
continue;
int y = asciVal/kColumnCount;
int x = asciVal%kColumnCount;
if(xp<x)
{
for(;xp<x;xp++)
printf("Move Right\n");
}
else if(xp>x)
{
for(;xp>x;xp--)
printf("Move Left\n");
}
if(yp<y)
{
for(;yp<y;yp++)
printf("Move Down\n");
}
else if(yp>y)
{
for(;yp>y;yp--)
printf("Move Up\n");
}
printf ("OK/to select %c\n", mess[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
printStepsForMessage(" ");
printStepsForMessage("mapzansz ");
getch();
return 0;
}
Not sure why so much very hard to read code is dumped here...
Let's consider 'con'. The distance between 'c' and 'o' is 'o'-'c'=12. This means currently we are 12/5=2 rows up and 12%5=2 cols left. So go down 2 and right 2. Similarly 'n'-'o'=1, so we are 0 rows down/up and 1 col to the left. Thus just go 1 to the right. We must be careful to stay in bounds, i.e. if the word is 'conq' then diff is 3 but we are at distance of 2 from the border (we always know where we are) then we have to wrap, i.e. add a row and go left instead of right. I guess the devil is in details :)
public void findCharSequence(String word) {
int currX = 0, currY = 0;
for (int i = 0; i < word.length(); i++) {
int charValue = word.charAt(i) - 'a';
int destX = charValue % 5; // no need to -1 since charValue already starts from 0
int destY = charValue / 5;
for (int j = 0; j <= Math.abs(currY-destY); j++) {
if (currY-destY < 0) // if currY is row 1, and destY is row 3
print "Down"
else
print "Up"
}
for (int j = 0; j <= Math.abs(currX-destX); j++) {
if (currX-destX < 0) // if currX is col 1, and destX is col 3
print "Right"
else
print "Left"
}
print "OK"
currX = destX;
currY = destY;
}
}
Will this work? Anyone?
public static void findCharSequence(char[][] m, String word) {
int currX = 0, currY = 0;
for (int i = 0; i < word.length(); i++) {
int charValue = word.charAt(i) - 'a';
int destX = charValue % 5; // no need to -1 since charValue already starts from 0
int destY = charValue / 5;
// inclusive, a -> c, starting from 1, so that we can use j to print
for (int j = 1; j <= Math.abs(currY-destY); j++) {
if (currY-destY < 0) // if currY is row 1, and destY is row 3
System.out.println("Down //we are at " + m[currY+j][currX]);
else
System.out.println("Up //we are at "+ m[currY-j][currX]);
}
for (int j = 1; j <= Math.abs(currX-destX); j++) {
if (currX-destX < 0) // if currX is col 1, and destX is col 3
System.out.println("Right //we are at "+ m[destY][currX+j]);
else
System.out.println("Left //we are at " + m[destY][currX-j]);
}
System.out.println("OK //to select " + m[destY][destX]);
currX = destX;
currY = destY;
}
}
For "zoosi":
Down //we are at f
Down //we are at k
Down //we are at p
Down //we are at u
Down //we are at z
OK //to select z
Up //we are at u
Up //we are at p
Up //we are at k
Right //we are at l
Right //we are at m
Right //we are at n
Right //we are at o
OK //to select o
OK //to select o
Down //we are at t
Left //we are at s
OK //to select s
Up //we are at n
Up //we are at i
OK //to select i
I don't think we will need a special case for z if we process y direction before x direction.
{
// typepat.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<stdio.h>
#include<conio.h>
#include<string.h>
int main()
{
char str[6][5],sub[20];
int i,j,loci,locj,m,n,p,len,k=0;
m=0;
n=0;
p=97;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
str[i][j]=p;
p++;
}
}
str[5][0]=p;
str[5][1]=str[5][2]=str[5][3]=str[5][4]=32;
for(i=0;i<6;i++)
{
for(j=0;j<5;j++)
{
printf("%c\t",str[i][j]);
}
printf("\n");
}
printf("\nEnter a string: ");
gets(sub);
printf("\n------------------\n");
len=strlen(sub);
p=0;
while(sub[p]!='\0')
{
for(i=0;i<6;i++)
{
for(j=0;j<5;j++)
{
if((sub[p]==str[i][j]&&sub[p]!='\0'))
{
loci=i;
locj=j;
break;
}
}
}
p++;
while(m<loci)
{
printf("PRESS DOWN ARROW\n");
m++;
}
while(n<locj)
{
printf("PRESS RIGHT ARROW\n");
n++;
}
while(n>locj)
{
printf("PRESS LEFT ARROW\n");
n--;
}
while(m>loci)
{
printf("PRESS UP ARROW\n");
m--;
}
if(m==loci&&n==locj)
{
printf("PRESS OK\n");
}
k++;
}
getch();
return 0;
}
}
import java.util.LinkedList;
import java.util.Queue;
public class Maze
{
private static char[][] maze = null;
static
{
maze = new char[6][5];
maze[0][0] = 'a';
maze[0][1] = 'b';
maze[0][2] = 'c';
maze[0][3] = 'd';
maze[0][4] = 'e';
maze[1][0] = 'f';
maze[1][1] = 'g';
maze[1][2] = 'h';
maze[1][3] = 'i';
maze[1][4] = 'j';
maze[2][0] = 'k';
maze[2][1] = 'l';
maze[2][2] = 'm';
maze[2][3] = 'n';
maze[2][4] = 'o';
maze[3][0] = 'p';
maze[3][1] = 'q';
maze[3][2] = 'r';
maze[3][3] = 's';
maze[3][4] = 't';
maze[4][0] = 'u';
maze[4][1] = 'v';
maze[4][2] = 'w';
maze[4][3] = 'x';
maze[4][4] = 'y';
maze[5][0] = 'z';
maze[5][1] = ' ';
maze[5][2] = ' ';
maze[5][3] = ' ';
maze[5][4] = ' ';
}
public void pathFinder(String word)
{
if (word == null || word.length() == 0)
{
return;
}
Queue<Corridante> queue = new LinkedList<>();
for (char c : word.toCharArray())
{
queue.add(new Corridante((c - 'a') / 5, (c - 'a') % 5));
}
findPath(queue, word);
}
private void findPath(Queue<Corridante> queue, String word)
{
Corridante pre = new Corridante(0, 0);
int xMove = 0;
int yMove = 0;
while (!queue.isEmpty())
{
Corridante cur = queue.poll();
xMove = cur.x - pre.x;
yMove = cur.y - pre.y;
int i = pre.x;
int j = pre.y;
if (xMove > 0)
{
for (i = pre.x + 1; i <= pre.x + xMove; i++)
{
System.out.println("DOWN//Now we are on: " + maze[i][j]);
}
i--;
}
else if (xMove < 0)
{
for (i = pre.x - 1; i >= pre.x + xMove; i--)
{
System.out.println("UP//Now we are on: " + maze[i][j]);
}
i++;
}
if (yMove > 0)
{
for (j = pre.y + 1; j <= pre.y + yMove; j++)
{
System.out.println("LEFT//Now we are on: " + maze[i][j]);
}
j--;
}
else if (yMove < 0)
{
for (j = pre.y - 1; j >= pre.y + yMove; j--)
{
System.out.println("RIGHT//Now we are on: " + maze[i][j]);
}
j++;
}
System.out.println("OK//To select: " + maze[i][j]);
pre = cur;
}
System.out.println("------------------------------------");
}
}
Python:
def find_path(word, box):
curs = 0
steps = []
for letter in word:
code = ord(letter) - ord(box[0][0])
curs_row = curs / len(box[0])
code_row = code / len(box[0])
dy = code_row - curs_row
curs_pos = curs - curs_row * len(box[0])
code_pos = code - code_row * len(box[0])
dx = code_pos - curs_pos
dy_before_dx = True
if len(box[curs_row]) < len(box[0]):
dy_before_dx = True
elif len(box[code_row]) < len(box[0]):
dy_before_dx = False
if dy_before_dx:
items = ((dy, 'down', 'up'), (dx, 'right', 'left'))
else:
items = ((dx, 'right', 'left'), (dy, 'down', 'up'))
for d, first_dir, second_dir in items:
while d != 0:
if d > 0:
d -= 1
steps.append(first_dir)
else:
d += 1
steps.append(second_dir)
steps.append('click')
curs = code
for step in steps:
print step
box = [
['a', 'b', 'c', 'd', 'e'],
['f', 'g', 'h', 'i', 'j'],
['k', 'l', 'm', 'n', 'o'],
['p', 'q', 'r', 's', 't'],
['u', 'v', 'w', 'x', 'y'],
['z']]
find_path('zonez', box)
- Scott January 19, 2014