## Amazon Interview Question

SDE1s**Country:**United States

**Interview Type:**In-Person

With more time than a standard Interview, I would expect a much better algorithm than this:

Pseudo code:

starting function:

create trie from valid strings

for each column i in char[][]

for each row j in char[][]

execute a DFS starting at char[i][j]

}

}

DFS (i, j):

if i or j are invalid indices in char[][]

return

add position i, j to the working array

if working array is a completed word in the trie

add working array to results

if working array is within the trie

set position i, j as having been explored

DFS(i-1, j)

DFS(i, j-1)

DFS(i+1, j)

DFS(i, j+1)

unset position i,j as having been explored

remove position(i, j) from the working array

Complexity for this solution really stinks. And it will operate at roughly O(n^2*m^2) where n and m are the dimensions of the char[][].

Code:

```
static class TrieNode{
boolean isWord;
HashMap<Character, TrieNode> nodes = new HashMap<Character, TrieNode>();
}
public static ArrayList<String> getWords(char[][] grid, List<String> words){
TrieNode trie = buildTrie(words);
ArrayList<String> results = new ArrayList<String>();
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[0].length; j++){
dfs(grid, i, j, trie, results);
}
}
return results;
}
private static void dfs(char[][] grid, int i, int j, TrieNode trie, ArrayList<String> results){
ArrayList<Character> working = new ArrayList<Character>();
boolean[][] charUsed = new boolean[grid.length][grid[0].length];
dfsRecur(grid, i, j, working, charUsed, trie, results);
}
private static void dfsRecur(char[][] grid, int i, int j, ArrayList<Character> working, boolean[][] charUsed, TrieNode trie, ArrayList<String> results){
if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || charUsed[i][j]){
return;
}
char c = grid[i][j];
TrieNode nextNode = trie.nodes.get(c);
if(nextNode != null){
working.add(c);
if(nextNode.isWord){
char[] wordArr = new char[working.size()];
for(int i = 0; i < wordArr.length; i++){
wordArr[i] = working.get(i);
}
results.add(new String(wordArr));
}
charUsed[i][j] = true;
dfsRecur(grid, i-1, j, working, charUsed, nextNode, results);
dfsRecur(grid, i, j-1, working, charUsed, nextNode, results);
dfsRecur(grid, i+1, j, working, charUsed, nextNode, results);
dfsRecur(grid, i, j+1, working, charUsed, nextNode, results);
charUsed[i][j] = false;
}
}
private static TrieNode buildTrie(List<String> words){
TrieNode root = new TrieNode();
TrieNode node = null;
for(String str : words){
node = root;
int index = 0;
char[] arr = word.getChars();
for(int i = 0; i < arr.length; i++){
char c = arr[i];
TrieNode nextNode = node.nodes.get(c);
if(nextNode == null){
nextNode = new TrieNode();
node.nodes.put(c, nextNode);
}
node = nextNode;
}
node.isWord = true;
}
return root;
}
```

```
var dic = ["car", "add", "rum", "rap", "carrots", "addition"];
var matrix = [['c','a','r'], ['o','d','u'],['s','d','m']];
function Node (value) {
var self = this;
self.value = value;
self.children = {};
self.isWord = false;
}
function Trie () {
var self = this;
self.children = {};
self.create = function (dic) {
var trie = self;
for (var i=0; i<dic.length; i++) {
var word = dic[i];
var t = trie;
for (var j=0; j<word.length; j++) {
var ch = word[j];
if (t.children[ch] === undefined) {
t.children[ch] = new Node(ch);
}
t = t.children[ch];
}
t.isWord = true;
}
}
}
(function searchAllPossibleWords(matrix, dic) {
// Create trie tree in o(PxK) where p is the number of dictionary entries and K is the max size of
// a dictionary entry. (Is this running time correct)?
var trie = new Trie();
trie.create(dic);
// This could be broken down into a utility function for recursion usage
var wordFound = "";
var t = null;
var ch = null;
// for each row. Running time is O(RxC) R is # of rows and C is number of columns.
for (var r=0; r<matrix.length; r++) {
wordFound = "";
t = trie;
for (var c=0; c<matrix[r].length; c++) {
ch = matrix[r][c];
if (t.children[ch] === undefined) {
break;
}
wordFound += ch;
t = t.children[ch];
}
if (t.isWord === true) {
console.log("found word: " + wordFound);
wordFound = "";
}
}
// for each column. Running time is O(CxR) C is # of columns and R is # of rows
for (var c=0; c<matrix[0].length; c++) {
wordFound = "";
t = trie;
for (var r=0; r<matrix.length; r++) {
ch = matrix[r][c];
if (t.children[ch] === undefined) {
break;
}
wordFound += ch;
t = t.children[ch];
}
if (t.isWord === true) {
console.log("found word: " + wordFound);
wordFound = "";
}
}
})(matrix, dic);
```

Are my running times correct? What you guys think...

Traverse the grid from left to right, top to bottom. For each cell, check if any words that start from this cell is in the dictionary. If current word is in the dictionary or the length of current word has exceeded the maximum length of words in dictionary, you can skip to next cell.

- yangxh92 December 05, 2014If the grid A has size N*M, dict has size K, the strings in dict has a maximum length of L, then the time complexity will be

O(NM(min(max(N, M), L) + log K))