Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

OK. I just got what you asked.
Sorry for writing bullshit (and for the double post).

Why not sorting the characters in the word by a determined order:

'BAC' -> 'ABC'
'CBA' -> 'ABC'
'ACB' -> 'ABC' etc...

and store only sorted words in the dictionary.
when you want to know if an anagram of that word is present, sort it and lookup the sorted word in the dictionary.

- Dave September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is the standard solution.
There is even a more efficient way - map all characters in the alphabet to the first 26 prime numbers and calculate the hash value of a word as the multiplication of those values. Hash is guaranteed to be unique for every different anagram set, and the same for all anagrams within a set. This reduces the complexity from O(nlgn) of sorting to O(n) in the calculation of the hash value.

- Omri.Bashari May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

So u were provided with input of words.. in which u need to tell whether the word(s) is/are anagram of ABC or not..? I am right.?

- nageshtikare September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no. he said don't generate all the anagram of input string. find out how many words are there in the dictionary which are anagram of string "ABC"

- NEO September 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe I'm missing something but I don't see a big problem.
If a hashmap is used to store the dictionary using hash function

f(x)

, then looking up a word

a

in the dictionary is around O(1) complexity:

1. compute the

f(a)

- O(1)
2. looking up

f(a)

in the hashmap - O(1)
3. handling any conflicts with other words that were hashed as

f(a)

- aprox. O(1) if the hash was implemented well

- Dave September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Maybe I'm missing something but I don't see a big problem.
If a hashmap is used to store the dictionary using hash function

f(x)

, then looking up a word

a

in the dictionary is around O(1) complexity:

1. compute the

f(a)

- O(1)
2. looking up

f(a)

in the hashmap - O(1)
3. handling any conflicts with other words that were hashed as

f(a)

- aprox. O(1) if the hash was implemented well

- Dave September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you can assume the dictionary is a trie of words. And your input string is "ABC". Search for characters A, B and C in the children of the root. Let's say you found B. Record this information that B has been found in another data structure. Now follow the branch with root as B. And look for A and C in it children. Let's say you found A. Record this information. Now try to find C in the children of A. If you find it, then you can print the anagram as "BAC". Then backtrack and look for other anagrams accordingly.

- Amy Lee September 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use trie data structure of sorted words. if you word is present in trie data structure then increase a count value of that node.
Node
{
int count_of_anagaram;
char[] a = new a[26];
}
Now let say you want to search a anagram of string s then sort it and search it into trie.

- Anonymous September 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

See following,

import java.util.ArrayList;
import java.util.Arrays;



public class AnagramsInDict {

	public static void main(String[] args){
		
		String s="abc";
		String[] anag={"bca", "cab", "xxx", "acb"};
		
		int i=findAnagrams(s, anag);
		System.out.println(i);
	}
	
	
	public static int findAnagrams(String s, String[] arr){
		ArrayList<String> anagramList=new ArrayList<>();
		
		char[] inString=s.toCharArray();
		Arrays.sort(inString);
		for(String ss: arr){
		
			
			boolean isAnagram=true;
			char[] elem=ss.toCharArray();
					Arrays.sort(elem);
			if(elem.length!=inString.length){
				isAnagram=false;
			}
			else
			{
				
			for(int o=0; o<elem.length; o++){
				
				if(elem[o]!=inString[o])
						{isAnagram=false;}
			}
			

			}
			if(isAnagram){
				
				anagramList.add(ss);
			}
			
		}
		return anagramList.size();
	}
	

}

- ATuring September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if i got ur question correctly. The problem is: we got a dictionary with some words inserted in the dictionary. Now given a String str we need to find if str or any of its anagram is part of the dictionary.

For the problem stated above, i think trie will be the best suited DS.
Suppose i got a dictionary(trie) and a string "same" and in my dictionary i have the anagram "emas". So my algorithm will start traversal from root and check if any of the chars from the string is a valid child of the root. If so we then move to next the child node and keep on checking for remaining characters till all the characters r completed else return false.

- anshulzunke September 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AnagramsInDict {

	private static String[] dict = new String[] { "BAC", "KPD", "LMK", "LMC",
			"XAZ", "IMT" };
	private static String[] sorteddDict = new String[dict.length];

	public static void main(String[] args) {
		createSortedDict();
		System.out.println(dictContains("ABC"));
		System.out.println(dictContains("MCL"));
		System.out.println(dictContains("MCLK"));

	}

	private static boolean dictContains(String string) {
		String temp = sortString(string);
		for (int i = 0; i < sorteddDict.length; i++) {
			if (sorteddDict[i].equals(temp)) {
				return true;
			}
		}
		return false;
	}

	private static void createSortedDict() {
		for (int i = 0; i < dict.length; i++) {
			String temp = dict[i];
			sorteddDict[i] = sortString(temp);
		}
		System.out.println(Arrays.toString(sorteddDict));
	}

	private static String sortString(String temp) {
		char[] chars = temp.toCharArray();
		Arrays.sort(chars);
		String sorted = new String(chars);
		return sorted;

	}
}

- AK October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

private static void checkStringAnagramIsInMap() {
String str = "ABC";
Map<Integer, String> dict = new HashMap<Integer, String>();
dict.put(stringToInt(str), str);

System.out.println(dict.containsKey(stringToInt(str)));

System.out.println(dict.containsKey(stringToInt("CAB")));
System.out.println(dict.containsKey(stringToInt("BAC")));
}

- Anonymous September 28, 2014 | 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