The Palindrome Algorithm: Working Through A Mock Technical Interview

A week and a half ago, I had a mock technical interview. It was my first technical interview ever, excluding my project reviews at Flatiron School. I was very nervous.

During the interview, I was asked to solve an algorithm: Given a string, check if the characters of the given string can be rearranged to form a palindrome.

I was immediately mad at myself upon hearing the question. Just that week I had attended an Algorithm Workshop and was told to look out for palindromes in particular. I kept telling myself to sit down and study them, but never got around to it. And there I was, frozen and staring at my screen.

I was able to pull myself together and worked through most of the logic of the question, but struggled with applying the code in vanilla Javascript. With some really helpful tips from my interviewer, I ended up working through the problem as follows:

function isPalindrome(str) {
 //some code goes here
}

console.log(isPalindrome('civic')); // civic => true
console.log(isPalindrome('civil')); // civil => false
console.log(isPalindrome('level')); // level => true
console.log(isPalindrome('sees')); // sees => true

My first thought was to split the string so that I could work with individual letters, something like this:

function isPalindrome(str) {
 let chars = str.split("")
}

I had to think quite a bit about what those split letters needed to do. My interviewer asked me some great prompting questions which led me to the realization that I didn't need to split them at all.

When it comes down to it, palindromes are just words that have, at most, one character with an odd number of occurrences. All other letters have to appear an even amount of times.

With that, I set out to create an object that counted how many times each letter appeared in a word.

function isPalindrome(str) {

  let count = {}
  for (let i = 0; i < str.length; i++) {
    let letter = str[i];
        !count[letter] ? count[letter] = 1 : count[letter]++;
  }

 return count

}

console.log(isPalindrome('civic')); // { c: 2, i: 2, v: 1 }
console.log(isPalindrome('civil')); // { c: 1, i: 2, v: 1, l: 1 }
console.log(isPalindrome('level')); // { a: 2, b: 2, c: 2, d: 1 }
console.log(isPalindrome('sees')); // { s: 2, e: 2 }

Sweet! Now I knew how many times each letter appeared in a string. All I had to do was check that only one letter, if any, had an odd count.

This was the part where the code itself stumped me. I understood what needed to happen, but not how to write the code. My interviewer was incredibly helpful. I pseudo-coded the rest of the function and he helped me translate it into Javascript.

The first step: Get an array of values for each letter by using Object.values(count). Then, set a variable to track how many odd values are in the array. I used a second for loop and the remainder operator to increase oddCounts when a letter count was not divisible by 2.

Lastly, I set the function to return false if the oddCounts was greater than 1.

And voilà:

function isPalindrome(str) {

  let count = {}
  for (let i = 0; i < str.length; i++) {
    let letter = str[i];
        !count[letter] ? count[letter] = 1 : count[letter]++;
  }

  let counts = Object.values(count)
  let oddCounts = 0; 
    for (let i = 0; i < counts.length; i++) { 
        if (counts[i] % 2 != 0) { 
            oddCounts++;
        }

        if (oddCounts > 1) { 
            return false;
        }
    }
  return true; 
}

console.log(isPalindrome('civic')); // civic => true
console.log(isPalindrome('civil')); // civil => false
console.log(isPalindrome('level')); // level => true
console.log(isPalindrome('sees')); // sees => true

I learned a lot from my mock technical interview and I'm so glad that I was afforded the opportunity have one. I feel as though I am very strong when it comes to talking about code, but have a difficult time thinking through coding during the live challenges.

With the experience in my back pocket, I know to practice my algorithms, brush up on some basic Javascript concepts, and not let Aibohphobia* get me down.

*The unofficial word for 'fear of palindromes', tehe.

Comments

[jamesmaskell]

Technical interviews and tests are stressful, even mock ones. Good work!

Hopefully a helpful tip... Try and use as less 'state' as possible in your algorithm (and code in general). State makes code complicated and can introduce more defects. The less you have to think about the better. Try and do this again with as few variables as possible.

[Taylor Sieling]

Thanks so much for the advice! I definitely intend to go back and refactor the code as I practice and learn more.