5 ms·

Here is a first go at it: https://gist.github.com/rilindo/6575580 https://gist.github.com/rilindo/6575580 Essentially, I just checked to see if the characters

by rilindo 13y ago

Here is a first go at it: https://gist.github.com/rilindo/6575580 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

MichaelSalib 13y ago
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.
- minikomi 13y ago
  Be careful using sets -- what about "banana" and "ban"
  - MichaelSalib 13y ago
    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.
    - rilindo 13y ago
      Yes and I appreciate it. https://gist.github.com/rilindo/6576017 https://gist.github.com/rilindo/6576017 New toy to play with. :)
- deleted 13y ago
  [deleted]
- matchu 13y ago
  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])`.
  - beambot 13y ago
    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#collections.Counter http://docs.python.org/2/library/collections.html#collection...
- meowface 13y ago
  At that point, might as well just do `sorted(list(x)) == sorted(list(y))`.
  - beambot 13y ago
    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.
cle 13y ago
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.
philwelch 13y ago
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.
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 ago
  An 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]
deleted 13y ago
[deleted]

by rilindo 13y ago

MichaelSalib 13y ago

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.

minikomi 13y ago
Be careful using sets -- what about "banana" and "ban"
- MichaelSalib 13y ago
  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.
  - rilindo 13y ago
    Yes and I appreciate it. https://gist.github.com/rilindo/6576017 https://gist.github.com/rilindo/6576017 New toy to play with. :)
deleted 13y ago
[deleted]
matchu 13y ago
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])`.
- beambot 13y ago
  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#collections.Counter http://docs.python.org/2/library/collections.html#collection...
meowface 13y ago
At that point, might as well just do `sorted(list(x)) == sorted(list(y))`.
- beambot 13y ago
  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.

cle 13y ago

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.

philwelch 13y ago

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.

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 ago
An 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]

deleted 13y ago

[deleted]