Sort a String using a Custom Alphabet in Javascript

Last week I completed a live coding challenge for a Junior Developer position for a company that I'm very fond of. I have really enjoyed getting to know my interviewer who is a Senior Developer with them. I was quite nervous going into the live code, as all I had ahead of time was the phrase "you’ll be given a short coding exercise that isn’t designed to be tricky or overly complex — we're just interested in how you tackle a problem". I didn't know what language it was going to be in or if it would be in the context of a framework.

However, I would be doing the technical with the same Sr Dev who conducted my initial interview and I felt we got along well and as such, I was comforted by the fact that it wouldn't be a stranger. When the call started my interviewer informed me I could pick the language and where we did the challenge whether that was in a local or browser-based IDE. I picked JavaScript and told him that I had recently used CodeSandbox.io and that would be fine with me since that would give him access to type code as well.

It took us both a little bit of troubleshooting to get it working live, and we joked that that was the first part of the code challenge; "Can you successfully set up a live code sandbox". Once it was rolling, he told me the first part was to return a string so that it is sorted alphabetically. I asked about case sensitivity and he listed the assumptions: all lowercase and no special characters including spaces. I also asked if it was ok that we test the function using console.logs instead of displaying it to the browser. He agreed as that would remove a layer of abstraction.

Having done similar string manipulations prior, I knew I could turn the string into an array with .split(''), use the array method sort() which is a built-in array method that sorts alphabetically and I pulled up the documentation just to make sure that I had the syntax right. Then I could turn that array back into a string with .join(''). The result is as follows:

/*
1. Return a string so that it is sorted alphabetically
assumptions: all lowercase and no special characters
*/

const alphabeticalSort = (str) => {
  let arr = str.split('')
  return arr.sort().join('')
}

console.log(alphabeticalSort("cbsgdafer"))
//abcdefgrs

Note: I did have a nervous moment where my brain tried to call sort directly on the string and I got the error .sort() is not a function. After staring at the documentation I saw that sort is called on an array, and I had an "oh duh" moment and knew I was missing the split('') method.

Once that was working successfully my interviewer threw in a wrinkle:

Now your function takes in a second argument with a custom alphabet. The same assumptions apply, all lowercase and no special characters, the alphabet does not repeat characters and the alphabet is an array.

I mused aloud for a moment about using an object with the keys as the alphabet and the values the number of times the letter appears in the string, then my interviewer asked how I would keep track of the order. I said good point, objects do not necessarily maintain order so let's not go down that path. I mentioned sort has the possibility to be customized because I've used that to sort an array of numbers previously.

However I did not know how to relate that to a custom alphabet so he recommended we look closer at the .sort() documentation. What is important is that you can give .sort() a compare function that defines an alternative sorting order. For example:

let points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return a - b});
//[1, 2, 10, 25, 40, 100]

This works because the function returns a negative, zero, or positive value, depending on the two arguments. When the sort() method compares two values, it sends the values to the compare function and sorts the values according to the returned (negative, zero, positive) value. For example, when comparing 40 and 100, the sort() method calls the compare function(40,100) which calculates 40-100, and returns -60 (a negative value). Because the compare function returned a negative number, the sort function will sort 40 as a value lower than 100.

The W3Schools documentation for sort was incredibly helpful for understanding how the compare function works. Once I understood this, I suggested that if I could find out the index of where the letter was in the custom alphabet then compare it to the index of the next letter in the string and based on if it returned a negative, positive, or zero, have it sort in ascending order. My interviewer agreed and my first instinct was to try,

   let arr = s.split('')
   return arr
     .sort((a,b) => {return alphabet[a] - alphabet[b]})
     .join('')

but that didn't sort how I was expecting and when I checked console.log(alphabet[a]) it returned undefined. I laughed at myself as my interviewer pointed out we can't access indices this way and I told him, my brain really wants me to be using an object. That's how you access a value if I were using an object. So I did the google search "javascript index of array element" and the first result was the MDN Docs Array.prototype.indexOf() and I said that looks like exactly what I need.

/*
2. Now your function takes in a second argument with a custom alphabet.
  same assumptions apply, all lowercase and no special characters, the alphabet does not repeat characters
  also, the alphabet is an array
*/

const alphabeticalSortTwo = (s, alphabet) => {
  let arr = s.split('')
  return arr
    .sort((a,b) => {return alphabet.indexOf(a) - alphabet.indexOf(b)})
    .join('')
}

console.log(alphabeticalSortTwo("abcdebebdca", "badcfeghijklmnopqrstuvwxyz".split('')))

My interviewer then had me test out a few different strings and custom alphabets to ensure it was working as expected, and indeed it was!

He then had some follow-up questions that we discussed.

Why did you use the fat arrow function instead of the function keyword when writing your functions?

I have gotten used to anonymous arrow functions in React because it helps with not having to .bind(this) when accessing or updating state. From there it has really become a habit and a stylistic choice that I prefer.

Why did you use let instead of const?

Looking at it now, I should have used const, because I'm declaring a variable that won't change during its life in the function. So to make it clear to other developers const would have been the better choice.

What would happen if the string I gave it was a million characters long?

The javascript sort function looks at each character once as it sorts it and so it would have an O(n) runtime so if each sorting action was a second, it'd take 1 million seconds to sort the string. It'd be a linear runtime.**

**Note: I was thinking about this response later and I looked it up. According to MDN "The time and space complexity of the sort cannot be guaranteed as it depends on the implementation." Some further investigation I found this StackOverFlow which indicates that it is browser based but in general under the hood it uses a merge sort algorithm and is O(n log n) in the worst-case scenario. I still need to work on my runtime studies!

He then shared with me his solution which looked very similar to mine:

const defaultAlphabet = "abcdefghijklmnopqrstuvwxyz".split("");

function alphabetize(string, alphabet = defaultAlphabet) {
  return string
    .split("")
    .sort((a, b) => alphabet.indexOf(a) - alphabet.indexOf(b))
    .join("");
}
console.log(alphabetize("abcdebebdca", "badcfeghijklmnopqrstuvwxyz".split('')))
//bbbaaddccee
console.log(alphabetize("abcdbdacbddbdbacbd")) //aaabbbbbbcccdddddd

There are a few items that I really like about his solution. The first is that he did not set a variable at all and directly returning the string.split('').sort(...).join(''). The second is that he set a default alphabet which is the normal English alphabet so you can use the same function to sort according to the regular alphabet. Then if you pass in a second optional argument that contains an array of your custom alphabet it will sort according to that custom alphabet.

Overall this was a particularly good live code challenge experience for me, although in hindsight I should have thought some more about the runtime while we were talking about the problem. We finished with time to spare and were able to talk more about the projects that the company has in the works. Some key takeaways for me were that thoroughly reading the documentation can be incredibly helpful and try not to let the anxiety get too ramped up, as that can lead to sloppy mistakes.

Happy coding!