Forem: Steven Frasica

Algorithms: Product Sum from an Array

Steven Frasica — Fri, 27 Nov 2020 14:59:53 +0000

We'll be working on a problem today in which we get the product sum from an array that contains integers and other arrays also containing integers. This problem helped me understand recursion more, and hopefully it does the same for you.

Problem

This problem came from AlgoExpert.

We're tasked with writing a function that takes in a "special" array and returns the product sum.

The special array is non-empty and contains integers or other arrays. We can get the product sum of an array by adding all of its elements together and then multiplying by the level of depth of the array.

The depth is determined by how nested the array is.
Ex. The depth of [] is 1. The depth of the inner array in [[]] is 2. The depth of the innermost array in [[[]]] is 3.

In an array, [x, y], the product sum is (x + y). In array [x, [y, z]], the product sum is x + 2 * (y + z). In array [x, [y, [z]]], the product sum is x + 2 * (y + 3z).

Example Input:

[5, 2 [-7, 1], 3, [6, [-13, 8], 4]]

Example Output:

12

calculation:

5 + 2 + 2 * (7 - 1) + 3 + 2 * (6 + 3 * (-13 * 8) + 4)

Approach

We'll initialize a variable sum to keep track of our total sum as we add together integers in the array or in the nested arrays.

A for loop will be used to iterate through our main array to do work on each element. Our array's elements will consist of integers or arrays containing integers or arrays as well. That means we need to do different things whether we encounter arrays or integers while we loop.

When we encounter integers, we'll want to multiply those integers by the depth, and add it to the sum.

When we encounter an element that is an array, we want to recursively call the productSum function on that array, passing in that array and a multiplier increased by 1 as arguments. The reason we increase the multiplier by 1 is because if we encounter an array, that means it is nested, and is one level deeper than the previous array. This recursive call allows us to drill down into the nested arrays and access their integers to then multiply by the level of depth and add it to the total sum.

Solution

We have our given function with a default value of 1 for multiplier, which will increase as we access more nested arrays. We'll be returning sum as our final answer, but initially set it to 0.

function productSum(array, multiplier = 1) {
  let sum = 0;
}

We write out our for loop to iterate through an array. We'll put code in the loop to run depending on whether we encounter an array or an integer.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
  //do some work here
  }
}

We use the Array.isArray() function to determine if the element is an array. It'll return true if it's an array, false if otherwise.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(array)) {

   }
  }
}

If our conditional returns true, we call the productSum function on our current element which is an array, pass in the element and the multiplier increased by 1, since the array is nested a level deeper. We also multiply the entire product sum by the multiplier to account for the depth. We add it to our total sum.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(element)) {
     sum += productSum(element, multiplier + 1) * multiplier
   }
  }
}

Otherwise, we multiply the current element by the level of depth its array is in and add it to the total sum.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(element)) {
     sum += productSum(element, multiplier + 1) * multiplier
   } else {
     sum += element * multiplier
   }
  }
}

Lastly, we make sure to return our total sum outside of the for loop.

function productSum(array, multiplier = 1) {
  let sum = 0;
  for (let element of array) {
   if (Array.isArray(element)) {
     sum += productSum(element, multiplier + 1) * multiplier
   } else {
     sum += element * multiplier
   }
  }
  return sum;
}

Resources

-AlgoExpert

Algorithms: Depth-first Search

Steven Frasica — Fri, 20 Nov 2020 16:17:36 +0000

The depth-first search problem was great practice involving a tree. My initial attempts at the solution were iterating through in essentially a breadth-first search way, but after working through it, I managed to figure out how to use recursion in order to drill all the way down one branch before moving to a sibling node.

Here is a quick definition of depth-first search.

Problem

We're given a Node class with a name and an array of optional children nodes. The nodes form a tree structure.

We're tasked with implementing the depthFirstSearch function on the Node class, and the function takes in an empty array. The function is supposed to traverse the tree with the Depth-first Search approach, store all of the nodes' names in the array and return the array.

Our tree will look like this:

     A
   / | \
  B  C  D
 / \   / \
E  F  G   H
  / \  \
 I   J  K

With the depth-first search approach, we want to return an array that looks like this:

["A", "B", "E", "F", "I", "J" "C", "D", "G", "K", "H"]

Approach

