## Flipkart Interview Question for Software Engineer / Developers

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

My soln assumes that two words are anagrams if they are separated from each other by given delimiters like space etc and they contain same letters.

e.g. I saw a cat at the tac.

Here I can say that <cat, tac> is a anagram pair.

Algorithm:
Tokenize the words
As you are tokenizing, put the words in the hashtable as <word sorted by characters, actual word> e.g.if you find cat put <key, value> as <act, cat>
If you already find that word in hash table while putting in, you have found the anagram.
Time Complexity - O(len of str) assuming words are of constant size (lets say max size = 25).

Space complexity O(n) for the hash table.

Does anyone have better answer for this?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(len of str)?
Sorting the words would also take time.
At best its O(nlgn)

Comment hidden because of low score. Click to expand.
0

Sorting of word would itself take O(nlogn) where n is the length of the string.
Instead we can take 1st 26 prime number and allocate it to a-z. Now for every word we compute the product of the characters, this will be unique as we have chosen prime numbers.
Now for all the words Map it to HashMap<Integer,Word> if the key is there we have found one pair, else we insert the element into the map.

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

Good job coder, I liked your solution, way simple

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

anon and coder solutions are superb.

Trie can be used in this case.

Comment hidden because of low score. Click to expand.
0

Before inserting a word in a trie ,sort the word by its characters.
Do the same to determine , a given word has its anagram in the trie

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

If you sotr before inserting, how do you retrieve them back.

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

I think for anagrams best solution is to use Prime numbers assign A-2, B-3, C-5 etc., and put them in hash then CAB is 5*3*2 = 30, use this as the key and value can be list of Strings.

Do this for all words and finally iterate over the hash to print the anagrams.
This deals away the sorting burden.

Comment hidden because of low score. Click to expand.
0

thanks manoj this 1 seems a better solution

Comment hidden because of low score. Click to expand.
0

The solution works. But the downside is that if we have very large sentence or text, the cost of multiplying i.e. tokenising the entire text would be very high.

For log words, i.e. of 10 characters, there is a potential chance of arithmetic overflow and a high cost of multiplication.

I'd suggest keep it simple by sum of ascii values and the no. of characters in a word. There would be collisions but would be very minimal.

tac would have the same weightage as tbb, act etc.

A trie would suffice. No hashtable required.

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

we can also put the indexes of the words in the hash to reduce space usage...

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

we can also put the indexes of the words in the hash to reduce space usage...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Staying with the assumption from coder, you can use a trie (prefix tree) instead of a hash. When determining if a word is an anagram, you would check to see if the word's reverse is in the trie. The advantages of using a trie:

1) No need for hashing algorithm
2) No collisions
3) Less storage (not entirely sure on this one)

Comment hidden because of low score. Click to expand.
0

how is this going to work?i don't think it works. "reverse of word?" what are you checking here?

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.

### 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.