10
\$\begingroup\$

I got this out of an article on interviews / code challenges. The challenge text goes like this:

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”.

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

Your function should accept a string as a parameter and return a boolean (true if the string is a palindrome, false if it is not).

Assume that this code will be put into a real production system and write accordingly.

Article in question: https://blog.devmastery.com/how-to-win-the-coding-interview-71ae7102d685

My Implementation:

Even though the article provides a way to solve it, my implementation is different in a few ways, so I would like your reasoning on it.

/*
 * Reverses a given string of characters
 *
 * @param {string} string - the string to reverse
 * @returns {string} - the reversed string
 *
 */
const reverseString = string => string.split('').reverse().join('');

/*
 * Function to test if a given string is a palindrome
 *
 * @param {string} string - the string to test
 * @returns {boolean | string} - returns true/false based on the string, being a palindrome, 
 *                               or string if there is an error
 *
 */
const isPalindrome = string => {
    if (string) {
      let regexReplacer = /\.|\,| |\!|\?|\'|\"|\/|\\|\-|\_|\+|\‘|\’/g;
      let cleanString = string.replace(regexReplacer, '');
      return (cleanString.toLowerCase() === reverseString(cleanString).toLowerCase());
    }
    return '[isPalindrome]: string not supplied, exiting!';
};

/*
 * Basic function to test equality, poor-man's unit test
 *
 * @param {string} test - the string to test
 * @param {string | boolean} reponse - the expected result
 * @param {function} [func = isPalindrome] - the function to test, defaults to isPalindrome
 *
 */
const expectToEqual = (test, reponse, func = isPalindrome) => {
    if (func(test) === reponse) { console.info('Test for "' + test + '" passed!'); }
    else { console.error('Test for "' + test + '" failed!'); }
};

expectToEqual('A man, a plan, a canal, Panama!', true);

expectToEqual('raceca', false);

expectToEqual('No \‘x\’ in Nixon', true);

expectToEqual('', '[isPalindrome]: string not supplied, exiting!');

Link to jsbin: https://jsbin.com/hilatev/edit?js,console

Questions:

  1. Regex - I'm using /\.|\,| |\!|\?|\'|\"|\/|\\|\-|\_|\+|\‘|\’/g to replace non word characters versus this /[^a-z0–9]/ig which is kind of obvious. But would still like your input.
  2. String testing - The implementation provided in the article goes though the string in a while loop and tests each character. Is this favorable vs how I just compared the strings ? Why ?
  3. Returns - The palindrome function returns true/false based on the string, but also returns a string if there is no string supplied. Is this favorable or I should of just thrown an error ?
  4. Edge cases - In hindsight I'm missing and obvious big case, after the regex replace, what if you end up with an empty string? Besides this did I miss anything else major ? Or minor ?
  5. Tests - I've written my own small test function vs in the article it just prints out the expected result (Ex: console.log(isPalindrome("racecar") + " = true");). Is this favorable? Why?
  6. Other - Things that I may have missed ?
\$\endgroup\$
6
  • 5
    \$\begingroup\$ Very good first question, if you put this much explaining/contextualizing effort into all your questions you will be very welcome here. I hope you get a great review :) \$\endgroup\$
    – Caridorc
    Jul 1, 2016 at 12:58
  • \$\begingroup\$ @Caridorc Thanks for the hart warming welcome :) \$\endgroup\$ Jul 2, 2016 at 11:47
  • \$\begingroup\$ @200_success I see you edited my post. Was thanking people in the question against the rules ? \$\endgroup\$ Jul 2, 2016 at 11:48
  • \$\begingroup\$ No, but greetings/thanks are meant to be temporary and may be removed at any time. \$\endgroup\$
    – Caridorc
    Jul 2, 2016 at 12:07
  • 2
    \$\begingroup\$ This Meta post has the policy on saying "thanks". It's an extension of the "no chit-chat" principle given in the tour. Also, it is expected that thanks should be expressed through voting, as that is the currency that makes the site work. \$\endgroup\$ Jul 2, 2016 at 14:03

5 Answers 5

6
\$\begingroup\$

Good question,

  1. as Joseph mentions, white listing is usually a better approach, and in this case it is also the more readable approach.

  2. I like your approach better, it avoids re-writing the wheel

  3. When one passes 4 as a parameter, what will happen? I would throw an Exception if the caller does not pass a String. I would probably pass false if "" is provided.

  4. See point 3.

  5. I am no big fan of TDD, but I am an outlier ;) Still, the Nixon test case made me chuckle

  6. You only have to convert to lowercase once:

    let cleanString = string.replace(regexReplacer, '').toLowerCase();
    return cleanString === reverseString(cleanString);
    

    I also removed the brackets around the return value, my mind tends to get stuck for a second or two, wondering whether I am missing something or whether the author is just paranoid ;)

\$\endgroup\$
1
  • \$\begingroup\$ 1. Agreed 2. :) 3-4. You are right, never handled numbers at all. 5. :) 6. Thanks for pointing this out. I missed this completely. \$\endgroup\$ Jul 2, 2016 at 11:46
