## Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.
If 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))

Comment hidden because of low score. Click to expand.
0
of 0 votes

Great, your idea can be improved further by using hashing so you can eliminate log(K) term from your time complexity formula. Hash of the word can be computed incrementally.

Comment hidden because of low score. Click to expand.
0
of 0 vote

@wyu277 It will be great if you can provide a small example.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

should we not put the code in dfsRecur under the check !charUsed[i][j] before using the character at that position

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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...

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More