5 ms·
There's a much easier way to solve this problem than what you've done. And this is sorta/kinda the point of the article, where you will do well at a technical
by typicalrunt 13y ago
There's a much easier way to solve this problem than what you've done. And this is sorta/kinda the point of the article, where you will do well at a technical interview if you know some tricks in programming, whether it be through academic study or just on-the-job stuff.
To find if two words are anagrams of each other, do this:
sort(word1) == sort(word2)
done.
The trick is knowing that an anagram has a signature, and that signature can be found if you sort a word's characters alphabetically. Then you do the same to the other word and compare both of their signatures together. Voilá.
"genuine class" == "alec guinness"
because
"aceegilnnssu" == "aceegilnnssu"
In Ruby you'd write your own alphabetic sorting function first, then apply it to each word.
def sortAZ (word)
word.downcase.unpack("c*").sort.pack("c*")
end
def is_anagram (word1, word2)
sortAZ(word1) == sortAZ(word2)
end
puts "is_anagram(ARGV[1], ARGV[2])"
I recall seeing this trick in a Ruby book (probably PickAxe or something) and thought it was cool because I had never thought about finding an anagram in this way. Regardless, it stuck with me so, if this was asked in an interview, I'd be able to answer the question easily and look like a rockstar...when really it's just knowledge that stuck with me.
By the way, the alphabetic sorting here is done by unpacking each character into its number representation and then sorting the resulting numbers.
- mmorett 13y agoAn even easier way is to check StackOverflow. http://stackoverflow.com/questions/9321654/java-anagram-finder-algorithm http://stackoverflow.com/questions/9321654/java-anagram-find... One of the comments mentions: "Just had a phone interview with Amazon and this was the exact question they asked. Interesting problem if you have more than 10 minutes to solve it. – Javamann Jun 14 '12 at 20:46" So....do you store this knowledge in your back pocket in case you need to check anagrams at work (which will be never), or do you toss it aside knowing you can hit StackOverflow if/when you need it? It seems like the only time this stuff is "used" is on technical interviews. I readily concede you can't substitute StackOverflow for general competence, but an algo for checking for anagrams doesn't seem like general competence.
- deleted 13y ago[deleted]
- philwelch 13y agoThe whole point of the question is that you don't already know the solution. If you already knew the solution the question would be less useful.
- nilkn 13y agoAnother easy solution is to just make a histogram of characters in each word and to compare the histograms. Anyway, if anagram questions were all that were asked in technical interviews, I really doubt we'd have so much critique and analysis here. I've never been asked such a simple question in any technical interview. The closest would be the first phone screen I had for a Google internship, which had (arguably) simpler questions (like raise one integer to an integer power efficiently) but there were like three or four of them that you had to get right.
- philwelch 13y agoThe anagram question is a phone screen question, yeah. I believe the histogram solution is better performing than sorting, because storing the histograms as hash tables is O(n) on both words while the sorting solution is O(nlogn).
- nandemo 13y agoIf the interviewer expects a correct answer off the bat, or rates candidates based on the time they got the solution, then the interview process is bad. But the question is legitimate. If you're a programmer then you should be able to come up at least with a naive (but correct) solution. You don't need any tricks for that. Then you estimate the efficiency of your naive solution and see if you can improve it. That said, there's still the problem that OP and several comments here mention, that the interviewer might get nervous, freeze, etc, even for problems that they would normally have no problem solving.
- nl 13y agoI think the general approach in an interview would be to ask the person being interviews "can you explain what time function that runs in".. "can you improve it", and see if they work out the "sort" trick by themselves. That's how it was done to me anyway (although I talked it through before I started writing, and by the time I got actually writing anything down I'd worked out the trick).