[p4wnc6]

Regexes would not be a good way. Starting a pointer at the beginning and end and moving them toward each other is what I would suggest in an interview. If I was interviewing someone else, I'd also be impressed if they came up with the idea of sorting the string and counting characters (only at most one character could have at odd number of occurrences). Even though sorting and counting is nlogn and requires either storing the sorted string in new memory or else saving the inverse sort to unsort at the end (if the sort is in-place), I wouldn't care. In an interview setting, if they could identify those weaknesses, that's good enough. It's clever and shows attention to detail and good critical thinking for someone to come up with the sort-and-count solution. An interview is not the time nor place to be grilling someone about whether an nlogn solution is really optimal. That's just wasted time.

The fact that the post's author offered regexes as a solution is a bit frightening. In many languages, such as with Python's built-in re module, this is literally impossible, because the regular expression engine is literally confined to check for regular grammars, and you can show that no finite state automaton is adequate for expressing all palindromes (basically because they can't remember an arbitrary number of characters from the start of the string to use at the end).

Of course, lots of languages have regular expression engines that are more powerful than this, but it's a sham for an interview question to rely on that. It doesn't read to me like the post's author actually considered the theory of computation aspect of this, and instead just glibly and naively rattled off that regular expressions should work well.

This is the person judging the candidates on whether they are talented enough at computer science? Yikes.

[garrettgrimsley]

>I'd also be impressed if they came up with the idea of sorting the string and counting characters

While that method would identify if a string has the necessary attributes of a palindromic string it is not sufficient to prove that a string is a palindrome.

>This is the person judging the candidates on whether they are talented enough at computer science? Yikes.

Right, anyone reading the OP would probably be better served by Steve Yegge's posts[0, 1] on the subject.

[0] https://sites.google.com/site/steveyegge2/five-essential-pho...

[1] http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...

Edit: Went back and actually read the code provided, they only use regex for a preprocessing step.

[p4wnc6]

You're totally right. I was confusing the stated problem with a common associated problem: whether a string is a permutation of a palindrome.

[jaredsohn]

If you use a bucket sort, your time complexity could be O(max(n,k)) and space O(k) where k is the size of the character set and n is the length of the string. Depending on the relationship between n and k, this could be faster than n log n. (But the pointers solution or even comparing against a reversed string seems better for both time and space.)

Also, your solution is poor since it only tells you that a string is _not_ a palindrome in certain cases but cannot tell with certainty that a string is a palindrome. For example, 'aabb' will pass your test but is not a palindrome.

[p4wnc6]

I assume the 'poor' solution you meant was the sort and count solution. You're totally right. I was confusing the stated problem with a common associated problem: whether a string is a permutation of a palindrome.