We want to add all of the nodes' names in one branch to the final array before moving on to the next branch. So first, we start at root node "A", then go to its first child "B", then go to the child of "B", which is "E". Those names are now all in the array. There are no children of "E", so once we complete that branch, we go back up to "B" and check if it has other child nodes. "B" does have another child "F". We add "F" and check if it has children, and it does. We add its child "I", check if it has children, and it does not. We go back up to "F" and add its child "J" to the array. "J" does not have children so we go back up to "F", which has no more children, go back up to "B" which has no more children, so we're back at "A". We repeat the process with "C", and then "D".

We'll be using a for loop and a recursive approach to solve this problem.

The way I approached it was by keeping track of a currentNode throughout the function. First step is to add the currentNode's name to the array. Then we loop through the children of the currentNode, and we recursively call the depthFirstSearch function again on any child nodes of the currentNode. This is how we drill down the same branch and add all the children on one branch to the array before moving to the next sibling of the currentNode.

Lastly, we return the array with all of the node names.

Solution
We're working on the function depthFirstSearch within the given Node class. This gives us access to the this keyword, to reference the currentNode instance we are working with.

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

depthFirstSearch(array) {

  }
}

We have access to this, so I saved it to a variable currentNode for easy tracking.

depthFirstSearch(array) {
  let currentNode = this;
}

We push the currentNode's name into the array.

depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
}

Next, we begin our for loop to iterate through our currentNode's children.

depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {

  }
}

This part is key, because our recursion occurs in the for loop.

As we loop through each child, we reassign currentNode to be the currentNode's child. Next step is we call the depthFirstSearch function on that child. This means we go through the function again, but with this child node instead. We add that child node's name to the array, then we enter the for loop and iterate through that child node's children, and repeat the process.

depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {
    currentNode = child;
    currentNode.depthFirstSearch(array);
  }
}

Lastly, we return the array for our answer.

depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {
    currentNode = child;
    currentNode.depthFirstSearch(array);
  }
  return array;
}

Inside the Node class, it looks like this:

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

depthFirstSearch(array) {
  let currentNode = this;
  array.push(currentNode.name);
  for (let child of currentNode.children) {
    currentNode = child;
    currentNode.depthFirstSearch(array);
  }
  return array;
 }
}

Resources

-AlgoExpert

-Stephen Grider's Udemy DS & Algorithms Course

-Wikipedia

Algorithms: Finding the Closest Element in a Binary Search Tree

Steven Frasica — Thu, 12 Nov 2020 16:29:47 +0000

Getting to the topic of binary search trees (bst) in my studies was exciting and intimidating at first, but after repeated practice and working with a friend, I have begun to get a grasp on binary search trees. In this problem, we'll be working through a binary search tree to find the closest element to a given target. Here is a quick definition of a binary search tree.

Problem

We are given a binary search tree and a target, and we are tasked with finding a value in the binary search tree that is closest to value of the given target. In this problem, there will only be one closest value.

Approach

First off, we'll be using an iterative approach to solving this problem. We will need to keep track of the current node we are looking at in the bst, as well as which node's value is closest to our target.

We'll implement a while loop to go through the bst as long as the current node's value is NOT null.

A conditional is going to help us assign a node that is closest in value to the given target, as well as reassign when we find another node even closer in value to the target.

We'll use two conditionals to determine if we move to the current node's left child node or the right child node, dependent upon the target's value relative to the current node.

Our final answer will be the node value closest to the target value.

Solution

We set up our main function that takes in two arguments, a binary search tree and target value.

function findClosestValueInBst(tree, target) {

}

A helper function is going to be useful here, so the focus will be on it for now, returning to the main function at the end. An important thing to note is that we added a third parameter, closest, which will be the node with the value closest to the target value. We also assign a variable currentNode equal to tree to keep track of where we are in the bst.

We will build out the helper function outside of the main function, but then return it in our main function. When the helper fn is in the main function, note that the third argument is tree.value, because we will use that as our initial closest value to the target value.

function findClosestValueInBst(tree, target) {
  return helperToFindClosestValue(tree, target, tree.value)
}


function helperToFindClosestValue(tree, target, closest) {
  let currentNode = tree;
}

Implement a while loop so we continue going through our tree as long as a node is there, so while it is NOT equal to null.

function helperToFindClosestValue(tree, target, closest) {
  let currentNode = tree;

  while (currentNode !== null) {
   //work will go here
  }
}

Next step is very important because we are reassigning what the closest value is to the target. We do this by comparing the absolute value of the difference between the target and the closest value against the absolute value of the difference between the target and current node value we are looking at.

