0

So I had interview today and interviewer asked me how I would go about, from a list of words, delete the anagrams. And by that he meant if the words 'eat' and 'ate' are on the list one of them would be deleted. As I was thinking out loud I came to adding up the ASCII value for each letter of the word and comparing, but that doesn't work. Then they reminded that you can assign whatever value I want, and after a little thought it dawned on me. Assign each letter a unique prime number and multiply all the 'letters' to get a unique value for that combination of letters. From this you would be able to compare the words to test whether or not they are anagrams.

My question is: Did I happen to think of a unique solution or is this something that is common knowledge? I am all worked up and trying to gauge how the interview went, though either way I think I did well because I had no prior knowledge of that.

3
Contributors
4
Replies
5
Views
6 Years
Discussion Span
Last Post by iamthwee
0

I think you might be onto something there.

http://www.techreplies.com/programming-28/fast-way-judge-anagram-468039/

Seems like the algorithm will produce integer overflow when letter combinations become large though. So incorporating a bignum library would be necessary to avoid errors due to rounding. This is expensive.

The easiest way to find an anagram is to simply sort the string and just do a comparison.

star, rats

sorted = arst
sorted = arst

This works beautifully for anagrams with many many letters.

Whilst, interview questions are designed to get you think outside the box, they are also testing to see if you can come up with the quickest (log(n)) solution. They don't really want to be employing a person who thinks up wild algo's (whilst in theory may work), maybe impractical to implement.

I wouldn't worry too much about it. It's done now. You were probably judged on all other aspects as well.

Edited by iamthwee: n/a

0

but i am so smart for thinking of what a famous mathematician did in less than 5 minutes... :)

0

but i am so smart for thinking of what a famous mathematician did in less than 5 minutes... :)

It's unlikely you interviewer will see it this way.

Like I said before, simplicity and practicability over everything else.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.