Amazon Interview Question
Country: India
This solution will not run in linear time. You forgot to account for the time to sort each word.
It's not O(n lg n). It is more like O (n* m lg m) where m is the max number of characters possible in the words. Now, if m is small, m lg m will be just like a small constant and thus it will be O(n)
@yossee: That's the correct analysis.
O(n) isn't going to be achievable because there's O(m*n) bits of data to look at. O(m*n) complexity is the lowest you can hope for, so O(n*mlogm) is really pretty close to optimal.
For each word, make a integer array 26 long. Scan through each word and for each letter x, lowercase the letter and increment the value at index[Ascii(x) - Ascii('a')] by 1. Now use the string representation of the array as the key to look up entries in a hash table. If an entry exists, print out this word and the value in the hash table. If not, load the hash table with the string version of the array as the key and the word as the value.
For each word, make a integer array 26 long. Scan through each word and for each letter x, lowercase the letter and increment the value at index[Ascii(x) - Ascii('a')] by 1. Now use the string representation of the array as the key to look up entries in a hash table. If an entry exists, print out this word and the value in the hash table. If not, load the hash table with the string version of the array as the key and the word as the value.
Scan through the list of words find the sum of each word by adding the ascii values and add it simultaneously to hashmap with key as sum of word nd value as word if collision occurs print the current word nd the stored one. Order is O(n) .assumption n(no of words) > m(length of any word).
This approach would not work, and I'll provide an example
The String "22" has sum of ascii value 100 ('2' has ascii value of 50). This would collide with the String "d", which has ascii value of 100 by itself. However, I agree with the idea of producing an order-irrelevant hash value for each string.
Instead of using sum as keys, you can design a data-structure that removes the ordering and use the data-structure as key.
e.g. hashMap<char, int>, you would increase the int each time the same char appears. Depending on the "resource vs time" argument, you can also use an array or int instead (ascii table has 127 char in total, so you would use array with 127 elements).
I completely agree with the above comment.
The idea of using some hash function to use as the key for values is great. Obviously, the sum of ascii values does not prove to be a good key value. I got some idea from the RK algorithm.
We can use double-hash or triple-hash if required to get a unique key value. Adding the ascii values can be one technique. If it matches, then we can apply another hash technique on top of that. The other hash technique has to be thought of and can be anything like:
"Anna" -> ascii(A) - ascii(n) + ascii(n) - Ascii(A).
This is just an example and maintain another hashmap for these entries.
If our string to be checked matches all these criterions, then we assume it is an anagram and print the value for that key and our word under consideration.
This provides a full proof method for avoiding wrong analysis of anagrams, though the storage is a little bit higher but good time complexity.
static void printAnagrams(String[] words) {
HashMap<Integer, String> hash = new HashMap<Integer, String>();
for(String s : words) {
int code = getCode(s);
if(hash.containsKey(code)) {
System.out.println(s + " and " +hash.get(code) + " ");
hash.remove(code);
} else {
hash.put(code, s);
}
}
}
static int getCode(String s) {
int code = 1;
for(char c : s.toCharArray()) {
code *= prime[c-'a']; // array of primes
}
return code;
}
import java.lang.String;
import java.util.*;
public class similiar
{
public static Hashtable store = new Hashtable();
public static void pairs (String arg)
{
double temp = convert(arg);
if(store.containsKey(temp))
System.out.println(store.get(temp)+" , "+arg);
else
store.put(temp,arg);
}
public static double convert(String args)
{
double output=0;
int lengthofargs = args.length();
int j=0;
for( j=0;j<lengthofargs;j++);
{
j-=1;
int temp=(int)args.charAt(j);
temp-=96;
output+=Math.pow(10,temp-12);
}
return output;
}
public static void main(String args[])
{
for(String arg:args)
{
pairs(arg);
}
}
}
O(n) code
import java.lang.String;
import java.util.*;
public class similiar
{
public static Hashtable store = new Hashtable();
public static void pairs (String arg)
{
double temp = convert(arg);
if(store.containsKey(temp))
System.out.println(store.get(temp)+" , "+arg);
else
{
store.put(temp,arg);
// System.out.println("temp : " +temp + " arg : " + arg);
}
}
public static double convert(String args)
{
double output=0;
int lengthofargs = args.length();
int j=0;
for( j=0;j<lengthofargs;j++)
{
int temp=(int)args.charAt(j);
temp-=96;
output+=Math.pow(10,temp-11);
// System.out.println(j);
// System.out.println("char :" +args.charAt(j)+" output : " + output);
}
return output;
}
public static void main(String args[])
{
for(String arg:args)
{
pairs(arg);
}
}
}
Take each word, sort it and put it in a hashmap with key => sorted word & value => original word. Thus the hashmap will look like
Now iterate through the hashmap and print all the values. O(n) solution
- rookie.coder March 30, 2012