A General Note about Coding Interviews

Coding interviews can be difficult. You’re tested on data structures and algorithm design that you might rarely use in your actual day-to-day work. But most tech companies will ask at least a few algorithm problems, so you need to be prepared to solve them. Make sure you practice them, understand the underlying patterns and principles, and be able to discuss their performance.

Problem Source / Inspiration

Cracking the Coding Interview
Asked by: FAANG

Problem Description

Given a string, write a function to check if it is a permutation of a palindrome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

Example
Input: “Tact Coa”
Output: true (permutations: “taco cat”, “atco cta”, etc.)

Problem Solution

The first step in any algorithm problem is to build your mental model. This step is easier for some problems and harder for others. In case you’re stuck on this one, I’ve decided to illustrate part of my mental model. Let’s take a look below.

An illustration of normalizing and mapping a string to its character count

For me, this problem can be broken down into two parts: character mapping and validation. We need to count the frequencies of each character because of the nature of palindromes. Palindromes are symmetric, which means for every character on one half of the string you should have a matching character on the other side. There is an exception for odd-length strings because they might have a central character that does not need to be matched. Thus, we can count all of the characters and then validate them afterward. The illustration above shows the character mapping process.

First, we normalize the incoming string since our palindromes are case-insensitive and spaces are to be ignored. It would be best to clear this up with your interviewer since they might expect otherwise. After that, we just iterate through the string and update the count in the mapping.

The second part of the problem is to validate the character counts to make sure they abide by the rule we defined earlier. Each character should have a pair with only one exception. That is, each character should occur an even number of times except for potentially one character can occur an odd number of times.

That’s it! Let’s check out how we might translate this mental model to code.

A solution to validating a string for a palindrome permutation

As you can see, lines 2 through 11 deal with the character mapping logic while lines 13 through 25 handle the validation.

For the character mapping, we simply iterate through the string and increment the count for that character in the map. We also convert all of the characters to lowercase on line 3 and ignore spaces with the conditional statement on line 8.

The validation section begins with a bit of state. We store whether or not we’ve found a character with an odd frequency so that if we find another odd frequency occurrence later, we know that this string has failed the test. We check if the character count is odd on line 18 and we check if we’ve already found an odd occurrence on line 19.

Conclusion

I always like to say that the coding part of algorithm problems is trivial. The hard part is building your mental model. In this case, the key was to use some additional memory to create a mapping that you can then reference later. Creating maps to organize data is a common pattern in algorithm problems, so having seen this at least once now, you’ll have this tool in your toolbelt for when it counts at your interview. Best of luck!