Hacker News Reader

Comment by YeGoblynQueenne | Hacker News Reader

>> On this particular challenge, I am expecting many will use RegEx as a part of the solution. The regex needed for this is some of the most basic regex out there

Woohooa, cowboy. The language of palindromes is a classic example of a context free language that is not possible to describe with a regular grammar, such as accepted by a regular automaton... in other words a regex.

In Recruiter-Parseable English (RPE): you can't decide whether a string is a palindrome using a regex. It's impossible. Like, maths-impossible.

You can use regular expressions to compare strings while you decide whether a string is a palindrome but you can't do the whole thing in one regex.

View on HN

He's not expecting the use of a regex to do the whole heavy lifting of checking for a palindrome, in the example he uses it for the replace functionality to remove non-alphanumeric characters.

https://gist.github.com/anonymous/e8553707cd6162040e7d12b2a1...

stringToTest = stringToTest.toLowerCase().replace(/[^a-z0–9]/ig, '');

Yep, should have read all the way through before posting.

But the example solution is so bad anyway.

What's your preferred solution?

Nothing more complicated than this:

  is_a_palindrome(S) {
    assert is_a_string(S)

    if reverse(S) == S
      return true
    return false
  }

A string is a palindrome if it's equal to itself reversed. The example "solution" in the article is dreadfully overengineered to death and back. Noone interviewing should be happy to see such a solution and noone being interviewed should expect to be required to give such a solution, to such a trivial problem.

Unless of course the recruiter is trying to catch you pants-down, but then the parent article wouldn't post that overengineered "solution" as a gold-standard, like they did.

That solution would fail to catch several of the examples that were requested to be caught. Sometimes something that appears overengineered is built that way to meet the actual requirements a problem presents.

>> Sometimes something that appears overengineered is built that way to meet the actual requirements a problem presents.

That's poppycock. Here are the requirments:

>> Write the most efficient function you can that determines whether a given string is a palindrome.

A palindrome is a string that is equal to itself reversed. That's like, the mathematical definition of a palindrome (simplified, of course). What I gave you catches exactly that. If some of the test cases in the proposed solution don't agree with the commonly accepted definition that's a problem of the proposed solution, not mine.

Also, in terms of the "most efficient" solution, the guy's proposed solution is far from that- because he tries to be smart and reverse the string while he compares it, thinking that's faster than going the whole hog. But that's only going to save you some cycles a tiny amount of the time, because the vast majority of strings you can expect to encounter are unlikely to be palindromes. Reversing and comparing the string to itself is the neatest, quickest, most legible and prettiest thing you can do in this case, regardless of your use case or anything else.

And if you're a recruiter that expects anything else, that's because you have no idea what you're looking for, not because you are as smart as you think you are.

You omitted the bit just above your quote, which says:

>> A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward. Allowances may be made for adjustments to capital letters, punctuation, and word dividers. Examples in English include “A man, a plan, a canal, Panama!”, “Amor, Roma”, “race car”, “stack cats”, “step on no pets”, “taco cat”, “put it up”, “Was it a car or a cat I saw?” and “No ‘x’ in Nixon”.

Given the last sentence, doesn't that change the meaning of your sentence to directly refute your interpretation?

Reply on news.ycombinator.com