π₯ Kill this interview question π₯
π― The challenge
Write a function that β given a string β returns true if the string is a palindrome or false otherwise.
Let's look at 11 different approaches to solving this in JavaScript ππ§΅
π― The challenge
Write a function that β given a string β returns true if the string is a palindrome or false otherwise.
Let's look at 11 different approaches to solving this in JavaScript ππ§΅
π The definition
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as taco cat or madam or racecar or the number 10801.
- Wikipedia
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as taco cat or madam or racecar or the number 10801.
- Wikipedia
According to the definition, we need to strip potential non-alphanumeric characters thus convert to lower-case.
So in all of the following solutions, we will be using a "clean" function to get a clean sequence of characters.
So in all of the following solutions, we will be using a "clean" function to get a clean sequence of characters.
To measure the different approaches, I'm gonna run them all through palindromes of various lengths, and measure runtime performance in NodeJS.
- A small palindrome of 10 characters
- A medium palindrome of 1000 characters
- A large palindrome of 5000 characters
- A small palindrome of 10 characters
- A medium palindrome of 1000 characters
- A large palindrome of 5000 characters
πΈ Using a for loop
For each character at position i, we compare with the character at position i from the end.
If any of these does not equal, we can reject the input as being a palindrome and break out of the loop and return false.
For each character at position i, we compare with the character at position i from the end.
If any of these does not equal, we can reject the input as being a palindrome and break out of the loop and return false.
Performance:
Small: 0.0731 ms
Medium: 0.1267 ms
Large: 0.6272 ms
Pros:
Performs very well, even on large strings.
We are able to return as soon as we identify the first violation.
Cons:
In the world of ES6, this solution appears a bit βclumsyβ to read.
Small: 0.0731 ms
Medium: 0.1267 ms
Large: 0.6272 ms
Pros:
Performs very well, even on large strings.
We are able to return as soon as we identify the first violation.
Cons:
In the world of ES6, this solution appears a bit βclumsyβ to read.
πΈ Using forβ¦of
Similar to a for loop.
With this approach, we convert the string into an array and then we iterate through each element.
For each element, we remove the last element of the array using pop(), and then we compare the current element with that.
Similar to a for loop.
With this approach, we convert the string into an array and then we iterate through each element.
For each element, we remove the last element of the array using pop(), and then we compare the current element with that.
Performance:
Small: 0.0415 ms
Medium: 0.0966 ms
Large: 0.9997 ms
Pros:
Performs good, and looks fairly readable.
We are able to return as soon as we identify the first violation.
Cons:
We imperatively mutate the array, which cost us a bit of performance.
Small: 0.0415 ms
Medium: 0.0966 ms
Large: 0.9997 ms
Pros:
Performs good, and looks fairly readable.
We are able to return as soon as we identify the first violation.
Cons:
We imperatively mutate the array, which cost us a bit of performance.
πΈ Using split, reverse and join
Alright, letβs turn to use some of JavaScripts inbuilt methods.
This solution is very intuitive β we will simply reverse the string and compare it to the original. If they are equal, itβs a palindrome.
Alright, letβs turn to use some of JavaScripts inbuilt methods.
This solution is very intuitive β we will simply reverse the string and compare it to the original. If they are equal, itβs a palindrome.
Performance:
Small: 0.1633 ms
Medium: 0.1986 ms
Large: 1.5192 ms
Pros:
Concise and very readable.
Easy to understand what is going on.
Cons:
Not the most well-performing, namely on small strings.
Small: 0.1633 ms
Medium: 0.1986 ms
Large: 1.5192 ms
Pros:
Concise and very readable.
Easy to understand what is going on.
Cons:
Not the most well-performing, namely on small strings.
πΈ Using forEach
This solution is quite similar to solutions 1 and 2.
We are going to convert the string into an array and then apply forEach on it.
For each iteration, we are doing the same comparison as in solution 1, but this time we will flag a variable in the outer scope.
This solution is quite similar to solutions 1 and 2.
We are going to convert the string into an array and then apply forEach on it.
For each iteration, we are doing the same comparison as in solution 1, but this time we will flag a variable in the outer scope.
Performance:
Small: 0.0444 ms
Medium: 0.1487 ms
Large: 1.2537 ms
Pros:
Plus points for using ES6 methods.
Overall more readable and easy to understand.
Cons:
With forEach we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
Small: 0.0444 ms
Medium: 0.1487 ms
Large: 1.2537 ms
Pros:
Plus points for using ES6 methods.
Overall more readable and easy to understand.
Cons:
With forEach we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
πΈ Using map
We return a new array with true/false for each element, representing whether this character matches the same character from the end.
Finally, we are using some to check if the new array contains a false.
If it doesnβt the string is a palindrome, otherwise not.
We return a new array with true/false for each element, representing whether this character matches the same character from the end.
Finally, we are using some to check if the new array contains a false.
If it doesnβt the string is a palindrome, otherwise not.
Performance:
Small: 0.0644 ms
Medium: 0.1560 ms
Large: 0.9630 ms
Pros:
Plus points for using ES6 methods.
Cons:
With map we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
Small: 0.0644 ms
Medium: 0.1560 ms
Large: 0.9630 ms
Pros:
Plus points for using ES6 methods.
Cons:
With map we cannot break the iteration, nor can we ensure only doing string.length / 2 total iterations.
πΈ Using reduce
This solution is similar to using forEach, instead, we use reduce.
The key difference here is, that where we had to flag a variable in the outer scope using forEach, we can pass this flag into the next iteration using reduce.
This solution is similar to using forEach, instead, we use reduce.
The key difference here is, that where we had to flag a variable in the outer scope using forEach, we can pass this flag into the next iteration using reduce.
Performance:
Small: 0.0425 ms
Medium: 0.1830 ms
Large: 0.8459 ms
Pros:
Plus points for using ES6 methods.
Cons:
If the check fails early, we keep passing on false to the next iteration.
This may seem like quite a waste, namely on larger strings.
Small: 0.0425 ms
Medium: 0.1830 ms
Large: 0.8459 ms
Pros:
Plus points for using ES6 methods.
Cons:
If the check fails early, we keep passing on false to the next iteration.
This may seem like quite a waste, namely on larger strings.
πΈ Using every
We convert the string into an array, and then we apply every to it.
We convert the string into an array, and then we apply every to it.
Performance:
Small: 0.0414 ms
Medium: 0.1977 ms
Large: 1.4204 ms
Pros:
Concise.
Will break early if a character does not match.
Cons:
We canβt ensure only doing string.length / 2 total iterations.
In the case of a palindrome, every will iterate through the whole array.
Small: 0.0414 ms
Medium: 0.1977 ms
Large: 1.4204 ms
Pros:
Concise.
Will break early if a character does not match.
Cons:
We canβt ensure only doing string.length / 2 total iterations.
In the case of a palindrome, every will iterate through the whole array.
πΈ Using recursion
Letβs solve this problem by using recursion.
The idea is to compare the first and the last character of a string.
If they are equal, we are going to create a substring where the first and last letter is removed, and then recursively apply the function again.
Letβs solve this problem by using recursion.
The idea is to compare the first and the last character of a string.
If they are equal, we are going to create a substring where the first and last letter is removed, and then recursively apply the function again.
Performance:
Small: 0.0842 ms
Medium: 5.1806 ms
Large: 108.5716 ms
Pros:
The interviewer may give you credit for knowing how to handle recursion.
Other than that, there is probably not much good to say about this solution.
Small: 0.0842 ms
Medium: 5.1806 ms
Large: 108.5716 ms
Pros:
The interviewer may give you credit for knowing how to handle recursion.
Other than that, there is probably not much good to say about this solution.
Cons:
There are, on the other hand, some considerations here.
We are opening a lot of function closures, and building up a β potentially β large call stack.
Notice how the performance on the large string blows through the roof here, compared to any of the previous solutions.
There are, on the other hand, some considerations here.
We are opening a lot of function closures, and building up a β potentially β large call stack.
Notice how the performance on the large string blows through the roof here, compared to any of the previous solutions.
Alright - let's take it to the next level now π€©
Letβs imagine that the interviewer asks you if there is a way that we can approximate how βcloseβ a given string is to be a palindrome.
Let's look at 3 approaches.
I will use these test-strings for verification π
Letβs imagine that the interviewer asks you if there is a way that we can approximate how βcloseβ a given string is to be a palindrome.
Let's look at 3 approaches.
I will use these test-strings for verification π
πΈ Calculating the match percentage
Let's revisit the example above using map.
But we're gonna refactor it a little.
Let's count the number of 'false' and divide it with the total length to get a match percentage.
Let's revisit the example above using map.
But we're gonna refactor it a little.
Let's count the number of 'false' and divide it with the total length to get a match percentage.
Result:
100.00%
80.95%
27.27%
0.00%
0.00%
Performance:
Small: 0.0718 ms
Medium: 0.2233 ms
Large: 1.4426 ms
100.00%
80.95%
27.27%
0.00%
0.00%
Performance:
Small: 0.0718 ms
Medium: 0.2233 ms
Large: 1.4426 ms
πΈ Using cosine similarity
The idea is, that we are going to split the string into two equal parts and then revert one of them.
Then we convert them into their vector representation in n dimensions, n being the length of the half strings.
The idea is, that we are going to split the string into two equal parts and then revert one of them.
Then we convert them into their vector representation in n dimensions, n being the length of the half strings.
Then we are going to measure the angle between these vectors.
The bigger the angle, the bigger the mismatch between the strings.
Sounds fun, right? π€©
Let's do this!! π
The bigger the angle, the bigger the mismatch between the strings.
Sounds fun, right? π€©
Let's do this!! π
The tricky part is to represent a character as a number that includes both the character itself and its position in the string.
Here, Iβm using the characters charCode and then subtracting the position in the array from that number.
Here, Iβm using the characters charCode and then subtracting the position in the array from that number.
Alright, assuming we've converted both strings into vector representations, we can now proceed with the following steps:
- Calculate the dot product of the two vectors
- Calculate the magnitude of each vector
- Calculate the cosine of the angle between the vectors
- Calculate the dot product of the two vectors
- Calculate the magnitude of each vector
- Calculate the cosine of the angle between the vectors
Since the cosine of the angle is in the range of [-1; 1], we want to convert this into a percentage, where -1 represents 0% and 1 represents 100%.
We simply add 1 to the cosine and divide it by to, and finally multiplies with 100.
Let's put it all together π
We simply add 1 to the cosine and divide it by to, and finally multiplies with 100.
Let's put it all together π
![Since the cosine of the angle is in the range of [-1; 1], we want to convert this into a percentage,...](https://pbs.twimg.com/media/E9IuCVHXEAATyDO.jpg)
Result:
100.00%
90.04%
57.90%
69.17%
12.37%
Performance:
Small: 0.0314 ms
Medium: 0.2597 ms
Large: 1.5066 ms
100.00%
90.04%
57.90%
69.17%
12.37%
Performance:
Small: 0.0314 ms
Medium: 0.2597 ms
Large: 1.5066 ms
πΈ Using Levenshtein distance
Are you still here after all that? π
Haha - you're insane!
Keep reading, cause it's getting worse π
Are you still here after all that? π
Haha - you're insane!
Keep reading, cause it's getting worse π
Just as with the previous approach, we are going to start by splitting the string up into two half strings and revert the second one.
The idea is to calculate the Levenshtein distance between these two strings and convert that into a measure of percentage.
The idea is to calculate the Levenshtein distance between these two strings and convert that into a measure of percentage.
The Levenshtein distance is the minimum number of single-character edits required to change one word into the other.
We can calculate the Levenshtein distance using the following formula π
We can calculate the Levenshtein distance using the following formula π
A single-character edit can be either an insertion, a substitution or a deletion.
For example, if we calculate the Levenshtein distance of the two words βHONDAβ and βHYUNDAIβ, we get 3:
1. Delete the letter "Y".
2. Substitute "O" with "U"
3. Insert "I"
For example, if we calculate the Levenshtein distance of the two words βHONDAβ and βHYUNDAIβ, we get 3:
1. Delete the letter "Y".
2. Substitute "O" with "U"
3. Insert "I"
Letβs go through this setup, and see how we can use this to approximate a string in terms of a palindrome.
- Split the string into two even half strings
- Reverse the second half
- Create a matrix
- Fill the matrix
- Count edits
- Convert into percentage
- Split the string into two even half strings
- Reverse the second half
- Create a matrix
- Fill the matrix
- Count edits
- Convert into percentage
Let's put the whole thing together, and we get something like this π
Result:
100.00%
80.00%
27.27%
6.67%
0.00%
Performance:
Small: 0.0635 ms
Medium: 32.5343 ms
Large: 616.9648 ms
100.00%
80.00%
27.27%
6.67%
0.00%
Performance:
Small: 0.0635 ms
Medium: 32.5343 ms
Large: 616.9648 ms
Are you kidding me?!
Did you really read all the way to here?
You are either extremely committed or totally crazy π
Did you really read all the way to here?
You are either extremely committed or totally crazy π
Anyway! These are all approaches to determine (or approximate) whether a string is a palindrome.
It's a common interview question, and you're gonna score great points if you can ace this by arguing for different approaches and their pros and cons βοΈ
It's a common interview question, and you're gonna score great points if you can ace this by arguing for different approaches and their pros and cons βοΈ
Loading suggestions...