If the absolute value of the difference between the target and current node value is smaller than the absolute value of the difference between the target and the closest value, then we reassign closest to the current node value. Hopefully the code is clearer than that explanation.

function helperToFindClosestValue(tree, target, closest) {
  let currentNode = tree;

  while (currentNode !== null) {
    if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
      closest = currentNode.value;
   }
  }
}

That takes care of keeping track of the closest value.
Next, we work on two conditionals to help us navigate the bst, going either left or right down the tree.

If our target is greater than the current node's value, then we navigate down the right child node's side because anything on the left will be less than the current node's value, meaning the absolute value difference will be farther from our target value.

If our target is less than the current node's value, then we navigate down the left child node's side because anything on the right will be greater than the current node's value, meaning the absolute value difference will be farther from our target value.

function helperToFindClosestValue(tree, target, closest) {
  let currentNode = tree;

  while (currentNode !== null) {
    if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
     closest = currentNode.value;
    }
   if (target > currentNode.value) {
     currentNode = currentNode.right;
   } else if (target < currentNode.value) {
       currentNode = currentNode.left
    }
  }
}

Almost there, next we consider the case where the target is actually equal to the value of the current node. If that's the case, we break out of the loop and return the closest value.

function helperToFindClosestValue(tree, target, closest) {
  let currentNode = tree;

  while (currentNode !== null) {
    if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
     closest = currentNode.value;
   }
   if (target > currentNode.value) {
     currentNode = currentNode.right;
   } else if (target < currentNode.value) {
       currentNode = currentNode.left
   } else {
      break;
   }
  }
  return closest;
}

All together, it looks like this:

function findClosestValueInBst(tree, target) {
  return helperToFindClosestValue(tree, target, tree.value)
}

function helperToFindClosestValue(tree, target, closest) {
  let currentNode = tree;

  while (currentNode !== null) {
    if (Math.abs(currentNode.value - target) < Math.abs(closest - target)){
     closest = currentNode.value;
    }
    if (target > currentNode.value) {
     currentNode = currentNode.right;
    } else if (target < currentNode.value) {
       currentNode = currentNode.left
    } else {
      break;
    }
  }
  return closest;
}

Resources

-AlgoExpert

-InterviewCake

-Stephen Grider's Algo & DS course

-Geeksforgeeks

Algorithm Practice: Checking for a Subsequence

Steven Frasica — Tue, 03 Nov 2020 03:52:06 +0000

In this problem, we're given an array and a sequence (also an array), and we are checking if the sequence is a subsequence of the array. An array is a subsequence of the original array if it is made up entirely of elements from the original array and if the elements are still in the same order. An array is still a subsequence if it contains all of the element of the original array, without any deletions or changes in the order of the elements.

Problem

Given an array and a sequence (which is another array), check if the sequence is in fact a subsequence of the array. Return true if it's a subsequence, and false if not.

A subsequence of an array is a new array which is formed from the original array by deleting some (or none) of the characters without changing the order of the elements in the array.

Ex. [3, 7, 4, 9] is a subsequence of [1, 3, 2, 7, 8, 4, 5, 9]

Notice how integers in the larger array are in the same order as in the subsequence, even though they are not necessarily right next to each other in the larger array.

Ex. [6, 8, 9] is not a subsequence of [1, 3, 2, 7, 8, 4, 5, 9] because the larger array does not contain 6.

Approach

We will use a while loop to iterate through the entirety of the original array, checking for the integers in the given sequence. We initialize pointers for both the array and sequence, increasing each pointer by 1 as we loop. The while loop will continue executing as long as the pointer for the array is less than the length of the array, AND as long as the pointer for the sequence is less than the length of the sequence. These pointers will keep track of our positions in the array and sequence. The pointer for the sequence will increase only if there is a match, that is the current element we are looking at in the sequence is the same as the element we are looking at in the array. The pointer for the array will increase with each iteration because we have to look through the entire array to find the elements in the sequence in order, since order matters. Our problem asks for a boolean as the answer, so we return true if the sequence pointer value is the same as the length of the sequence itself, meaning it is a true subsequence, and false otherwise.

Solution

Initialize our pointers to keep track of our positions in the array and sequence.

function checkValidSubsequence(array, sequence) {
  let arrayIndex = 0;
  let sequenceIndex = 0;
}

Create a while loop using the conditions mentioned in the approach.

function checkValidSubsequence(array, sequence) {
  let arrayIndex = 0;
  let sequenceIndex = 0;

  while (arrayIndex < array.length && sequenceIndex < sequence.length) {

  }
}

