Algorithms in JavaScript: Fibonacci, Floodfill, FizzBuzz.

Algorithms in JavaScript: Part 1

In this first part of the Algorithms in JavaScript series, we are going to look at the algorithms for Fibonacci, Floodfill and FizzBuzz, pretty easy and often asked during coding interviews for Front-end positions and Software Engineering positions in general.

Fibonacci

The Fibonacci algorithm aims to create a Fibonacci series of a given length. A Fibonacci series is a series of numbers in which each number is equal to the sum of the two preceding numbers of the series (0, 1, 1, 2, 3, 5, 8, 13, 21, ...). Let's look at the recursive implementation!

function getFibonacciSeries(lenght) {
  
  const result = [];
  
  function getFibonacciNumber(index) {
    if (index === 0) {
      return 0;
    }
    if (index === 1) {
      return 1;
    }
    return getFibonacciNumber(index-1) + getFibonacciNumber(index-2);
  }
  
  for(let i=0; i<lenght; i++) {
    result.push(getFibonacciNumber(i));
  }
  return result;

}

console.log(getFibonacciSeries(8)); //[ 0, 1, 1, 2, 3, 5, 8, 13 ]

That implementation has a pitfall though, in fact in its recursive way to the result it re-calculates the results that were already been calculated, wasting CPU time. Caching (memoizing) those values would speed up the function and allow to create much bigger series without incurring in memory or overflow errors. That's critical: as a practical example on my machine (a MacBook Pro) if I run that function trying to get a series for example of 1000 elements, the memoized function executes in less than a second, while the non-memoized function hangs for minutes eventually throwing an error. So let's look at this memoized version, which is really easy to implement, it takes just a couple of little changes.

function getFibonacciSeriesMemoized(lenght) {
    
  const result = [];
  const memoization = [];
  
  function getFibonacciNumber(index) {
    if (index === 0) {
      return 0;
    }
    if (index === 1) {
      return 1;
    }     
    if (!memoization[index]) {
      memoization[index] = getFibonacciNumber(index-1) + getFibonacciNumber(index-2)
    }
    return memoization[index];
  }
  
  for(let i=0; i<lenght; i++) {
    result.push(getFibonacciNumber(i));
  }
  return result;

}

console.log(getFibonacciSeriesMemoized(8)); //[ 0, 1, 1, 2, 3, 5, 8, 13 ]

Floodfill

The Floodfill algorithm usually needs three parameters to work: a start node, a target color, and a replacement color. In this version we will work with just two: a start node and a replacement color, we will get the target color from the start node and store it using a closure. The algorithm looks for all the nodes that are connected to the start node by a path of the target color and changes them to the replacement color. Let's see how we can implement that in JavaScript.

First of all let's try to imagine and sketch (using TypeScript) the interface of the node that we will be using for this example:

  export interface INode {
    top: INode | null;
    bottom: INode | null;
    left: INode | null;
    right: INode | null;
    color: string;
  }

And now to the Floodfill implementation!

  function floodFill(startNode, replacementColor) {
    
    if (!startNode) {
        return false;
    }

    const initialColor = startNode.color;

    if (replacementColor === initialColor) {
        return false;
    }

    function checkAndOverrideColor(targetNode) {

        if (!targetNode) {
            return false;
        }
    
        if (targetNode.color === initialColor) {
            targetNode.color = replacementColor;
            checkAndOverrideColor(targetNode.top, replacementColor);
            checkAndOverrideColor(targetNode.bottom, replacementColor);
            checkAndOverrideColor(targetNode.left, replacementColor);
            checkAndOverrideColor(targetNode.right, replacementColor);
        }
    }

    checkAndOverrideColor(startNode);

}

FizzBuzz

FizzBuzz is an extremely easy and trivial task that can be asked during code interviews as an early entry-level barrier to exclude from the interview people who have nothing to do with developing software. Every developer should be able to solve it really easily, but for some reason in the web it seems that many aren't able to (one explanation is that many people apply for positions totally out of their circle of competence or background). This simple algorithm is about replacing in a given array of numbers any number divisible by three with the word "Fizz", and any number divisible by five with the word "Buzz". Numbers divisible by both three and five become "FizzBuzz".

function fizzBuzz(input) {
    
  if (!input || !Array.isArray(input)) {
      return false;
  }

  return input.map(element => {
      let result = '';
      if (!(element % 3)) {
          result = "Fizz";
      }
      if (!(element % 5)) {
          result += "Buzz";
      }
      return result || element;
  })
  
}

console.log(fizzBuzz([1, 3, 15, 30, 10, 11, -5, -15, -3, -4])); //[1, 'Fizz', 'FizzBuzz', 'FizzBuzz', 'Buzz', 11, 'Buzz', 'FizzBuzz', 'Fizz', -4]

For updates, insights or suggestions, feel free to post a comment below!