Google Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
This works, but building a trie on all dictionary words is not efficient solution, I think.
We have to do DFS from each position in the matrix right? and we have to initialize visited matrix to zero from every position DFS call.
it is not necessary to convert the dictionary to a tire as the problem states that it's efficient to check whether a word present
also the dictionary could contains huge number of words and tire is space consuming
the more critical part of this problem is to get all possible words. it can be done either by BFS or DFS
@ifenjoy9 : if dictionary is not a trie, how can we decide whether a character is to be added to make a word or not? Are we going in right direction in making a valid word?
This is exactly like the boggle game interview question. Has been asked by Amazon, Microsoft and the likes.
@Bharat, you don't need to build a trie for this solution, because the question already states that the lookup can be done effectively. Sure, a trie would make sense, but that is not the objective of the question. The question was to find out if you're able to realize that this is a DFS/BFS question and if you're able to code it. Not implementing a trie.
The logic is already given, so I wouldn't repeat it. I'll just add that you have to be careful to mark the visited locations as unvisited once you return from the recursion. That should solve it.
Yes, DFS should nicely solve it. One can add some heuristics to this logic to improve on the time. Say the longest English word is 20 chars. Once the DFS has reached 20char depth, you know you're not going to find anything deeper - so back track from the recursion.
This way, given a 100x100 matrix, the execution time can be cut down significantly.
we've to find all possible words and check if the dictionary contains a particular word
public void findWords(char[][] a)
{
words.clear();
int m = a.length;
int n = a[0].length;
boolean[][] b = new boolean[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
findWords(a, b, "", i, j);
}
}
System.out.println(words);
}
private void findWords(char[][] a, boolean[][] b, String word, int i , int j)
{
if(i < 0 || i >= a.length || j < 0 || j >= a[i].length || b[i][j]) return;
String word1 = word + Character.toString(a[i][j]);
if(dict.contains(word1)) words.add(word1);
boolean[][] b1 = new boolean[b.length][b[0].length];
for(int p = 0; p < b.length; p++)
for(int q = 0; q < b[p].length; q++)
b1[p][q] = b[p][q];
b1[i][j] = true;
findWords(a, b1, word1, i - 1, j);
findWords(a, b1, word1, i + 1, j);
findWords(a, b1, word1, i, j - 1);
findWords(a, b1, word1, i, j + 1);
}
private static List<String> words = new ArrayList<String>();
private static Set<String> dict = new HashSet<String>();
typedef set<string> Dict;
struct Node
{
Node(char v, unsigned short i);
char val;
unsigned short index;
Node *left;
Node *right;
Node *top;
Node *bottom;
};
class Grid
{
public:
Grid();
Grid(Node* const& node);
~Grid();
Node *start;
};
extern Dict dict;
bool isInDIct(const string& str);
void checkWord(Node* const& node, string str, set<unsigned short> path);
void findWord(const Grid& input);
bool isInDIct(const string& str)
{
if (dict.find(str) != dict.end())
return true;
else
return false;
}
void checkWord(Node* const& node, string str, set<unsigned short> path)
{
unsigned short index = node->index;
if (path.find(index) != path.end())
return;
path.insert(index);
str += node->val;
if ( isInDIct(str) )
cout << str << endl;
if (node->left != NULL)
checkWord(node->left, str, path);
if (node->right != NULL)
checkWord(node->right, str, path);
if (node->top != NULL)
checkWord(node->top, str, path);
if (node->bottom != NULL)
checkWord(node->bottom, str, path);
}
void findWord(const Grid& input)
{
if (input.start == NULL)
{
cout << "EMPTY grid." << endl;
return;
}
set<unsigned short> path;
checkWord(input.start, "", path);
}
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;
public class FindWordsInMatrix
{
private enum ansEnum {
startswith, exists, non
};
static ArrayList<String> hSet = loadDictionary();
public static void main(String[] args)
{
int rows = 8;
int columns = 8;
char[][] matrix = new char[rows][columns];
Random random = new Random();
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix[0].length; j++)
{
matrix[i][j] = (char) ('a' + random.nextInt(26));
System.out.print(String.format("%2s", matrix[i][j]));
}
System.out.println("");
}
HashSet<String> usedSet = new HashSet<>();
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix[0].length; j++)
{
GetNextAvalibleSymbol(matrix, i, j,
String.valueOf(matrix[i][j]), (HashSet<String>) usedSet.clone());
}
}
System.out.println(hSet.size());
}
private static void GetNextAvalibleSymbol(char[][] matrix, int i, int j,
String str, HashSet<String> usedSet)
{
usedSet.add(i + "." + j);
ansEnum ans = ansEnum.startswith;
if(str.length()>2)
{
ans = IsExists(str);
if (ans == ansEnum.exists)
System.out.println(str);
}
if (ans == ansEnum.startswith)
{
if (i > 1)// row >1 we can move up
{
if (!usedSet.contains((i - 1) + "." + j))
{
GetNextAvalibleSymbol(matrix, i - 1, j, str + matrix[i - 1][j], (HashSet<String>) usedSet.clone());
}
}
if (j > 1)// row >1 we can move left
{
if (!usedSet.contains((i) + "." + (j-1)))
GetNextAvalibleSymbol(matrix, i, j - 1, str + matrix[i][j - 1], (HashSet<String>) usedSet.clone());
}
if (i < matrix.length-1)// row >1 we can move up
{
if (!usedSet.contains((i + 1) + "." + j))
{
// System.out.println("heee");
GetNextAvalibleSymbol(matrix, i + 1, j, str + matrix[i + 1][j], (HashSet<String>) usedSet.clone());
}
}
if (j < matrix[0].length-1)// row >1 we can move left
{
if (!usedSet.contains((i) + "." + (j+1)))
GetNextAvalibleSymbol(matrix, i, j + 1, str + matrix[i][j + 1], (HashSet<String>) usedSet.clone());
}
}
}
private static ansEnum IsExists(String str)
{
int curIndex = hSet.size() / 2;
int delta = curIndex / 2;
int deltaShifts = 10;
boolean startswith = false;
while (deltaShifts > 0)
{
String temp = hSet.get(curIndex);
int compare = hSet.get(curIndex).compareTo(str);
// System.out.println(curIndex +"\t"+delta + "\t" + "\t" + compare +
// "\t" + temp );
if (compare == 0)
return ansEnum.exists;
if (!startswith && hSet.get(curIndex).startsWith(str))
startswith = true;
if (compare > 0)
curIndex = curIndex - delta;
else
curIndex = curIndex + delta;
if (delta > 1)
delta = delta / 2;
else
{
delta = 1;
deltaShifts--;
}
}
if (startswith)
return ansEnum.startswith;
else
return ansEnum.non;
}
private static ArrayList<String> loadDictionary()
{
ArrayList<String> hashSet = new ArrayList<String>();
try
{
FileReader fReader = new FileReader(
"C:\\WORKSPACE\\HowManyWords\\12dicts-5.0\\5desk.txt");
BufferedReader brBufferedReader = new BufferedReader(fReader);
for (String string = brBufferedReader.readLine(); string != null; string = brBufferedReader
.readLine())
{
hashSet.add(string.toLowerCase());
}
}
catch (FileNotFoundException e)
{
e.printStackTrace();
}
catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
return hashSet;
}
}
Using backtracking here.
public void findAllWords(String[][] a)
{
int m = a.length;
int n = a[0].length;
int[][] assignmentMatrix = new int[m][n];
LinkedList<String> list = new LinkedList<String>();
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
emptyAssignmentMatrix(assignmentMatrix);
list.addAll(findWords("", assignmentMatrix, a, i, j));
}
}
System.out.println(list);
}
public void emptyAssignmentMatrix(int[][] assignmentMatrix){
for(int i=0;i<assignmentMatrix.length;i++)
for(int j=0;j<assignmentMatrix[i].length;j++)
assignmentMatrix[i][j]=0;
}
public LinkedList<String> findWords(String word, int[][] assignmentMatrix, String[][] a, int x, int y){
LinkedList<String> list = new LinkedList<String>();
LinkedList<String> result = new LinkedList<String>();
if(x < 0 || x >= a.length || y < 0 || y >= a[x].length || assignmentMatrix[x][y]==1) return list;
String word1 = word + a[x][y];
if(isWord(word1)) list.add(word1);
assignmentMatrix[x][y] = 1;
result.addAll(findWords(word1, assignmentMatrix, a, x, y-1));
result.addAll(findWords(word1, assignmentMatrix, a, x+1, y));
result.addAll(findWords(word1, assignmentMatrix, a, x, y+1));
result.addAll(findWords(word1, assignmentMatrix, a, x-1, y));
if(result.size()>0){
list.addAll(result);
}else{
assignmentMatrix[x][y] = 0;
}
return list;
}
Sounds like a game of Boggle.
- CameronWills November 09, 20121. Load the dictionary words into a Trie data structure.
2. Model the MxN matrix as a graph, each vertex representing a position in the matrix (a letter) and edges for the adjacent matrix positions. e.g. edges between (1,1) , (1,2), (2,2).
3. Starting from each vertex, traverse the graph with a depth first search, and check letters off in the Trie while traversing. Keeping track of 'visited' vertices to ensure the same letter isn't used multiple times. And prune paths where there is no matching letter / path in the Trie.
4. When a complete word in the Trie is found, output the word.