If the element we are currently on in the sequence matches the element in the array, then we increment sequenceIndex by 1.

function checkValidSubsequence(array, sequence) {
  let arrayIndex = 0;
  let sequenceIndex = 0;

  while (arrayIndex < array.length && sequenceIndex < sequence.length) {
    if (sequence[sequenceIndex] === array[arrayIndex]) {
      sequenceIndex++;
    }
  }
}

Inside of the while loop, but outside of the if statement, increase the arrayIndex by 1 so we continue searching through the array.

function checkValidSubsequence(array, sequence) {
  let arrayIndex = 0;
  let sequenceIndex = 0;

  while (arrayIndex < array.length && sequenceIndex < sequence.length) {
    if (sequence[sequenceIndex] === array[arrayIndex]) {
      sequenceIndex++;
    }
    arrayIndex++;
  }
}

Lastly, we set up a boolean expression to return true or false dependent on if we have a subsequence of the given array. If the sequenceIndex is equal to the length of the sequence, we return true, and false otherwise. This is outside of the while loop.

function checkValidSubsequence(array, sequence) {
  let arrayIndex = 0;
  let sequenceIndex = 0;

  while (arrayIndex < array.length && sequenceIndex < sequence.length) {
    if (sequence[sequenceIndex] === array[arrayIndex]) {
      sequenceIndex++;
    }
    arrayIndex++;
  }
  return sequenceIndex === sequence.length;
}

Resources

Algorithm Practice: Sum Two Arrays

Steven Frasica — Thu, 29 Oct 2020 16:56:29 +0000

I collaborated on this problem with a group of friends and it was helpful to get so many different perspectives on the problem as we discussed and approached it. As a result, the solution felt a bit scattered and while it's not the most optimal, the main takeaway was the successful collaboration of four people.

The Problem

Found on Codewars, the problem reads as follows:

"Your task is to create a function called sum_arrays() in Python or addArrays in Javascript, which takes two arrays consisting of integers, and returns the sum of those two arrays.

The twist is that (for example) [3,2,9] does not equal 3 + 2 + 9, it would equal '3' + '2' + '9' converted to an integer for this kata, meaning it would equal 329. The output should be an array of the the sum in a similar fashion to the input (for example, if the sum is 341, you would return [3,4,1]). Examples are given below of what two arrays should return."

Ex.

[3,2,9],[1,2] --> [3,4,1]
[4,7,3],[1,2,3] --> [5,9,6]
[1],[5,7,6] --> [5,7,7]

"If both arrays are empty, return an empty array.

In some cases, there will be an array containing a negative number as the first index in the array. In this case treat the whole number as a negative number. See below:"

[3,2,6,6],[-7,2,2,8] --> [-3,9,6,2] # 3266 + (-7228) = -3962

Approach

There are a couple of cases initially considered, such as if both arrays given are empty, then we want to return an empty array. If there is only one empty array, then we simply want to return the other array.

Once we consider those cases, when we are actually working with an array containing elements, it seemed simple to change the elements into an integer. First, we join the elements into a string, then use parseInt() to turn the string into an integer. We then want to add those two sets of integers we now have together.

Then we take that sum, and convert it to a single array.
We also declare an empty array that we'll work with a little later.

We'll loop through the single array made up of the sum, and explain that more with the actual coding part.

Since we want our answer to be an array of elements, we'll push the elements from the sum array into our empty array declared earlier, and return that array with the new elements inside.

Solution

Here we account for the cases of having two or one empty arrays.

function addArrays(array1, array2) {
  if(array1.length < 1 && array2.length < 1){
    return []
  }
  else if( array1.length < 1 ){
    return array2
  }
  else if( array2.length < 1){
    return array1
  }

Here we convert each array into an integer and add them together, setting it to the variable sum.

let num1 = parseInt(array1.join(''));
let num2 = parseInt(array2.join(''));
let sum = num1 + num2;

We convert our sum into a single array. We declare an empty array we will use for our final answer.

let strArr = sum.toString().split('')
let newArr = []

We have to check for negative numbers, so we used this conditional to look at the first element in our array. If the element is a negative sign, then we are essentially tacking on that negative sign to the first integer in the array, and then removing the negative sign element.

  if(strArr[0] === '-'){
    strArr[1] = '-'+ strArr[1]
    strArr.shift()
  }

Lastly, we use a for...of loop to iterate through our array and we convert each character of the array into an integer using parseInt() and push the integer into our newArr, which was previously empty.

Make sure to return the newArr which holds the separate integers as elements as the problem requested.

  for(let char of strArr){
    newArr.push(parseInt(char))
  }
  return newArr

}

