Google Interview Question Software Engineer / Developers
Looks pretty similar to FloodFill() in image processing. Recursion is needed to do job.
btw, can a word be represented in diagonally connected? Be clear, is 4-neighbor or 8-neighbor or even not on a straight line?
Yup the solution can be solved by using recursion. i dont know much optimised code other than this. for evry position (i,j) there are total 8 directions possible in which we can move. Scanning in each directions keeping track of in which base direction we are moving and checking boundary conditions . and updating the same
Not a completely correct program..
package google;
import java.util.ArrayList;
import java.util.HashMap;
public class CrossWord {
//private char [][] puzzle;
private ArrayList<String> puzzle = new ArrayList<String>();
private HashMap<String,Integer> myMap = new HashMap<String,Integer>();
public CrossWord(){
puzzle.add("aerops");
puzzle.add("bharls");
puzzle.add("wrislo");
puzzle.add("asnktq");
}
private void createHashMap(){
int i = 0;
int row = 0;
int col = 0;
while(i < puzzle.size()){
String key = getWord(i,-1);
myMap.put(key,0);
i++;
}
while (col < (puzzle.get(row).length() )){
String key = getWord(-1, col);
myMap.put(key,0);
col++;
}
}
private String getWord(int row ,int col){
char[][] puzzleArr = null;
String tempo = null;
String temp = null;
if(row >= 0 && row < puzzle.size()){
temp = puzzle.get(row);
row++;
}
else{
if(col >= 0){
for(int i = 0; i < puzzle.size() ; i++){
char[] temp1= puzzle.get(i).toCharArray();
Character c = temp1[col];
tempo += (c.toString());
}
String correctWord = tempo.substring(4);
return correctWord;
}
}
return temp;
}
public void display(){
System.out.println(myMap.keySet().toString());
}
public void isPresent(String word){
if(myMap.keySet().contains(word)){
System.out.println("Found!");
}
else{
System.out.println("Not Found!");
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CrossWord obj = new CrossWord();
obj.createHashMap();
obj.isPresent("slow");
}
}
My solution (intentionally) looks all 4 ways to search for the word, not just left->right and up-> down
public void FindAWordInPuzzleStart()
{
char[,] puzzle = { { 'a', 'e', 'r', 'o', 'p', 's' },
{ 'b', 'h', 'a', 'r', 'l', 's' },
{ 'w', 'r', 'i', 's', 'l', 'o' },
{ 'a', 's', 'n', 'k', 't', 'q' } };
string[] searchWords = new string[] { "rain", "bha", "ropa", "rainr", "rops", "abz", "abw", "123456", "1234567" };
Console.WriteLine("Puzzle:");
int lengthDim2 = puzzle.GetLength(1);
for (int i = 0; i < puzzle.Length; i++)
{
Console.Write(puzzle[i/lengthDim2, i%lengthDim2]);
if (i%lengthDim2 == lengthDim2-1)
Console.WriteLine();
}
Console.WriteLine();
foreach (string searchWord in searchWords)
{
Console.WriteLine("Searching for \"" + searchWord + "\": " + FindAWordInPuzzle(searchWord.ToCharArray(), 0, puzzle, -1, -1).ToString());
}
}
private bool FindAWordInPuzzle(char[] word, int startIndex, char[,] puzzle, int currentSearchLoc, int searchDirection)
{
if (word == null || word.Length < 1 || puzzle.Length < 1)
throw new ArgumentException();
int lengthDim1 = puzzle.GetLength(0),
lengthDim2 = puzzle.GetLength(1),
x,
y,
nextX,
nextY;
//word too big to fit into the puzzle
if (word.Length > lengthDim1 && word.Length > lengthDim2)
return false;
if (startIndex < 1)
{
//startIndex = 0;
for (int i = 0; i < puzzle.Length; i++)
{
x = i / lengthDim2;
y = i % lengthDim2; //always positive since i is positive
if (word[0] == puzzle[x, y])
{
//startIndex++;
if (word.Length == 1)
return true;
if (word.Length <= lengthDim2)
{
nextY = (y - 1) % lengthDim2;
while (nextY < 0)
nextY += lengthDim2;
if (FindAWordInPuzzle(word, 1, puzzle, x * lengthDim2 + nextY, -1))
return true;
nextY = (y + 1) % lengthDim2;
if (FindAWordInPuzzle(word, 1, puzzle, x * lengthDim2 + nextY, +1))
return true;
}
if (word.Length <= lengthDim1)
{
nextX = (x - 1) % lengthDim1;
while (nextX < 0)
nextX += lengthDim1;
if (FindAWordInPuzzle(word, 1, puzzle, nextX * lengthDim2 + y, -lengthDim2))
return true;
nextX = (x + 1) % lengthDim1;
if (FindAWordInPuzzle(word, 1, puzzle, nextX * lengthDim2 + y, +lengthDim2))
return true;
}
}
}
return false;
}
else
{
currentSearchLoc = currentSearchLoc % puzzle.Length;
while (currentSearchLoc < 0) //make it positive
currentSearchLoc += puzzle.Length;
x = currentSearchLoc / lengthDim2;
y = currentSearchLoc % lengthDim2; //always positive since currentSearchLoc is guaranteed positive above
if (word[startIndex] == puzzle[x, y])
{
startIndex++;
//if the last character has just been compared, then we found it, return true.
if (startIndex == word.Length)
return true;
if (searchDirection == -1 || searchDirection == +1)
{
nextY = (y + searchDirection) % lengthDim2;
while (nextY < 0)
nextY += lengthDim2;
return FindAWordInPuzzle(word, startIndex, puzzle, x * lengthDim2 + nextY, searchDirection);
}
else
{
nextX = (currentSearchLoc + searchDirection) % puzzle.Length;
while (nextX < 0)
nextX += puzzle.Length;
return FindAWordInPuzzle(word, startIndex, puzzle, nextX, searchDirection);
}
}
else return false;
}
}
This problem can be solved in O(M+N). Obviously we have to use recursion.
Call a function for row and column recursively . The function can be terminated when length of word will be traverse completely.
If the first character of word will match with puzzle matrix then we go call recursively either in direction of row or column. and it will be continue till the end(word search complete)
NOTE : I'm considering only 4 direction ( L->R, R->L,T->B,B->T). This solution can be extended for diagonal checking also.
Comments are most welcome.
After looking at the problem I thought its not that difficult but I had like 5-6 bugs in my implementation and it took around 2 hours to get this code.
Idea is for each element in matrix find if it matches the first word, if it matches then we have to look in 4 directions. If there is match in that direction proceed till we are end of the string. If match return true if not return false. We have or || all the directions because the string can be in any of 4 directions. Also Math.abs takes care of wrap around (this was my big bug)
package com.code.prolificcoder;
public class StringFinder {
enum Direction{up,down,left,right};
public static void main(String args[]){
char[][] ar=new char[][]{{'m','s','s','h'},
{'a','t','c','i'},
{'p','d','a','n'},
{'s','a','t','h'},
};
String str="tcia";
StringFinder sf=new StringFinder();
System.out.print(sf.stringFinder(ar,str));
}
private boolean stringFinder(char[][] ar, String str) {
int size=ar.length;
if(str.length()>size+1) return false;
int k=0;
char[] charArray=str.toCharArray();
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(ar[i][j]==charArray[k])
return isMatch(ar,charArray,i,Math.abs((j+1)%size),k+1,Direction.right)||
isMatch(ar,charArray,Math.abs((i+1)%size),j,k+1,Direction.down)||
isMatch(ar,charArray,Math.abs((i-1)%size),j,k+1,Direction.up)||
isMatch(ar,charArray,i,Math.abs((j-1)%size),k+1,Direction.left);
return false;
}
private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k, Direction dir) {
int size=ar.length;
if(k==charArray.length-1)
{
if(ar[i][j]==charArray[k]) return true;
else return false;
}
if(ar[i][j]==charArray[k]){
if(dir==Direction.down)
i=Math.abs((i+1)%size);
else if(dir==Direction.right)
j=Math.abs((j+1)%size);
else if(dir==Direction.left)
j=Math.abs((j-1)%size);
else //dir==Direction.up
i=Math.abs((i-1)%size);
return isMatch(ar,charArray,i,j,k+1,dir);
}
return false;
}
}
This is a simple question. To write bug free code is not that simple.
The secret is to use abstraction; don't write messy code in one big function. In real interviews the code typically just has no more than 20 lines.
For this problem I will first define the following data structures:
enum Direction {
UP, DOWN, LEFT, RIGHT;
}
class Point {
// returns false if unable to go to that direction
// otherwise move the current point to new position
public boolean go(Maze maze, Direction dir);
}
class Maze implements Iterable<Point> {
public Iterator<Point> iterator();
public char get(Point point);
}
And here is the code, just a few lines:
public static boolean exists(Maze maze, String word) {
if (word.length() == 0) return true;
char firstChar = word.charAt(0);
for (Point point : maze) {
char ch = maze.get(point);
if (ch == firstChar && exists(maze, point, word, 1))
return true;
}
return false;
}
private static boolean exists(Maze maze, Point point, String word, int index) {
if (index == word.length() - 1) return true;
char ch = word.charAt(index);
for (Direction dir : Direction.values()) {
if (point.go(maze, dir)
&& maze.get(point) == ch)
&& exists(maze, point, word, index + 1))
return true;
}
return false;
}
By providing a few lines of code, the chances of getting bugs are low.
Then, next step is to implement each functions if the interviewer asks.
boolean search(char[][] matrix, int m, int n, char[] str)
{
if (str == null) return true;
for (int i = 0; i < m; i ++)
{
for( int j = 0; j < n; j ++)
{
boolean hit = false;
if (matrix[i][j] == str[0])
{
if (subsearch(matrix, m, n, str, strlen(str), 1, j, i, 0) return true;
if (subsearch(matrix, m, n, str, strlen(str), 1, j, i, 1) return true;
if (subsearch(matrix, m, n, str, strlen(str), 1, j, i, 2) return true;
if (subsearch(matrix, m, n, str, strlen(str), 1, j, i, 3) return true;
}
}
}
return false;
}
boolean subsearch(char[][] matrix, int m, int n, char[] str, int len, int loc, int curx, int cury, int direction)
{
if (loc == len) return true;
if (direction == 0) // go right
{
curx ++;
if (curx == m)
{
curx = 0;
cury ++;
if (cury >= n) return false;
}
}
else if (direction == 1) //go down
{
cury ++;
if (cury == n)
{
cury = 0;
curx ++;
if (curx >= m) return false;
}
}
else if (direction == 2) //go left
{
curx --;
if (curx == -1)
{
curx = m - 1;
cury --;
if (cury < 0) return false;
}
}
else //go up
{
cury --;
if (cury == -1)
{
cury = n - 1;
curx --;
if (curx < 0) return false;
}
}
if (matrix[curx][cury] == str[loc])
{
return subsearch(matrix, m, n, str, len, loc + 1, curx, cury, direction)
}
return false;
}
import java.util.ArrayList;
/**
* Created by poorvank on 15/08/16.
*/
public class StringPuzzle {
private static int row, col;
//Traversing in all 4 directions
private static int x[] = {0, 1, -1, 0};
private static int y[] = {1, 0, 0, -1};
public static boolean find(String toFind, Character[][] puzzle) {
row = puzzle.length;
col = puzzle[0].length;
boolean[][] visited = new boolean[row][col];
for (int j = 0; j < col; j++) {
for (int i = 0; i < row; i++) {
if ((puzzle[i][j] == toFind.charAt(0)) && !visited[i][j]) {
if (findUtil(toFind, puzzle, i, j, visited, new StringBuilder(), 0,new ArrayList<>())) {
return true;
}
visited[i][j] = false;
}
}
}
return false;
}
private static boolean findUtil(String toFind, Character[][] puzzle, int i, int j, boolean[][] visited, StringBuilder sb, int index, ArrayList<String> list) {
sb.append(puzzle[i][j]);
//List used to print path when a string is found
list.add("(" + i+ "," + j +")");
if (sb.toString().equals(toFind)) {
System.out.println("Path is = " + list.toString());
return true;
}
if(index==toFind.length()) {
return false;
}
visited[i][j] = true;
int nextIndex = index + 1;
int nextR, nextC;
for (int k = 0; k < 4; k++) {
nextR = i + x[k];
nextC = j + y[k];
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
//Checking Wrap Around cases
//Corner Cases
if ((i == 0 && j == 0) || (i == row - 1 && j == col - 1)) {
nextR = row - 1;
nextC = 0;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
nextR = 0;
nextC = col - 1;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
} else if ((i == 0 && j == col - 1) || (i == row - 1 && j == 0)) {
nextR = row - 1;
nextC = col - 1;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
nextR = 0;
nextC = 0;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
} //Side cases
else if (i == 0) {
nextR = row - 1;
nextC = j;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
} else if (i == row - 1) {
nextR = 0;
nextC = j;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
} else if (j == 0) {
nextR = i;
nextC = col - 1;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
} else if (j == col - 1) {
nextR = i;
nextC = 0;
if (isValid(nextR, nextC, toFind, nextIndex, visited, puzzle)) {
return findUtil(toFind, puzzle, nextR, nextC, visited, sb, nextIndex,new ArrayList<>(list));
}
}
}
//mark last visited node(while backtracking) as false again so that it can be used again
visited[i][j] = false;
sb.deleteCharAt(sb.length()-1);
return false;
}
private static boolean isValid(int i, int j, String toFind, int index, boolean[][] visited, Character[][] puzzle) {
return (i >= 0 && j >= 0 && i < row && j < col && !visited[i][j] && puzzle[i][j] == toFind.charAt(index));
}
public static void main(String[] args) {
Character[][] puzzle = new Character[][]{{'a', 'e', 'r', 'o', 'p', 's'},
{'b', 'h', 'a', 'l', 'l', 's'},
{'w', 'r', 'i', 's', 'l', 'o'},
{'a', 's', 'n', 'k', 't', 'q'}};
String toFind = "slow";
System.out.println(StringPuzzle.find(toFind,puzzle));
}
}
We can maintain a hashmap of char to position.
total of 26 keys.
eg:
r->(0,2),(1,3).
and for each position of the starting letter, we can do 8 searches in 8 directions.
comments/suggestions welcome.
Thanks,
Rohith Menon.
The best solution is O(n + m) using a generalized suffix tree (GST) of all strings (along each row and along each column). Here n = length of all strings in puzzle (both along each row and along each column) and m = length of word which we need to find. For word w, scan the GST tree. For circular string, if word w is present till ith character then follow the 'pth row'/'qth col' corresponding to that leaf node in GST tree and see whether remaining characters in word are present in original char matrix's 'pth row'/'qth col'.
- Gopal Krishna August 13, 2009It may appear complicated, but once you understand how suffix trees (http://en.wikipedia.org/wiki/Suffix_tree) and generalized suffix trees (http://en.wikipedia.org/wiki/Generalised_suffix_tree) are, it will seem pretty trivial.