Had the same thing happen to me. Simple problem: find out if two strings are anagrams of each other.
My immediate solution: Sort the two strings and then compare them:
(defn anagrams? [x y] (= (sort x) (sort y)))
or some such. I was fortunate in that they didn't make me implement the sort (because it's been a long time for me) :)
"Ok, what's the efficiency of that solution?"
"Well, assuming the library sort functions I'm using are sane, I'll take a guess and say O(n log n)"
"Can you come up with a more efficient solution."
Off the top of my head, on the spot, I couldn't. Later, during the plane ride home, the obvious occurred to me: Don't sort the strings, just scan through each string once and build a hash table, keeping track of the number of occurrences of each letter in each string. Then compare the occurrences for each string. Not as elegant to express in code, but faster.
As it turns out, they later declined to hire me, giving me an excuse that made it clear they weren't really serious about hiring anyone for the position (as is the case at least half the time, it seems).
And thus ended my latest round of failed interviews. I cancelled the last one I had scheduled (probably another fake) and decided to take a break for a while (I mean, I do have a job right now, so it isn't urgent).
You need not to sort the strings. Create a vector with indices he ascii codes, incrementing for the first string and decrementing the count for the second, and keep a count of the number of chars, if you get a negative number exit false, else if the count of chars is zero then each one is an anagram of the other. (n+m+128) operations n and m are the length of both strings and 128 for creating the vector
on a tangent, one way could be assign a number code to each alphabet. Add the numbers that occur in the strings. IF the sum matches, they are anagrams.
To get decent anagram lengths and complexity, implement the numbers as a dict of repetitions of primes, and implement the multiplication by summing the repetitions. ;-)
In which case you can just compare the dicts without performing the multiplication (which happens to be the costliest part for arbitrary-precision integers).
You would have to make sure the sum of any combination of all characters was unique. For example, if the code was the character number, a=1, b=2, etc, both "abc" and "bbb" would have the same sum.
So I think something silly like:
character_code = len(string)*len(alphabet)^character_index
should work.
My immediate solution: Sort the two strings and then compare them:
or some such. I was fortunate in that they didn't make me implement the sort (because it's been a long time for me) :)"Ok, what's the efficiency of that solution?"
"Well, assuming the library sort functions I'm using are sane, I'll take a guess and say O(n log n)"
"Can you come up with a more efficient solution."
Off the top of my head, on the spot, I couldn't. Later, during the plane ride home, the obvious occurred to me: Don't sort the strings, just scan through each string once and build a hash table, keeping track of the number of occurrences of each letter in each string. Then compare the occurrences for each string. Not as elegant to express in code, but faster.
As it turns out, they later declined to hire me, giving me an excuse that made it clear they weren't really serious about hiring anyone for the position (as is the case at least half the time, it seems).
And thus ended my latest round of failed interviews. I cancelled the last one I had scheduled (probably another fake) and decided to take a break for a while (I mean, I do have a job right now, so it isn't urgent).