Resources

-Codewars

-Collaboration with others!

Algorithm Practice: Two Sum

Steven Frasica — Thu, 22 Oct 2020 16:47:15 +0000

This was an interesting problem I worked on, as it helped me get more familiar using a hash table to come up with a more efficient solution than if I had solved it using nested for loops. One of my close friends/mentor worked through it with me, and I owe him a great deal for being patient and providing great insight as I struggled through it initially. I found this problem on leetcode, a helpful site for practicing algorithms.

Problem

"Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order."

Examples:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Approach

We'll create an empty hash table where we'll pass in our key value pairs.

We'll be using a single for loop to iterate through our given array nums and passing in key value pairs into a hash table, which will be the elements (keys) and corresponding indices (values). The problem states that there is only one solution for a given array, so if our hash table contains the two indices corresponding to the elements that make up the target, we can stop there. However, in the worst case scenario, our hash table will contain every single element from the given array nums.

We figure out the difference by subtracting the current element we're looking at from the target and save that to a variable.

Next, we check if that key difference is in our hash table, and if it is, we will return the value of the key difference and the index of the current element we are looking at.

If the key difference is not in our hash table, then we assign the current element as a key in the hash table and its index as a corresponding value and continue looping.

Solution

First, declare an empty object, or hash table.
This is where we will pass in our elements and corresponding indices as key value pairs

var twoSum = function(nums, target) {
  const mapper = {};
}

Next, we create a for loop to iterate through the array nums.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {}

}

Inside the loop, we declare a variable difference, which we get by subtracting the element we're currently looking at in the array, nums[index] from the given target.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {
      let difference = target - nums[index];

  }

}

Next, we check if difference is an existing key in our hash table mapper. If it is, we return mapper[difference] and the current index we are on.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {
       let difference = target - nums[index]; 

        if (difference in mapper) {
            return [mapper[difference], index]
        }

  }
}

Lastly, if our hash table mapper, does not contain the difference, then we assign a new key value pair in the hash table using the current element we're iterating through and its index.

var twoSum = function(nums, target) {
    const mapper = {};
    //this is the hash table

    for (let index = 0; index < nums.length; index++) {
       let difference = target - nums[index]; 

        if (difference in mapper) {
            return [mapper[difference], index]
        } else {
            mapper[nums[index]] = index;
        }
  }
}

This is a more efficient solution, giving us O(n) runtime than using a nested for loop which would have been a runtime of O(n^2). One last thing to remember is that the question is asking us to return the indices of the elements that sum up to target, not the elements themselves.

Algorithms: Find the Vowels

Steven Frasica — Fri, 16 Oct 2020 12:46:22 +0000

In this blog, we'll go over how to find the vowels in a string. This problem provided me with good practice using a for...of loop.

Problem

We are given a string and are asked to create a function that returns the number of vowels contained in the string. If there are no vowels in the string, then the function should return 0. Vowels are the characters 'a', 'e', 'i', 'o', and 'u'.

vowels('hello')
//will return 2

vowels('aardvark')
//will return 3

vowels('rkzlwmlz')
//will return 0

Approach

We know that we can iterate through a string, so a for...of loop would be useful here. As we go through the loop, we will increase a variable named count by 1 for each vowel we encounter in the string. It will not matter if the character is lowercase or not, so we will ensure our function accounts for that. In order to check if the string contains any vowels, we will check the string against an array of vowels.

Solution

function vowels(string) {
  let count = 0;
}

We will increase count every time our loop encounters a vowel in the string.

