Member Avatar for riotburn

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
  • 731 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by iamthwee
Member Avatar for iamthwee

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 because: n/a
Member Avatar for Momerath

It's not new, sorry. Euler used it in his famous proof.

Member Avatar for riotburn

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

Member Avatar for iamthwee

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.