Palindromes & Code Challenges

Tacocat is Tacocat 🐱 😺 🐈

Hello, reader! Welcome to my super cool tech blog about palindromes and hidden patterns. You may remember palindromes from school, writing an English paper, or a trivia night question. They are also common on “easy” level coding problems like on LeetCode or HackerRank. Sometimes it’s a bit hard to wrap your head around so I’m writing this blog to breakdown a few things that are helpful about palindromes and writing code.

"A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam, racecar. There are also numeric palindromes, including date/time stamps using short digits 11/11/11 11:11 and long digits 02/02/2020. Sentence-length palindromes ignore capitalization, punctuation, and word boundaries." - wikipedia

See the original side, middle, and mirror side

The Symmetrical Pattern

When you come across a Palindrome in a coding challenge for the first time it can be a little overwhelming. Even the word sounds a bit intimidating, but I encourage you to look at it another way. When you see a palindrome just remember this, it’s a mirror image. You can break it down into three parts. An original side, middle point, and mirror side. If you can divide that palindrome at its middle point. You can compare the original side with the mirror side(probably want to invert that side). If the two should match, you got a bonafide palindrome. Once you got that locked in, your potential solution beings to take shape.

LeetCode question #9

9. Palindrome Number
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Follow up: Could you solve it without converting the integer to a string?

Let’s take a look at a problem I solved on LeetCode. Initially, I wanted to make a brute force solution without “the follow up”. It’s normal to have your proctor, pivot the requirements of the challenge. The idea being, they want to see how well you do under pressure. So I took my time, I thought about how a palindrome works and came up with this novel solution.

My Thought process:

1. Set up a base case, for x being a negative number.
2. Convert x to a string
3. Break down the string into an array of single characters
4. Reverse the array (the main reason I converted the data)
5. Join the array into one string
6. Check that reversed string vs. the original string
7. Return a boolean output

My first Attempt
const isPalindrome = function(x) {
    if(x< 0) return false;
    let string =`${x}`
    let reverse = string.split('').reverse().join('')
    
    if(string === reverse) return true;  
    
    return false;
};

Refactor

“I have not failed. I have found 10,000 ways that don’t work.” — Thomas Edison

This isn’t a great solution. But I did manage to wrap my head around the problem. It’s slow and it takes up a bit of space. Also will need to figure out how to solve this without converting the number into a string. This wasn’t easy for me as you had to pivot your thinking from 3rd space to something more mathematical.

Not a great run time or memory usage, but I got it to pass!

Division & Remainders

How do you take a number like 321 and make it 123? Simple, you can do so with place values, simple division, and remainders. Now I’ll admit, this didn’t strike me right away. It’s been a while since I had a math exam, but it’s not a hard concept to understand.

My Thought Process…

1. You have to play with the place value.
2. dividing the number argument by 10 works, which moves the place value
3. I need to hold on to that remainder or tenth, 100th, etc. place value in a variable.
4. I’ll need to hold on to that quotient from the original number argument as well. I should probably round down.
5. a while loop could work, have it return the number when it breaks on zero.

My Notes:

let y = 0 (holds previous remainder, start at 0)
let x = num / 10 (holds quotient of number, start at num)
let num = (starts with number argument)

In a while loop…
y = ( y * 10) + num % 10
X = x/10
...Break at zero! return reversed number!

How to test it out

Let’s imagine we have a number like 123 and we want the reverse of it. How would our solution behave step by step? When in doubt? write it out. Leave nothing to chance. Let’s look at my notes below.

Round 1

Notice how we are saving the remainder and the quotient in separate variables.

y = 0 * 10 = 0 + 123 % 10 = 3 remainder ///first Digit
X = 123/10 = 12 round down

Round 2

See how the remainder flows back into y, while the quotient flows back into x

y = 3 * 10 = 30 + 12 %10 = 2 remainder ///second Digit
X = 12/10 = 1 round down

Round 3

This keeps going, both y and x are getting smaller.

y = 2 * 10 = 20 + 1%10 = 1 remainder /// third Digit
X = 1/10 = 0 round down

Round 3

Eventually, x and y become zero. Breaking the loop and returning the number.

y = 1 * 10 = 10 + 0%10 = 0 remainder /// Zero
X = 0/10 = 0 round down 
Loop Breaks !
Math Refactor 
function isPalindrome(x) {
  let num = x;
  if (x < 0) {
    return false;
  }
  let y = 0;
  while (num) {
    y *= 10; 
    y += num % 10;
    num = Math.floor(num / 10);
  }
  return x === y;
};

Failures are secret lessons if you pay attention to them…

I would be lying to you if I said I got the refactor on my own. I didn’t and that’s important to understand. Other people’s solutions will help mold the way you think. They open the eyes to the possibilities. Solutions are a great way to improve on your failures. If you do get things right, it’s equally valuable to look at the other solutions as well. The range of ambiguity in solutions is quite surprising and only improves your understanding of the problem.

Conclusion

Palindromes one minute, next it’s all about math. Seems a bit misleading right? Yes, that’s the point. Reviewers want to put you outside of your comfort zone. They want to see how well you can solve problems in a challenging environment. It’s frustrating, but get accustomed to it now. The reward is an awesome role as a developer!

Links Below:

Shout out to Captain Canada on leet code, for the OG refactor solution!

Wikipedia on Palindromes https://en.wikipedia.org/wiki/Palindrome

LeetCode https://leetcode.com/

HackerRank https://www.hackerrank.com/