DEV Community

loading...
Cover image for Breaking Down JavaScript Solutions To Common Algorithmic Questions (Part 1)

Breaking Down JavaScript Solutions To Common Algorithmic Questions (Part 1)

emmabostian profile image Emma Bostian ✨ ・5 min read

Have you ever struggled to develop an algorithm solution on a technical interview? In this short tutorial, we'll break down three top algorithm coding questions, starting with the brute force method (step-by-step but not necessarily performant) and transitioning to a more optimized, elegant solution.

If you find another solution, feel free to post it in the comments!

Reverse a string

Task
Given a string, return the reverse of it.

Solution 1
We can use the string.substring() method to take each letter of the str parameter, and append it to a new string. The substring method takes one required parameter and one optional parameter.

The first parameter is the index from which you want the substring to start. This is inclusive meaning if you write myString.substring(1), the output will include the first character.

The second (optional) parameter is the ending index. This parameter is not inclusive. This means that your substring will include all characters until this index plus every remaining character to the right of that index.

Another string method we could use in the brute force method would be the string.charAt() method. The charAt method takes one parameter: the index of the character you want to return.

Let's write two brute-force algorithms for returning the reverse of a string.

// Method 1: Substring
function reverseString(str) {
    let reversedString = '';

   /* Loop through this process for each character in the str parameter
    In order to get the reverse, we'll initialize i to str.length
    Add each character, starting from the end, to the new string.
   */
    for (let i = str.length; i > 0; i--) {
        reversedString += str.substring(i, i-1);
    }
    return reversedString;
}

// Method 2: CharAt
function reverseString(str) {
    let reversedString = '';

   /* Loop through this process for each character in the str parameter
    In order to get the reverse, we'll initialize i to str.length - 1
    while i is greater than or equal to 0.
    Add each character, starting from the end, to the new string.

   */
    for (let i = str.length-1; i >= 0; i--) {
        reversedString += str.charAt(i);

    }
    return reversedString;
}

Solution 2
One of the quickest inline ways to solve this problem is to split each character in the string into an array index, reverse the items within the array, and turn the items in each index into a concatenated string.

We'll use the following methods:

  • string.split() method which splits each character into an array index.
  • array.reverse() method which reverses an array in place.
  • array.join() method which concatenates all array values into a string.

You can chain these three functions together for an elegant, inline solution.

function reverseString(str) {
  return str.split('').reverse().join('');
}

Longest Word

Task
Return the length of the longest word in the provided sentence.

Solution 1
For the first attempt, you can use the string.split(' ') method to break the individual words within a sentence into array indeces. This tutorial will not account for punctuation, however you could solve for this with a regular expression.

Next, we can iterate through each index of the array and count the number of letters in each word. We can keep track of the longest word value in a variable. If the current word value is larger than the maximum word value currently saved, replace it! Then, just return the variable containing the longest word.

You can loop through the array using a for-loop or the array.forEach() method. I prefer the latter, but I've included both below.

// Solution with for-loop
function findLongestWordLength(str) {
  let maxVal = 0;

  const wordArr = str.split(' ');

  for(let i = 0; i < wordArr.length; i++) {
      let word = wordArr[i];
      if (word.length > maxVal) {
          maxVal = word.length;
      }
  }
  return maxVal;
}

// Solution with array.forEach method
function findLongestWordLength(str) {
  let maxVal = 0;

  const wordArr = str.split(' ');

  wordArr.forEach(word => {
      if (word.length > maxVal) {
          maxVal = word.length;
      }
  });
  return maxVal;
}

Solution 2
To optimize this solution, we will still use the string.split() method to separate each word into an array index.

Next, we're going to use the array.map() method to carry out some type of expression on the value within each array index. This will return a completely new array, so we'll save that to a new variable.

For each item in the array, return the length of the string and save it in a new array called arrOfLengths.

Finally, we can use the Math.max(...spreadOperator) method with a spread operator in order to return the integer value for the longest string in a sentence.