function vowels(string) {
  let count = 0;
  const vowels = ['a', 'e', 'i', 'o', 'u'];

We use the vowels array to compare against the string.

function vowels(string) {
  let count = 0;
  const vowels = ['a', 'e', 'i', 'o', 'u'];

  for (let char of string.toLowerCase()) {

  }
}

We use a for...of loop to iterate through the string. We use the toLowerCase() method to convert the string to lower case. This ensures that we can correctly match the vowels in the string to the vowels array.

function vowels(string) {
  let count = 0;
  const vowels = ['a', 'e', 'i', 'o', 'u'];

  for (let character of string.toLowerCase()) {
    if (vowels.includes(character)) {
        count++;
      }
  }
}

We use a conditional that says if the current character in the string that we're checking with our loop is included in the vowels array, then increase count by one.

function vowels(string) {
  let count = 0;
  const vowels = ['a', 'e', 'i', 'o', 'u'];

  for (let character of string.toLowerCase()) {
    if (vowels.includes(character)) {
        count++;
      }
  }
  return count;
}

Lastly, we return count since the question asks for the number of times vowels appear in the string.

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake

Algorithm Practice: Fizzbuzz problem

Steven Frasica — Thu, 08 Oct 2020 15:46:32 +0000

The fizzbuzz problem was simply a fun problem to work through. There are clear steps to break down the problem. While I initially had a tendency to try and usually unsuccessfully solve an algorithm problem by jumping into code and not outlining and pseudocoding the problem, tackling fizzbuzz helped me break that habit. I now know to be more patient and break every problem down into smaller parts.

Problem
The problem asks that our function console log or print out every number from 1 to n. We have to print "fizz" instead of the number for every multiple of 3. For every multiple of 5, we have to print "buzz", instead of the number. For numbers that are multiples of BOTH 3 and 5, we have to print "fizzbuzz".

If we call the function fizzBuzz with an argument of 5, it will look something like this:

fizzBuzz(5);
1
2
fizz
4
buzz

Solution

We can use a for loop to iterate through every integer from one to n. Inside the loop, we'll do some work with each integer, which will be console logging it. In cases where the integer is a multiple of 3, 5, or both, we will console log "fizz", "buzz", and "fizzbuzz", respectively. In order for our loop to recognize whether the integer is a multiple of 3, 5, or both, we will utilize conditionals.

To determine if an integer is a multiple of a given number, we can use the modulo % operator. If the result of a modulo operation is 0, then the integer is a multiple of a given number. If the result of a modulo operation is greater than 0, in other words, if there is a remainder, then the integer is not a multiple of the given number.

We'll use the modulo operator in our conditional to determine if we console log a string instead of the integer itself.

We will write out the for loop. In most for loops, the counter i typically starts at 0, but this problem is different. It specifically asks that we print out from 1 to n, meaning we don't need to start our counter at 0. Since we are also printing out n itself, we want to make sure our loop goes until i <= n, inclusive of n.

function fizzBuzz(n) {
  for (let i = 1; i <= n; i++) {
}

Next, we'll write out the first conditional which checks if an integer is a multiple of both 3 and 5. We use the and symbol && to include two conditionals in the if statement.

function fizzBuzz(n) {
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      console.log('fizzbuzz');
    } 
}

Next is the conditional for multiples of only 3, followed by a conditional for multiples of only 5.

function fizzBuzz(n) {
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      console.log('fizzbuzz');
    } else if (i % 3 === 0) {
       console.log('fizz');
    }
}

function fizzBuzz(n) {
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      console.log('fizzbuzz');
    } else if (i % 3 === 0) {
       console.log('fizz');
    } else if (i % 5 === 0) {
       console.log('buzz');
    }
}

Lastly, on the default case, we will simply console log the integer itself. These are all the other numbers that are not multiple of either 3 or 5.

function fizzBuzz(n) {
  for (let i = 1; i <= n; i++) {
    if (i % 3 === 0 && i % 5 === 0) {
      console.log('fizzbuzz');
    } else if (i % 3 === 0) {
       console.log('fizz');
    } else if (i % 5 === 0) {
       console.log('buzz');
    } else {
       console.log(i);
    }
}

It was not until this problem that breaking down into smaller steps became very apparent to me. I hope this helps in your algorithm studies!

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake

Algorithms : Understanding Stacks

Steven Frasica — Thu, 01 Oct 2020 15:35:32 +0000

Stacks are a data type I was excited to learn about, given that I heard the term mentioned many times in my studies, but had not yet devoted much time to understanding. Once I did a couple of problems involving stacks, their implementation became much clearer.

Stack

Stacks are containers that hold individual pieces of data. There are comparisons to make between stacks and queues. One important difference is that in a stack, the first item that goes in, will be the last item that goes out of the stack. An example to understand stacks is a stack of plates. As mentioned, the first item in a stack is the last item out of a stack. When putting dishes away in a cabinet, the first dish is on the bottom and any subsequent dishes go on top of it, in a stack. Once there are a few plates on top of the first dish, it becomes increasingly difficult to remove the bottom or first dish. It is much easier to remove the top or last dish you placed on the stack. We will use an array and array methods to implement a stack and functionality.

Creating a Stack class

We are asked to create a stack data structure with functionality to push or add a record to the stack, pop or remove a record from the stack, and peek to "view" a record in the stack without removing that record.

class Stack {
  constructor() {
    this.data = [];
  }
/* using constructor, we can initialize an array when we create an instance of a stack. The array is a stack property called data.
*/
}

Now we implement the push method to add a record to the stack.

class Stack {
  constructor() {
    this.data = [];
  }

  push() {
  //use array method push and pass in an argument record to push or add into the stack.
  }
}

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
   this.data.push(record);
  }
}

