Amazon Amazon Interview Question
Country: India
Interview Type: In-Person
Here as an approach from my side
1.) Trie DS to store the list of words.
2.) Perform a DFS with a visited array extra space to identify the connected components in this case words to map against the Trie store
import java.util.*;
public class TreeNode {
public char value;
public TreeNode[] nextChars = null;
public Boolean wordEnd = false;
public TreeNode(char value, Boolean wordEnd) {
this.value = value;
this.nextChars = new TreeNode[26];
this.wordEnd = wordEnd;
}
}
public class Program {
/**
* @param args
*/
public static void main(String[] args)
{
//Get input
char[][] block = new char[7][3];
//Assuming all words are lower case.
String[] dictionary = new String[100];
TreeNode rootNode = BuildTree(dictionary);
}
private static LinkedList<String> dfsUsingStringCues(TreeNode rootNode, String word)
{
LinkedList<String> words = new LinkedList<String>();
Stack<TreeNode> stack = new Stack<TreeNode>();
int index = 0;
stack.push(rootNode);
while (!stack.empty() && index < word.length())
{
char currentWordChar = word.charAt(index++);
TreeNode currentNode = stack.pop();
if (currentNode.wordEnd)
words.add(word.substring(0,index));
else
{
int charPosition = currentWordChar - 'a';
if (currentNode.nextChars[charPosition] != null)
{
stack.push(currentNode.nextChars[charPosition]);
}
}
}
return words;
}
private static TreeNode BuildTree(String[] dictionary)
{
TreeNode rootNode = new TreeNode(' ', false);
for(int i = 0; i < dictionary.length; i++)
{
TreeNode currentNode = rootNode;
int index = 0;
int length = dictionary[i].length();
while (index < length)
{
char currentChar = dictionary[i].charAt(index++);
int charPosition = currentChar - 'a';
if (currentNode.nextChars[charPosition] == null)
{
currentNode.nextChars[charPosition] = new TreeNode(currentChar, false);
}
if (index == length - 1)
currentNode.nextChars[charPosition].wordEnd = true;
currentNode = currentNode.nextChars[charPosition];
}
}
return rootNode;
}
}
Below is my algorithm:
findWord(char[][] matrix, int row, int col)
For(int i = 0 ; i < char[][0].length ; i++)
if(Dictionary.contains(matrix[Math.abs(i-row)][col] -- I mean the word here in i to row)){
list.add(add this word)
}
//This will look for other words top-down or bottom up in the same col
findWord(matrix, row + 1, col)
for(int j = 0 ; j < matrix[i].length){
if(Dictionary.contains(matrix[row][Math.abs(j-col)] -- I mean the word here in this
range)){
list.add(add this word)
}
//This will look for other words left-right or right-left in the same row
findWord(matrix, row, col+1)
}
return list;
}
Complexity of this algo isnt really nice....but still I believe this should work.
My solution:
package it.mafa.amazon.question5;
import java.util.LinkedList;
public class Answer {
public String[] find(char[][] matrix,String[] rawList){
Node root = new Node(null);
for (String eachString : rawList) {
char[] array = eachString.toCharArray();
Node prev = root;
for (char eachChar : array)
prev = prev.add(eachChar);
prev.word = eachString;
}
return findWords(matrix,root);
}
private String[] findWords(char[][] matrix, Node root) {
LinkedList<String> result = new LinkedList<>();
for(int i=0;i<matrix.length;i++)
for(int j=0;j<matrix[0].length;j++){
findWord(matrix,i,j,root,result);
}
return result.toArray(new String[]{});
}
private void findWord(char[][] matrix,int i,int j,Node root,LinkedList<String> result){
if(i<0 || i>=matrix.length) return;
if(j<0 || j>=matrix[0].length) return;
Node next = root.get(matrix[i][j]);
if(next==null) return;
if(next.word!=null) result.add(next.word);
findWord(matrix, i-1, j-1, next, result);
findWord(matrix, i-1, j, next, result);
findWord(matrix, i-1, j+1, next, result);
findWord(matrix, i, j-1, next, result);
findWord(matrix, i, j+1, next, result);
findWord(matrix, i+1, j-1, next, result);
findWord(matrix, i+1, j, next, result);
findWord(matrix, i+1, j+1, next, result);
}
private static class Node {
final private Node parent;
private String word;
final private Node[] children = new Node['z'-'a'];
public Node(Node parent) {
this.parent = parent;
}
public Node add(char aChar){
if(children[aChar-'a']==null)
children[aChar-'a'] = new Node(this);
return children[aChar-'a'];
}
public Node get(char aChar){
return children[aChar-'a'];
}
}
}
public class test {
public static void main (String[] args)
{
String [] rawList = {"god", "goat", "godbody", "amour", "net"};
Character[][] matrix = {{'g','o','d', 'b', 'o', 'd','y'},{'t','a','m','o' ,'p','r','n'}, {'u','i','r','u','s', 'm', 'p'}};
String[] vuelta = find (matrix, rawList);
System.out.println(vuelta.toString());
}
public static String[] find(Character[][] matrix,String[] rawList){
List<Character> lsCharTotal = new ArrayList<Character>();
List<String> wordtotal = new ArrayList<String>();
for (Character[] line: matrix){
lsCharTotal.addAll(Arrays.asList(line));
}
for (String word: rawList){
List lsCharWord = new ArrayList<Character>();
for (Character charAux : word.toCharArray())
lsCharWord.add(charAux);
if (lsCharTotal.containsAll(lsCharWord))
wordtotal.add(word);
}
return wordtotal.toArray(new String[wordtotal.size()]);
}
}
In order to get rid of O(n^2), I came up with the following solution.
1. Sort the elements in 2D array and store it in 26 buckets with counts.
2. Build the tree of valid words having 26 possible children (A-Z) under each node.
While building this tree, do not add the child which is not present in the buckets.
Also the add only those words in the tree having same letter count present in the buckets. For example 'o' comes 3 times, thus do not add the word in the tree which contains more than 4 'o'.
3. this will create the tree of all significant possible letters which are also included in the valid word list.
4. Traverse and print the tree by following algorithm
A. Visit node and print it till you find the leaf.
B . If you find the leaf print it and go to parent and delete that leaf.
C. Go root node and follow A.
If we store the raw words in trie data structure and search the the valid world in 2D array according to moving from root to leave of the trie then it may be good solution......not sure completely
- csgeeg January 28, 2013