Hacker News Reader

Comment by rilindo | Hacker News Reader

Here is a first go at it:

https://gist.github.com/rilindo/6575580

Essentially, I just checked to see if the characters in the first string exists in other string and exits out of the code. It probably won't cover every use case (in other words, probably very buggy), but it is a start.

However, I have the luxury of relaxing while looking up the functions online, writing the code by my lonesome and then verifying it by running it directly. Last I checked, not any of these things are likely not present or available in a white board interview.

EDIT: I should at least put it in a function. :D

View on HN

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.

An even easier way is to check StackOverflow.

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.

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

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

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

The 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).

I 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).

Remembering the standard library isn't the competency being tested for, but rather the soundness of your solution. Your first solution has two problems from an interview-question standpoint: first, it's incorrect (it misses the case where two words use all the same letters but aren't anagrams, like "banana" and "nab"), and second, you're looping through each character of the second string for each character of the first string so it's a slow algorithm. I would probably try and get you to figure these out with probing questions, but the expectation is that you can figure it out and fix it.

What an interviewer will usually be looking for on a whiteboard interview is not knowledge of a library, but that the interviewee can reason that there's a better solution that works much faster than this solution.

You might want to try something like 'return set(x)==set(y)'. Or, a better solution might be 'return set(collections.Counter(x).items())==set(collections.Counter(y).items())'.

The point of the question isn't to see if you've memorized every single stdlib function. If you can describe a stdlib function but can't remember it, a good interviewer will tell you about it.

Be careful using sets -- what about "banana" and "ban"

The OP's solution didn't deal with letter counts at all; my first expression was to show him a similar solution that was more succinct to illustrate the principle at work. My second solution deals with multiplicity properly.

Yes and I appreciate it.

https://gist.github.com/rilindo/6576017

New toy to play with. :)

Python's Counters can also be compared directly. No need to drop them in a set; `Counter([1, 1, 2, 3]) == Counter([1, 2, 3, 1])`.

Using Counters is actually pretty cool... it's basically a sparse histogram. Can't believe I've never used 'em before -- all I've ever used from collections is OrderedDicts.

Actually... I prefer the parent's solution using set(counter.items()). This way, you know that the equality tests are ordering-agnostic. It's not clear if that's the case for counters... even the docs are unclear AFAICT: http://docs.python.org/2/library/collections.html#collection...

At that point, might as well just do `sorted(list(x)) == sorted(list(y))`.

Counters are effectively building a sparse histogram by going through each element in x, and then each element in y. Ignoring the test for equality, the Big-O for histograms is O(x+y). For sorting in general, the Big-O is O(x·log(x)+y·log(y)). In other words: the sorting solution is correct but less efficient.

Reply on news.ycombinator.com