Next method is the pop method to remove the last or most recently added record to the stack.

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
   this.data.push(record);
  }

  pop() {
   return this.data.pop();
  }
  // Include return keyword so we get the removed record from the stack.
}

Lastly, we will implement the peek method which allows us to check if there is a record left in the stack.

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
   this.data.push(record);
  }

  pop() {
   return this.data.pop();
  }

  peek() {
   // return the last record in the stack without removing it
  }
}

Since we are using an array to build out our stack class, we can use bracket notation to read the last item in the array, which actually allows us to read the last record in the stack.

class Stack {
  constructor() {
    this.data = [];
  }

  push(record) {
   this.data.push(record);
  }

  pop() {
   return this.data.pop();
  }

  peek() {
   return this.data[this.data.length - 1];
  }
}

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake

Algorithm Practice: Queues

Steven Frasica — Thu, 01 Oct 2020 14:57:55 +0000

Up until I started learning about queues, most of the algorithm problems I was practicing involved arrays, strings, and objects. That said, being introduced to queues expanded my understanding of different data structures necessary for interview problems and algorithms. It helps that in my initial implementation of queues, I was taught how to use an array to create a class for a queue. Familiarity with arrays made drawing relationships between arrays and queues made understanding queues that much easier.

Queue

A queue holds data in order, and the first instance of data that goes into a queue, is also going to be the first instance of data that goes out of the queue. In Stephen Grider's Udemy course, he uses the acronym "FIFO" or "First in, first out" as an easy way to remember the process. An example that comes to mind is ordering at a sandwich shop. You go in, grab a ticket, and your ticket will be called for you to place your order after the previous tickets are called. It would be unfair if you were able to get your sandwich before the other customers who entered the queue earlier. There is no skipping in a queue. Other examples would be your music playlist (sans shuffle) or your movie streaming service queue. Once your current show or movie is over, the streaming service is already queuing up or preparing the next episode or movie to autoplay.

Implementing a Queue Data Structure

We are asked to create the queue data structure with the functionality to add and remove individual pieces of data from the queue.

We can start with using an array data structure and some array methods to build out the functionality of the queue.

class Queue {
//create an empty array
}

class Queue {
  constructor() {
    this.data = [];
  }
/* data will be an array that is a property of each instance of a queue that is created. 
The "this" keyword refers to the queue instance.
*/
}

Our next step is to create an add method for the Queue class.

class Queue {
  constructor() {
    this.data = [];
  }

  add() {
  /* add will take in an argument of some data, which we can call record. add will take the record and place it into the queue. 
*/
  }
}

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }
}

The unshift array method places a new instance of data in the front of an array. So now whenever we call add with an argument on an instance of a queue, it will add a new record to the queue.

We move on to our remove method.

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
  // Use the array method pop to remove the last record in the array, which will allow us to remove the next record in the queue. 
  }
}

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop(); 
  }
  //remember to include the return keyword so it returns the queue record we just removed. 
}

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake

Algorithm Problem: Capitalize the First Character

Steven Frasica — Tue, 15 Sep 2020 02:57:40 +0000

We'll go over another algorithm problem, where we have to capitalize the first character of each word in a string. This solution we'll go over today made the most sense to me, as a problem is always the most clear to me when it can be broken down into small steps.

Problem

We are given a string and are asked to return the string, with the first letter of each word capitalized.

Ex.

capitalize("capitalize every word");
//Output is -> "Capitalize Every Word"

We have to make sure we only capitalize the first letter of the word, and not the entire word. Remember that we have to return a string too.

Approach

We start off with a string data type, and we know we'll be iterating over the data, so it would be useful to convert the string into an array first. We're using the .split() method to convert the string into an array. We'll be splitting up the string into words, not individual characters, so we have to insert a space ' ' as the argument for the split method. Once we have an array of words, we will loop through the array and change each word by capitalizing its first letter.

