Amazon Interview Question for Software Engineer / Developers






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

The best algorithm I found for this problem is:

1. Parse each word in the dictionary
2. define a hashtable and search on any hashtable is o(1)
2. Sort each word [best sorting algorithms complexity is nlog(n) ] and and save this sorted word as key in the hash table and store the actual word as value
3. if the key exists already in hashtable, then retrieve the value and append the new word to the existing words string
Note: you just need to parse the whole dictionary only once which is O(n).
so the whole creation of the hashtable is
n*mLogm (m is the average number of letters in a word and n is the total number of words in the dictionary)

and when you want to find anagrams for a given word,
--> sort the word - mlogm (m is the letters in the word)
--> find the sorted one in hashtable - O(1)

thanks
RJ

- Jammanapalli July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I had given same approach, but interviewer said if dictionary is huge and cannot fit in memory, then what approach can be applied.

I had gone with creating a trie of dictionary and then searched the word in it.

- xenon116 February 25, 2019 | Flag
Comment hidden because of low score. Click to expand.
2
of 0 vote

Assign a signature to each word. for exaxmple.
stop ---> opst
pots---->opst

do the sorting on signature and then finding the anagrams is a cake wake

- Amit June 01, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I assume your signature is the letters of the word arranged in alphabetical order. If this is the case, the word "tops" would also have a signature of "opst". This isn't game breaking as you can still compare each word matched by signature to verify that they are anagrams. However, this shows that you cannot rely on the signature alone for anagram determination.

- mik3y February 08, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i steal this algorithm from someone else because it's very pretty.

1)create a hash table with a key of each letter and assign a unique PRIME number to it as value. So you have 26 letters and 26 prime numbers.
2)for each letter in a word, multiple the letter values you get from the hash table.
3)compare the values!

- joe July 09, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is not helpful. a word could be very long. e.g "palindromic", or some chemical name. and the 26th prime is 101.
so the hash value of a word could be too large, that no primitive type can hold it.

- bbs59 July 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

(1)setup the dictionary with trie datastructure
(2)for every word(O(1) get time) search the reversed string (O(1) find time) in the trie
(3)if find print it
(4)if u dont want duplictaes then after finding the anagram, make a boolean flag set for both strings

- mail2vcp@gmail.com October 01, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

so totally its take O(n) for n words

- mail2vcp@gmail.com October 01, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about sorting the two words in lexicographic order and comparing them char-by-char?

- Anonymous November 08, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nlogn comp., which is unnecessary..

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

Ok... this is a repeated question in our careercup site under amazon interview questions.

The best solution I have come across so far is to associate prime numbers for each character (a-z). for each word, multiply their corresponding numbers and compare it with other words for anagram check.

- Anonymous August 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That is a ridiculous solution.

- LOLer August 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh, and I missed this: LOL.

- LOLer August 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//C#
static bool checkIf2StringsAreAnagrams(string _str1, string _str2)
        {
            bool isAnagrams = false;

            Dictionary<char, int> charset = new Dictionary<char, int>();
            for (int i = 0; i < _str1.Length; i++)
            {
                char key = _str1[i];
                if (!charset.ContainsKey(key))
                {
                    charset.Add(key, 1);
                }
                else
                {
                    charset[key] += 1;
                }
            }

            Dictionary<char, int> charset2 = new Dictionary<char, int>();
            for (int i = 0; i < _str2.Length; i++)
            {
                char key = _str2[i];
                if (!charset2.ContainsKey(key))
                {
                    charset2.Add(key, 1);
                }
                else
                {
                    charset2[key] += 1;
                }
            }

            for (int i = 0; i < charset.Count; i++)
            {
                char key = charset.Keys.ElementAt(i);
                if (charset2.ContainsKey(key))
                {
                    if (charset[key] == charset2[key])
                    {
                        isAnagrams = true;
                    }
                    else
                    {
                        isAnagrams = false; break;
                    }
                }
                else
                {
                    isAnagrams = false; break;
                }
            }
            return (isAnagrams);
        }

- anup.h.nair December 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

add value

- Anonymous February 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

апельсин

- Anonymous April 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!/bin/python

def anagram_checker(str1,str2):
# Use empty dictonary for each string

    dict1={ }
    dict2={ }

    for i in str1:
        dict1[i]=i
    for j in str2:
        dict2[j]=j
# beauty of dictonary - the elements are sorted by itself
    
    if dict1 == dict2:
        print "The strings are anagrams !!"

    else :
        print "Strings are not anagrams !!"

    
anagram_checker('silent','listen')

- python_guy May 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

fdsdsds

- Anonymous December 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Merhaba,

Great post. Well though out. This piece reminds me when I was starting out Amazon Interview Question for Software Engineer / Developers after graduating from college.

This is Erin from Amazon Web Services. I took a look at the support case you provided, I see that one of our agents was able to assist and resolve the case.

Please let us know if there is anything else we can help with!

Awesome! Thanks for putting this all in one place. Very useful!

Kind Regards,
Radhey

- Radhey June 01, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

add ascii values of each character in the strings and compare
better still if u do (strlen)a[0] + (strlen-1)a[1].....a[strlen];

- Anonymous May 30, 2008 | 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