function findLongestWordLength(str) {
  const arrOfWords = str.split(' ');
  const arrOfLengths = arrOfWords.map(item => item.length);

  return Math.max(...arrOfLengths);
}

Array Of Largest Sub-Array Values

Task
Return an array consisting of the largest number from each provided sub-array. For simplicity, the provided array will contain exactly 4 sub-arrays.

[1,2,3,4]
[5,18,0,12]
[3,5,12,5]
[28,9,2,34]

Should return => [4,18,12,34]

Solution 1
For the first pass through, we can start with a nested for-loop.

For each item in the outer array, go through its sub array and find the largest value, then push that into a new array.

// For loop
function largestOfFour(arr) {
  let arrayOfMaxValues = [];
  for (let i = 0; i < arr.length; i++) {
      let subArr = arr[i];
      let maxSubArrVal = 0;
      for (let j = 0; j < subArr.length; j++) {
          let currentValue = subArr[j];
          if (currentValue > maxSubArrVal) {
            maxSubArrVal = currentValue;
          }
      }
      arrayOfMaxValues.push(maxSubArrVal);
  }
  return  arrayOfMaxValues;
}

// For each method
function largestOfFour(arr) {
  let arrayOfMaxValues = [];
  arr.forEach(subArr => {
     let maxSubArrVal = 0;
     subArr.forEach(item => {
        if (item > maxSubArrVal) {
            maxSubArrVal = item;
        }
     });
     arrayOfMaxValues.push(maxSubArrVal);
  });
  return  arrayOfMaxValues;
}

Solution 2
We can use the Math.max(...spreadOperator) method with the array.map() method to loop over each item in the outer array, return the max value from within the sub-array, and return that newly created array directly.

function largestOfFour(arr) {
  return arr.map(subArr => Math.max(...subArr));
}

I plan to turn this into a series of posts, so if you enjoyed it make sure to follow me for updates!

Discussion (23)

pic
Editor guide
Collapse
worsnupd profile image
Daniel Worsnup

Love this post!! My only criticism would be that the code transitions between each brute force solution and each optimized solution are not improvements in algorithmic complexity (Big O) but are readability improvements from using standard library functions. I still think it's cool to showcase how knowledge of available standard library methods can clean up solutions tremendously!

Collapse
emmabostian profile image
Emma Bostian ✨ Author

Well.. some of them are optimized for better Big O run times, but not all

Collapse
worsnupd profile image
Daniel Worsnup • Edited