In order to capitalize, we will use the .toUpperCase() method on each word's first letter. That only gives us the first letter, now we need the rest of the word and we can use the .slice() method for this step. Once we've capitalized the word and rejoined it, we will use the .push() method to add that word to an empty array. The once empty array will contain all of the newly capitalized words, but we're not done yet. We need to convert the array back into a string, and we'll use the .join() method. Make sure to join by a space ' ', similar to how we split it in the first place.

Solution

First, we create an empty array where we will eventually push all the capitalized words.

capitalize(string) {
  const stringArray = []; 
}

Next, we will loop over an array we got from our string.

capitalize(string) {
  const stringArray = [];

  for (let word of string.split(' ')) {
   //We will do work on the array on this line
  }
}

We will take each word and capitalize the first letter of the word. Next, we'll combine it with the rest of the word that we got using the .slice() method. By only passing in the start index as the argument, .slice() will give us the word from the second character to the end of the word.

capitalize(string) {
  const stringArray = [];

  for (let word of string.split(' ')) {
    word[0].toUpperCase() + word.slice(1)
  }
}

The newly capitalized words need somewhere to live, so we will use the .push() method and get them into our currently empty stringArray.

capitalize(string) {
  const stringArray = [];

  for (let word of string.split(' ')) {
    stringArray.push(word[0].toUpperCase() + word.slice(1))
  }

}

Lastly, since we want a string as our answer, we need to return the stringArray in string form. We use .join() to get our newly capitalized string. Make sure to return it at the end and outside of the for loop.

capitalize(string) {
  const stringArray = [];

  for (let word of string.split(' ')) {
    stringArray.push(word[0].toUpperCase() + word.slice(1))
  }
  return stringArray.join(' ');
}

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake

Solving the Palindrome Algorithm Problem

Steven Frasica — Fri, 11 Sep 2020 13:21:36 +0000

The journey of learning more algorithms continues, and with each problem, I'm gaining more experience with different approaches and patterns. It's always helpful to break down every algorithm into smaller steps to tackle. I think the palindrome problem is a good example of how to reach a solution in small steps.

Problem

We're provided with a string and we have to return true or false depending on whether or not the string is a palindrome. A palindrome is a word or string of letters that spells out the same word when reversed. In this problem, spaces and punctuation marks count as characters in the string too.

Ex.

palindrome("abba") === true
palindrome("abcdefg") === false
palindrome("racecar") === true

Approach

One way to solve this problem would be to convert the string into an array of characters and iterate through it to see if the sequence of characters are a palindrome. Essentially we'll be checking if the first element matches the last element, if the second element matches the second to last element, and so on.

Ex.

Our string is "racecar".
The array would be ['r', 'a', 'c', 'e', 'c', 'a', r']

Iterating through the array and checking pairs of characters as we move inwards from both ends of the array.

['r', 'a', 'c', 'e', 'c', 'a', 'r']

On the last step, both the left and right side will both meet at character 'e', so this is a palindrome.

Solution

function palindrome(string) {

}

//1.
Convert string to an array using the split method. Remember to put '' as the argument in the split method to split the word into individual characters.

function palindrome(string) {
  string.split('')
}

//2.
Use the .every() array method to check whether each character in the string matches up in the aforementioned way to determine if it's a palindrome. .every() will return a boolean based on the condition you pass into .every(). .every() takes in a function with two arguments, character and index.

function palindrome(string) {
  string.split('').every((character, index) => {
  //we will implement the condition here 
  }
}

Our condition is going to be checking pairs of elements starting from the left and right ends of the array and moving in.

function palindrome(string) {
  string.split('').every((character, index) => {
    character === string[string.length - index - 1]
  }
}

Remember to return on both lines to ensure our function outputs the answer we want, in this case a boolean.

function palindrome(string) {
  return string.split('').every((character, index) => {
    return character === string[string.length - index - 1]
  }
}

Let's break down what's inside the brackets after 'string'.
Arrays are zero-indexed so we need to subtract 1 from the string.length to get the last element in the array. Next, we subtract index from the string.length to move inwards to the array and match up with the element on the left side.

The palindrome problem has many approaches, as do all algorithm problems, and this is just one way to solve it. Regardless of what approach you use, it's always helpful to break down every problem to smaller steps. It helps to catch errors early on, and you build out a roadmap to the solution before writing down any code.

Resources

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake