Code Tests – Alphanumeric Filter Sort Problem

Feb 13, 2020 | , , , , , , | Programming | 0 comments

Here is another post about a recent code test that I also struggled with. This was a timed take home test in which I had 60 minutes to solve this problem. I was unsuccessful in completing this test in the time frame in part due to some issues I had getting used to the online editor that was used for the test. Note to self for next time, I will try and familiarize myself with the editor provided before starting the actual test! Even so, the day after I took the test, I returned to the problem statement to solve it in my own development environment and am providing what I’ve come up with here in this blog post. I chose to take the test in JavaScript and have also implemented my full solution here in this post in JavaScript.

The Problem Statement

1 – Find all the values that exist in two separate strings.

2 – Order those values ascending numbers then letters (a-z)

3 – Print the final filtered, sorted values in a manner like the following ‘1 2 23 A B’

Example Input:

first string = ‘Z 1 3 B J C 2 11 X A -1’ and second string = ‘Z J X 11 G M 9 3 -1 C N R 2 A’

Example Output:

-1 2 3 11 A C J X Z

I assumed that no symbols or other languages besides English would be used.

I assumed that there wold be no duplicate values in the two inputs.

Logical Solution

First we need to find all values from the first string that also exist in the second. This results is a list of each value that exists in both strings. Then it seemed the simplest to sort the numbers first and then the letters. Combine them. And print them with spaces between.

Programming Solution

1 – Remove the spaces from each string.

2 – Create a list of items found in both strings.

3 – Sort the numbers in their own list.

4 – Sort the letters in their own list.

5 – Combine the numbers and letters into the same list.

6 – Convert the combined list into a space separated string.

Here is my code for each step:

The following is the main function of my code that orchestrates the execution of the script. The input strings are initialized as constants called first and second and passed to the main function for processing. I utilized the split() function to strip the spaces and create arrays with only the alphanumeric values from the input strings. I have also initialized the variable matching items as an empty array to be populated with the values that are found in both strings.

const first = 'Z 1 3 B J C 2 11 X A -1';
const second = 'Z J X 11 G M 9 3 -1 C N R 2 A';
/**
 * Main Function that orchestrates the execution of the code
 */
(function main(a, b){
    let first = a.split(' ');
    let second = b.split(' ');
    let matchingItems = [];
    collectMatchingItems(first, second, matchingItems);
    let sortedList = sortList(matchingItems);
    console.log(convertToSpaceDelimitedString(sortedList));
})(first, second);

The following function collectMatchingItems() is called to add all items to the matchingItems array that exist in both strings. The matchingItems array is passed by reference.

/**
 * Adds each item in the first list that is also in the second list to the matching * items list.
 *
 * @param {string[]} first
 * @param {string[]} second
 * @param {string[]} matchingItems
 */
function collectMatchingItems(first, second, matchingItems){
    for(let i = 0; i<first.length; i++){
        aChar = first[i];
        let found = second.indexOf(aChar, 0);
        if(found !== -1){
            matchingItems.push(aChar);
        }
    }
}

Then the following function sortList() was used to sort the unique values by numbers and then by letters in ascending order. This was done using two functions sortNumbers() and sortLetters() each taking advantage of a different use of the JavaScript sort() function. Prior to actually sorting the values, the separate lists were created using populateLists(), one for letters and one for numbers. This made the sorting easier given that the strings contain alphanumeric values. The populateLists() function used a custom utility function I wrote called isLetter() to determine of we were dealing with a letter or a number and thus which list the value should be stored in. Check out the “How to check if character is a letter in Javascript?” post on stack overflow for more details on isLetter(). The two lists were then sorted independent of each other after which they were combined using the JavaScript spread operator.

/**
 * Sorts the raw list of unique values ascending by number first then
 * letters.
 *
 * @param {string[]} aList
 */