6
\$\begingroup\$
  1. I suggest you whitelist allowable characters instead of blacklisting invalid characters. It's easier to list what's allowed than to chase all possible invalid characters.

  2. Suggesting you move out the regex from the function to avoid recreating it on every call. The pattern is actually an object. Also, I'd suggest throwing an error instead of returning a message. Usually better to test.

  3. The function checks if a string is a palindrome or not. Boolean is the correct return type. Errors should only be used when encountering something unexpected.

  4. A lot, especially when you're blacklisting instead of whitelisting.

  5. Small scale, yes. On larger apps, suggesting the use of a full test framework for more options.

\$\endgroup\$
1
  • \$\begingroup\$ 1. Agreed 2. Actually moving the regex out makes sense, ty for pointing it out 3. Ok 4. I kind of knew that before I posted :) 5. Not talking about production, just in the context of interview challenge. \$\endgroup\$ Jul 2, 2016 at 11:41
4
\$\begingroup\$
  1. First, pull the Regex out of the function. Another thing would be to change it to /\W|\_/g because in case you missed one of the characters in your long list of non-word characters.

  2. You are wasting a lot of time. You loop through once to remove all non-word characters, then once to split, then another to reverse, then another to join, then two more for each lowercase, and then loop through to check to see if they are the same...


string = string.replace(regexReplacer,'');
for(var i = 0, j = string.length; i < j;)
    if(string[i++].toLowerCase() !== string[--j].toLowerCase()) return false;
return true;

  1. Throw an error because a full string is still evaluated as true in JavaScript. But, in my opinion do not slow down your code to account for incorrect use. That way the people who know what they are doing won't be slowed down to check if it is a string. That way if someone wraps your library they can make the check if they want to:)

  2. If it's empty then it is palindrome in my opinion. Other than that, I don't see any big ones.

  3. Yes, this is usually called an assert. When doing small tests like you are doing it is fine to create a small one. I prefer modularity when building software. (As I said down in the comments) If all I want is a feather do not give me the whole bird. A lot of libraries out there for JavaScript are like that. Even the sacred jQuery does this, when all I want is to send an AJAX request I have to bring in this huge library. To me it's slow and bulky, so when I make software I make a small piece to handle one thing and optimize it to do that one thing. But, if you are looking for a common library used to handle unit testing at a industry level QUnit does a very good job but just brings the whole bird.

  4. The code I provided should help...

\$\endgroup\$
3
  • \$\begingroup\$ 1. Agree 2. Didn't looked at it like that, you are right 3. Ok 4. The challenge text didn't specify that so I think being cautious is the better approach 5. That is my doubt: do I write my own little test function, and risk it being labelled as a waste of time because in production you would use a real testing framework... 6. It's nicer version, but I usually tend to avoid for loops as much as possible. \$\endgroup\$ Jul 9, 2016 at 13:03
  • 1
    \$\begingroup\$ The for loops are much cheaper than a function call that does a for loop:) In my experience, when writing a library you try to make it as simple and as fast as possible without placing all of these if statements. Assume the user will use it correctly, which allows the user to choose whether or not they want to check for bad input because in most cases they will which means we just checked twice:( Writing your own small test suite is fine, because I like to follow a modularity approach. If all I want is a feather don't give me the whole bird:) And most libraries want to give the bird. \$\endgroup\$
    – tkellehe
    Jul 9, 2016 at 13:14
  • 1
    \$\begingroup\$ Now, from what I have seen in industry it is also bad to have duplicate functionality. It's best to have a single source for a particular functionality. So, if they provide a test suite and it's not modular, then you use that. If they do not, it may be smart to write one that is modular. But, it all depends on how that company wants to function. Spend money on you making a modular one that they can own, but has to be taught and maintain? Or, use a third party that may not be exactly what they want but is more robust and has more support? \$\endgroup\$
    – tkellehe
    Jul 9, 2016 at 13:35
2
\$\begingroup\$

This is even more stale now, but I thought I would chuck this in there. Once you have cleaned the string, you only need to do half a loop to test if it is a palindrome.

PALINDROME_PATTERN = /[^a-z]/g

function testPalindrome(s) {
  if (typeof s !== 'string') throw 'Parameter is not a string!'
  const s2 = s.toLowerCase().replace(PALINDROME_PATTERN, '')
  for (let i = 0; i < s2.length / 2; i++) {
    if (s2[i] !== s2[s2.length - i - 1]) return false
  }
  return true
}

I am stripping out digits, but the regex could be easily changed if you want to keep them. I am also assuming an empty string is a palindrome; it reads the same backwards and forwards.

\$\endgroup\$
1
\$\begingroup\$

This question is stale, but...

A. For efficiency, you can just call toLowercase() once.

B. One of the fundamental questions is whether an empty string-- or a string with no letters-- is a palindrome or not. If you say yes, then you don't need to put any code for it and you'll get the right answer:

  1. normalize string by removing all non-letters and lower-case.
  2. reverse it
  3. return true or false based on equivalency

C. Your point C, "also returns a string if there is no string supplied" isn't really accurate. If you pass it an empty string, you get the error string back. This is probably a bug. But to answer your question, for a boolean function, it's probably much better to just throw an exception. In this case, you can just take all this code out. The reverse code will blow up and you'll get the exception.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.