Amazon Amazon Interview Question


Country: India
Interview Type: In-Person




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

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rohit January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this method works

- ini January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- inosvaruag January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- A January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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'];
		}
	}
}

- MarcoF January 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can "Aho–Corasick_string_matching_algorithm" be used here ?

- singhsourabh90 January 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()]);
}

}

- Valbuena February 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I understand your logic. Thank you for sharing. What is the time and space complicity of this algorithm?

- mail.nuwan June 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use trie for raw words.
Construct a graph with each element in the 2d array as a node and a bidirectional edge between adjacent elements.

for each node perform a dfs and check if the concatenated nodes so far are in the dictionary

complexity O((n+m)*max(n,m))

- Anonymous March 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- pranav bhole February 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

looks like code is given from Dynamic programming.

- alien February 06, 2013 | Flag Reply


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