function sortList(aList){
    let numbersList = [];
    let lettersList = [];
    populateLists(aList, numbersList, lettersList);
    sortNumbers(numbersList);
    sortLetters(lettersList);
    let combinedLists = [...numbersList, ...lettersList];
    return combinedLists;
}
/**
 * Used to populate the number and letter lists from the main list
 * @param {string[]} aList
 * @param {string[]} numbersList
 * @param {string[]} lettersList
 */
function populateLists(aList, numbersList, lettersList){
    aList.forEach(anItem => {
        isLetter(anItem) ? lettersList.push(anItem) : numbersList.push(anItem);
    });
}
/**
 * Checks to see of a character is a letter or a number.  If it is a letter then
 * the uppercase and lowercase values will not be equal whereas for numbers they will.
 * In this case if it's not a letter then it is a number as symbols are not a part
 * of the possible values to be evaluated.
 *
 * @param {String} value
 * @returns boolean
 */
function isLetter(value){
    return value.toLowerCase() !== value.toUpperCase();
}
/**
 * Sorts a list of letters in ascending order
 *
 * @param {string[]} lettersList
 * @returns string[]
 */
function sortLetters(lettersList){
    lettersList.sort();
}

The sortLetters() function worked just fine using the default .sort() algorithm but the numbers were a different story as they were not sorted naturally (treating 2 digit numbers as single digits for the sort) but instead alphanumerically which resulted in a sort order of something like 1 11 2 3 33 4 where what we actually want is 1 2 3 4 11 33. In order to achieve this natural sort order I implemented my own callback to accomplish this based on the “Javascript sorting of multiple digit numbers” stack overflow post. In this callback, first I converted the value from a string to an int. Then I returned the value of subtracting ‘b’ from ‘a’. If they are the same than it would return zero and leave them as is. If ‘a’ is greater than ‘b’ the return value would be greater than zero and position ‘b’ to a lower index than ‘a’. If ‘a’ is less than ‘b’, the return value would be negative (less than 0) and position ‘a’ to a higher index than ‘b’.

/**
 * Sorts a list of numbers in natural ascending order
 *
 * @param {string[]} numbersList
 * @returns string[]
 */
function sortNumbers(numbersList){
    numbersList.sort((a,b) => {
        let intA = parseInt(a);
        let intB = parseInt(b);
        return intA - intB;
    });
}

The final step was to format the output with spaces between the values. This was done using the convertToSpaceDelimtedString() function as shown here.

/**
 * Builds a string of the elements in the array delimited by a space
 *
 * @param {string[]} aList
 * @returns string
 */
function convertToSpaceDelimitedString(aList){
    let output = '';
    for(let i=0; i<aList.length; i++){
        let anItem = aList[i];
        if(i === aList.length -1){
            output += anItem;
        }else {
            output += anItem + ' ';
        }
    }
    return output;
}

Result

code test 2 output

Conclusion

This solution was a little more challenging for me to solve than the Airplane Itinerary Problem mainly because of the need to figure out the sorting logic for the numbers. My background is CIS and not CS and I have never really needed to do a lot of algorithms/sorting/etc… kind of coding. Therefore, this problem presented a fun challenge and I enjoyed learning in more detail how sorting works in JavaScript’s array sort() function.

I started trying to solve this from where I left off in the live test. It took me a little over 47 min to solve this and another 25 min to refactor my code to what you see in this post. I have posted this solution to GitHub. You can find it in the getInBothOrdered.js file at the following link (https://github.com/bradnjones/codeTests). If you want to run my code grab it from GitHub, be sure to have Node.js installed and then type node getInBothOrdered.js from the command line and you should see the same results as the above screenshot.

Updated on 02/16/2020 – I updated my code to only look through one string and find the values rather than iterate through both. This is a better solution and makes much more sense. You can see the progression from the old to the new in the GitHub repo if you’re interested. A scenario that I may also look at is handling strings that both have more then one occurrence of the same value.

0 Comments

Submit a Comment

Your email address will not be published. Required fields are marked *