First, it's not so clear in what sense "efficient" is actually a real requirement if this is a model answer.
If the average input is very small then the cost of compiling/interpreting the regex is going to dominate any modest run-time improvement over even an extremely naive implementation.
And if the inputs are very large then the probability of contradiction in the first few characters even is extremely high, so all the upfront normalization is a huge waste.
I'm having trouble imagining the typical data set where this would be an efficient implementation and where there even exist non-ridiculous inefficient implementations.
Second, doesn't using regexes kind of defeat the whole point of the Palindrome exercise from an evaluation perspective? If someone asked if me if they could use regexes in a coding interview for this question my response would be "good instinct. If you have no other way then go for it. But I was really hoping to see you work through implementing/debugging/commenting/testing an implementation without regexes."
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.
>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.
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.
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.
It's because there is no standard way to determine the properties of a unicode grapheme cluster in JavaScript. Otherwise you could do things like isDigit(), isNumeric(), isPunctuation(), isWhitespace(), etc. Or just ask directly isLetter().
A Grapheme cluster basically corresponds to what a human would consider a "single letter", including any combining marks, etc.
> And if the inputs are very large then the probability of contradiction in the first few characters even is extremely high, so all the upfront normalization is a huge waste.
First, it's not so clear in what sense "efficient" is actually a real requirement if this is a model answer.
If the average input is very small then the cost of compiling/interpreting the regex is going to dominate any modest run-time improvement over even an extremely naive implementation.
And if the inputs are very large then the probability of contradiction in the first few characters even is extremely high, so all the upfront normalization is a huge waste.
I'm having trouble imagining the typical data set where this would be an efficient implementation and where there even exist non-ridiculous inefficient implementations.
Second, doesn't using regexes kind of defeat the whole point of the Palindrome exercise from an evaluation perspective? If someone asked if me if they could use regexes in a coding interview for this question my response would be "good instinct. If you have no other way then go for it. But I was really hoping to see you work through implementing/debugging/commenting/testing an implementation without regexes."