Unless I'm mistaken (please correct me if I'm wrong), the complexity is O(N) for all 6 solutions, where N is the number of letters in the reversed string, the number of letters in the sentence (because of String#split), and the total number of elements in all the arrays. I definitely apologize for being nitpicky here, but my concern is that newer developers will read this and misunderstand what you mean by "optimize" the solution. In this case you're optimizing readability, which is great, but the algorithmic complexity is unchanged.

Thread Thread
emmabostian profile image
Emma Bostian ✨ Author

I’m not positive how Math.max works and if the last example functions as a double nested loop. The last example wouldn’t necessarily be O(n) as input size grew and varied (but I’m not sure as to specifics). So the first 2 I believe are O(n) while the last one is probably O(n) given that the sub arrays have a finite set of elements, but for growing and variable input could creep up to O(2) But agreed I should change the wording from optimized.

Thread Thread
worsnupd profile image
Daniel Worsnup

Ahh I understand the confusion now. The last example is definitely tricky because it's easy to read it as one loop. In actuality, Math.max has to iterate over the full argument list in order to produce the maximum, making the last example O(N) if you consider N to be the total number of elements across all of the arrays. You could also say the last example is O(N * M) where N is the number of arrays and M is the number of elements in each array, but this assumes that each array has the same length, which may not be the case.

Collapse
detunized profile image
Dmitry Yakimenko

A great demonstration for beginners, but the terms "brute force" and "optimized" are quite misleading.

Brute force usually means exhaustive search, for example in password cracking, where all the possible combinations of letters are tried. Better term would be "naive".

Optimized usually means faster, better than naive simple method. In these examples no optimized solution is faster than the "brute force". It's still the same asymptotic complexity, but usually more operations, so normally it'd be slower. It's optimized for code size, I give you that.

Actually, all those "ugly", C style version for for loops and nester for loops usually perform better than their functional equivalents, because they usually allocate less memory to store temporaries. For example:

const arrOfLengths = arrOfWords.map(item => item.length);

creates an array to store lengths of words. This could be avoided by calculating the maximum on the fly, like in the "brute force" solution. Imagine a situation where you only have memory to store the original list of words, say it's 2GB long. It's still O(n), but requires double the memory.

Collapse
parshirahul profile image
Rahul Parshi

yes correct! Also in the interviews they(recruiters) would expect us to write the code without using in built methods.

Collapse
parshirahul profile image
Rahul Parshi

but while working in a software company we should use the in built methods for code readability.

Collapse
qm3ster profile image
Mihail Malo

they would expect us to write the code without using in built methods

They would? Since when? Where?

Thread Thread
parshirahul profile image
Rahul Parshi

In most of the top companies the interviewers will ask us to write the code without using any in build methods.

Thread Thread
qm3ster profile image
Mihail Malo

I guess I understand :/

Collapse
oddvalue profile image
oddvalue

Great post! I particularly like the use of Math.max and spread operator.

For returning the length of the longest word I think a single reduce would be slightly quicker than a map followed by a Math.max.

e.g.

string.split(' ').reduce((longest, item) => Math.max(longest, item.length), 0)
Collapse
detunized profile image
Collapse
0x450x6c profile image
El Azimov
function reverse(str) {
  return _reverse(str.matchAll(/./gu));
}

function _reverse(lettersIter) {
  const { value, done } = lettersIter.next();
  if (done) {
    return '';
  }

  return _reverse(lettersIter) + value[0];
}

image


function findLongestWordLength(str) {
  const wordsIter = str.matchAll(/[^ ]+/gu);

  return _findLongestWordLength(wordsIter);
}

function _findLongestWordLength(wordsIter) {
  const { value, done } = wordsIter.next();

  if (done) {
    return 0;
  }

  return Math.max(value[0].match(/./gu).length, _findLongestWordLength(wordsIter));
}

image

function largest(arr) {
  return arr.map(it => maximum(it[Symbol.iterator]()));
}

function max(a, b) {
   return a >= b ? a : b;
}

function maximum(iter) {
   const { value, done } = iter.next();
   if (done) {
     return 0;
   }

   return max(value, maximum(iter));
}

image

Collapse
anders profile image
Anders

Nice work. Would love to see actual performance of each method as well though : )

Collapse
qm3ster profile image
Mihail Malo

I'd use this for Longest Word. It's one less iteration, and can be easily modified to return the word.

function findLongestWordLength(str) {
  const arrOfWords = str.split(/\s+/)
  const longestWord = arrOfWords.reduce((a, b) => b.length > a.length ? b : a)
  return longestWord
}
Collapse
maxwell_dev profile image
Max Antonucci

I've never thought of the trick used in the last two optimized solutions, using Math with a spread operator. Will definitely look into those more!

Collapse
emmabostian profile image
Emma Bostian ✨ Author

Way better than using Math.max.apply!

Collapse
zerquix18 profile image
I'm Luis! \^-^/

Sweet and elegant!

Collapse
nageshwaruideveloper profile image
Nageshwar Reddy Pandem

thank you, good article... can you add more problems like these and also can you add javascriptarray problems which can be solved with javascript algorithms?

Collapse
parshirahul profile image
Rahul Parshi

what is the time complexity of array.length in Javascript

Collapse
buet17 profile image
buet17

I am cat dad

Collapse
buet17 profile image