DEV Community

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

Emma Bostian ✨ on February 20, 2019

Have you ever struggled to develop an algorithm solution on a technical interview? In this short tutorial, we'll break down three top algorithm cod...

Read full post

Daniel Worsnup • Feb 20 '19

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!

Emma Bostian ✨ • Feb 20 '19

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

Daniel Worsnup • Feb 20 '19 • 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.

Emma Bostian ✨ • Feb 20 '19

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(²⁾ But agreed I should change the wording from optimized.

Daniel Worsnup • Feb 21 '19

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.

Dmitry Yakimenko • Feb 20 '19

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.

Rahul Parshi • Feb 21 '19

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

Rahul Parshi • Feb 21 '19

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

Mihail Malo • Feb 22 '19

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

They would? Since when? Where?

Rahul Parshi • Feb 24 '19

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

Mihail Malo • Feb 24 '19

I guess I understand :/

oddvalue • Feb 21 '19

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)

Dmitry Yakimenko • Feb 21 '19

For anyone interested I posted an performance analysis and some gotchas of these solutions:

Performance measurement of JavaScript solutions to common algorithmic questions (part 1)

Dmitry Yakimenko

#javascript#performance#profiling

El Azimov • Aug 26 '20

function reverse(str) {
  return _reverse(str.matchAll(/./gu));
}

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

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

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));
}

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));
}

Anders • Feb 20 '19

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

Mihail Malo • Feb 22 '19

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
}

Max Antonucci • Feb 20 '19

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!

Emma Bostian ✨ • Feb 20 '19

Way better than using Math.max.apply!

I'm Luis! \^-^/ • Feb 20 '19

Sweet and elegant!

Nageshwar Reddy Pandem • Feb 17 '20

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?

Rahul Parshi • Feb 21 '19

what is the time complexity of array.length in Javascript

buet17 • Feb 21 '19

I am cat dad

buet17 • Feb 21 '19

Great