DEV Community: Christina

Use Backtracking Algorithm to Solve Sudoku

Christina — Fri, 04 Sep 2020 00:34:36 +0000

As promised in my recent article on how to design an algorithm, I am here to take a closer look at another popular technique for algorithm design called backtracking.

Backtracking is a useful algorithm for solving problems with recursion by building a solution incrementally. Generally speaking, backtracking involves starting with a possible solution and if it doesn't work, you backtrack and try another solution until you find something that works. Backtracking is particularly helpful when solving constraint satisfaction problems such as crosswords, verbal arithmetic, and Sudoku.

In general, backtracking algorithms can be applied to the following three types of problems:

Decision problems to find a feasible solution to a problem
Optimization problems to find the best solution to a problem
Enumeration problems to find a set of feasible solutions to a problem

In this article, I will be demonstrating the backtracking strategy by solving a popular problem known as the Sudoku Solver.

Sudoku Solver

As a Sudoku fan myself, I was excited to dive into this problem. The backtracking algorithm for this problem will try to place each number in each row and column until it is solved. Let's start with the main method:

function sudokuSolver(matrix) {
    if (solveSudoku(matrix) === true) {
        return matrix;
    }
    return 'NO SOLUTION';
}

Now, let's get into the main logic of our algorithm:

const UNASSIGNED = 0;

function solveSudoku(matrix) {
    let row = 0;
    let col = 0;
    let checkBlankSpaces = false;

    /* verify if sudoku is already solved and if not solved,
    get next "blank" space position */ 
    for (row = 0; row < matrix.length; row++) {
        for (col = 0; col < matrix[row].length; col++) {
            if (matrix[row][col] === UNASSIGNED) {
                checkBlankSpaces = true;
                break;
            }
        }
        if (checkBlankSpaces === true) {
            break;
        }
    }
    // no more "blank" spaces means the puzzle is solved
    if (checkBlankSpaces === false) {
        return true;
    }

    // try to fill "blank" space with correct num
    for (let num = 1; num <= 9; num++) {
        /* isSafe checks that num isn't already present 
        in the row, column, or 3x3 box (see below) */ 
        if (isSafe(matrix, row, col, num)) {
            matrix[row][col] = num;

            if (solveSudoku(matrix)) {
                return true;
            }

            /* if num is placed in incorrect position, 
            mark as "blank" again then backtrack with 
            a different num */ 
            matrix[row][col] = UNASSIGNED;
        }
    }
    return false;
}

Next, let's take a closer look at some helper methods:

function isSafe(matrix, row, col, num) {
    return (
        !usedInRow(matrix, row, num) && 
        !usedInCol(matrix, col, num) && 
        !usedInBox(matrix, row - (row % 3), col - (col % 3), num)
    );
}

function usedInRow(matrix, row, num) {
    for (let col = 0; col < matrix.length; col++) {
        if (matrix[row][col] === num) {
            return true;
        }
    }
    return false;
}

function usedInCol(matrix, col, num) {
    for (let row = 0; row < matrix.length; row++) {
        if (matrix[row][col] === num) {
            return true;
        }
    }
    return false;
}

function usedInBox(matrix, boxStartRow, boxStartCol, num) {
    for (let row = 0; row < 3; row++) {
        for (let col = 0; col < 3; col++) {
            if (matrix[row + boxStartRow][col + boxStartCol] === num) {
                return true;
            }
        }
    }
    return false;
}

Lastly, let's put our algorithm to the test:

const sudokuGrid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0], 
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

console.log(sudokuSolver(sudokuGrid));

Here's our sudoku example being solved by backtracking:

Conclusion

I had a lot of fun with this article and hope that you found it helpful for getting a basic understanding of backtracking. Here are some additional resources:

Overview of Backtracking from Wikipedia
Video Explanation of Backtracking by V. Anton Spraul

New to eLearning? Learn about SCORM

Christina — Thu, 27 Aug 2020 17:34:08 +0000

When I was contacted by an eLearning company about a role that involved integrating their learning management system, or LMS, with clients' LMSs using SCORM and SSO, I had to look these terms up but I was intrigued. Once I had a basic understanding I realized just how interesting the role sounded and was that much more excited to pursue it and to learn more. During my research I was especially interested in SCORM and decided I wanted to share my newfound knowledge here since writing these articles always helps me solidify my learning and I love sharing with this community however I can. Read on if you are curious about the eLearning industry, an industry that I believe is increasingly vital especially considering the current climate with COVID-19. I will specifically discuss SCORM, the most commonly used content standard in eLearning.

The Basics: LMS and SCORM

First of all I think it's important to get some vocabulary out of the way...

A Learning Management System (LMS) is a software application that is responsible for the administration, documentation, tracking, reporting, and delivery of educational courses. If, like me, you've ever used Moodle, it is the most popular SCORM compliant LMS.

SCORM stands for Sharable Content Object Reference Model and is a set of technical standards for web-based educational software products. SCORM basically tells programmers how to write their code so that it can integrate easily with other eLearning software. The SCORM standard makes sure that all eLearning content and LMSs can work with each other, just like the DVD standard makes sure that all DVDs will play in all DVD players. While it doesn't determine anything about the instructional design of eLearning content, it does govern how online learning content and LMSs communicate with each other.

"Sharable Content Object Reference Model" is a mouthful and I find it easier to understand if we break it down into its two main parts: Sharable Content Object and Reference Model.

Sharable Content Object describes the reusable elements of the SCORM package.
Reference Model refers to the standard that SCORM sets.

How Does It Work?

When creating an eLearning course with an authoring tool that is SCORM compliant the output is a zip folder which is uploaded to the LMS. The LMS handles everything from there (so long as it’s SCORM compliant too). When the course is published, the user can launch it in a browser and the LMS collects data to track and report results of their performance.

image from ispringsolutions.com

SCORM utilizes JavaScript to facilitate communication between the client side content and the run-time environment. When a user takes a SCORM course, data is being tracked and sent back to the LMS. Some examples include:

lesson_location (where the user left off)
suspend_data (bookmark with the specific information)
lesson_status (pass, fail, complete, incomplete)
session_time and total_time
score_raw (score the user got)
mastery_score (passing score)
interactions (individual answers to exam questions, time spent etc.)

Why Use SCORM?

Now that we understand what SCORM is, let's look at why it's so important in the eLearning industry:

It's great for consumers since learning content can be used on any compliant LMS meaning the user doesn't have to be trapped into using a poorly performing LMS.
Since SCORM is so widely used and is considered the gold standard at this point, there is a huge array of reliable, interoperable LMSs to choose from that are SCORM compliant.
Overall cost of delivering training has been reduced due to SCORM since the standard has been set with proven quality.
The data being tracked, as mentioned in the last section, creates a better user experience since they are able to easily bookmark, track scores, etc.

Conclusion

If you are interested in the eLearning industry and the technology behind the scenes of it, it's worth your while to learn about SCORM and its relation to LMSs. Personally, this industry speaks to me on many levels. I think high quality eLearning has become increasingly essential in education, especially right now. It also means greater accessibility to education for people who might not otherwise have the means.

Reference material:

How to Design an Algorithm

Christina — Mon, 24 Aug 2020 01:54:18 +0000

One of my favorite parts about studying and coming up with algorithms is seeing the different approaches that programmers take when resolving a problem. In this article, I will discuss some popular techniques you can use to solve problems such as...

Divide and Conquer Algorithms
Dynamic Programming
Greedy Algorithms
Backtracking Algorithms

Divide and Conquer

In my article on sorting algorithms, we looked at the merge and quick sort algorithms. What both have in common is that they are divide and conquer algorithms. Divide and conquer is a common approach to algorithm design and involves breaking a problem down into smaller sub-problems that are similar to the original problem. It often solves the sub-problems recursively and combines the solutions of the sub-problems to solve the original problem.

The logic for the divide and conquer approach can be broken down into three steps:

Divide the original problem into smaller sub-problems.
Conquer the sub-problems by solving them with recursive algorithms that return the solution for the sub-problems.
Combine the solutions of the sub-problems into the solution for the original problem.

Divide and Conquer Example: Binary Search

In my last post about searching algorithms, we implemented the binary search using an iterative approach. Here we will use the divide and conquer approach to implement the binary search.

function binarySearchRecursive(array, value, low, high) {
    if (low <= high) {
        const mid = Math.floor((low + high) / 2);
        const element = array[mid];

        if (element < value) {
            return binarySearchRecursive(array, value, mid + 1, high);
        } else if (element > value) {
            return binarySearchRecursive(array, value, low, mid - 1);
        } else {
            return mid;
        }
    }
    return null;
}

export function binarySearch(array, value) {
    const sortedArray = quickSort(array);
    const low = 0;
    const high = sortedArray.length - 1;

    return binarySearchRecursive(array, value, low, high);
}

Note that the binarySearch function above is what the developer sees to perform the search and the binarySearchRecursive is where we are using the divide and conquer approach.

Dynamic Programming

Dynamic programming is an optimization technique used to solve complex problems by breaking them down into smaller sub-problems. This may sound a lot like the divide and conquer approach but instead of breaking the problem into independent sub-problems and then combining, dynamic programming breaks the problem into dependent sub-problems.

The logic can be broken down into three steps:

Define the sub-problems.
Implement the recurrence that solves the sub-problems.
Recognize and solve the base cases.

Dynamic Programming Example: Minimum Coin Change Problem

This problem is a variation of a commonly used interview question known the the coin change problem. The coin change problem consists of finding out in how many ways you can make change for a particular amount of cents using a given amount of set denominations. The minimum coin change problem simply finds the minimum number of coins needed to make a particular amount of cents using a given amount of denominations. For example, if you need to make change for 39 cents, you can use 1 quarter, 1 dime, and 4 pennies.

function minCoinChange(coins, amount) {
    const cache = [];
    const makeChange = (value) => {
        if (!value) {
            return [];
        }
        if (cache[value]) {
            return cache[value];
        }
        let min = [];
        let newMin;
        let newAmount;
        for (let i = 0; i < coins.length; i++) {
            const coin = coins[i];
            newAmount = value - coin;
            if (newAmount >= 0) {
                newMin = makeChange(newAmount);
            }
            if (newAmount >= 0 && 
            (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
            }
        }
        return (cache[value] = min);
    }
    return makeChange(amount);
}

Some notes about the implementation above: The coins parameter represents the denominations (in the US coin system, it would be [1, 5, 10, 25]). In order to not recalculate values, we can use a cache (this technique is called memoization). The makeChange function is recursive and responsible for solving the problem and because it is an inner function, it has access to the cache.

console.log(minCoinChange([1, 5, 10, 25], 37)); // [1, 1, 10, 25]
console.log(minCoinChange([1, 3, 4], 6)) // [3, 3]

Greedy Algorithms

Greedy algorithms are concerned with the best solution at the time with the hope of finding a global optimum solution. Unlike dynamic programming, it does not take into consideration the bigger picture. Greedy algorithms tend to be simple and intuitive but may not be the best overall solution.

Greedy Algorithm Example: Minimum Coin Change Problem

The coin problem that we solved dynamically above can also be solved with a greedy algorithm. How optimal this solution will be depends on the denominations passed.

function minCoinChange(coins, amount) {
    const change = [];
    let total = 0;
    for (let i = coins.length; i>= 0; i--) {
        const coin = coins[i];
        while (total + coin <= amount) {
            change.push(coin);
            total += coin;
        }
    }
    return change;
}

As you can see, this solution is much simpler than the dynamic programming solution. Let's take a look at some example parameters to see the difference in optimization however:

console.log(minCoinChange([1, 5, 10, 25], 37)); // [25, 10, 1, 1]
console.log(minCoinChange([1, 3, 4], 6)) // [4, 1, 1]

The greedy solution gave the optimal result for the first example but not the second (should be [3, 3], like we got from the dynamic algorithm).

Greedy algorithms are simpler and faster than dynamic programming algorithms but may not give the optimal solution all of the time.

Backtracking Algorithms

Backtracking algorithms are good for incrementally finding and building a solution.

Try to solve the problem one way.
If it doesn't work, backtrack and select repeat step 1 until you reach an appropriate solution.

For an example using backtracking, I will be writing a separate post going over a more complex algorithm. I haven't decided yet but I may try writing a sudoku solver so stay tuned if that interests you!

Conclusion

The possibilities with programming are endless and same goes for algorithm design but I hope this article helps you understand some common approaches.

Linear, Binary, and Interpolation Search Algorithms Explained

Christina — Sun, 16 Aug 2020 23:35:27 +0000

In my last post, I took a look at some of the most common sorting algorithms in JavaScript. Now, I'd like to talk about searching algorithms. If you've checked out some of my other posts, for example the one on binary search trees, then you'll notice that this isn't the first time I've written about searching algorithms on DEV. That being said, I'm aiming for this article to take a deeper look at some of the most common searching algorithms and really break them down. In this article, I'll cover the following searching algorithms:

Linear Search (aka Sequential Search)
Binary Search
Interpolation Search

Linear Search

Also known as the sequential search, the linear search is the most basic searching algorithm. With a big-O notation of O(n), the linear search consists of comparing each element of the data structure with the one you are searching for. It's up to your implementation whether you return the value you were looking for or a boolean according to whether or not the value was found. As you can probably guess, this is a very inefficient process.



function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return null;
}

Binary Search

The binary search algorithm works with a sorted data structure. In this implementation we will use the quicksort algorithm. The big-O notation for this algorithm is O(log n). The process looks something like this:

Select a value in the middle of the (sorted) array
If the value is what we are searching for, we are done
Otherwise, if what we are searching for is less than the value, go back to step one with the left subarray
Or, if what we are searching for is greater than the value, go back to step one with the right subarray



function binarySearch(arr, target) {
    const sortedArr = quickSort(arr);
    let low = 0;
    let high = sortedArr.length - 1;
    while (low <= high) {
        const mid = Math.floor(low + high);
        const element = sortedArr[mid];
        if (element < target) {
            low = mid + 1;
        } else if (element > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return null;
}

Interpolation Search

The interpolation search is basically an improved version of the binary search. This searching algorithm resembles the method by which one might search a telephone book for a name: with each step, the algorithm calculates where in the remaining search space the target element might be based on the value of the bounds compared to the target element. If elements are uniformly distributed, the time complexity is O(log (log n)). In worst cases it can take up to O(n).

The steps to this algorithm are the same as the steps for binary search except for the first step. Instead of selected a value in the middle of the array as the value, we will select it using the position formula which you will notice in our implementation below:



function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    let position = -1;
    let delta = -1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        delta = (target - arr[low])/(arr[high] - arr[low]);
        position = low + Math.floor((high - low) * delta);
        if (arr[position] === target) {
            return position;
        }
        if (arr[position] < target) {
            low = position + 1;
        } else {
            high = position - 1;
        }
    }
    return null;
}

Note that in the following example, the distribution is very uniform and the delta/difference is very small, making this a pretty ideal situation for this search.

Conclusion

I hope that this article helped you gain a clearer understanding of some common search algorithms. Searching algorithms are fundamental to algorithm practice and open doors to much more complex and interesting solutions. Stay tuned as I hope to go over some interesting algorithms in future posts that will rely on much of the material covered in this post.

Common Sorting Algorithms in JavaScript

Christina — Fri, 07 Aug 2020 00:04:24 +0000

In this article, I will cover some common sorting algorithms in computer science. Sorting algorithms are important to study because they can often reduce the complexity of a problem. They also have direct applications in searching algorithms, database algorithms, and much more.

Sorting algorithms we will learn about:

Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Bucket Sort

Helper Methods for Swapping and Comparing

We will be swapping elements in arrays a lot so let's start by writing a helper method called swap:



function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

We will be comparing elements a lot so I think it's a good idea to write a function for just that:



const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

Okay, now that that's settled, let's move onto sorting!

Bubble Sort

Best: O(N), Worst: O(N^2)

The bubble sort is a good starting point since it is one of the simplest sorting algorithms. It's mostly just good for teaching purposes though since it is one of the slowest sorting algorithms.

In short, the bubble sort algorithm compares every two adjacent values and swaps them if the first one is bigger than the second one. This reflects its name since the values tend to move up into the correct order, like bubbles rising to the surface.



function bubbleSort(arr, compare = defaultCompare) {
    const { length } = arr;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // refer to note below
            if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

Note that the solution I provided is a slightly improved version of the usual bubble sort algorithm since we are subtracting the number of passes from the inner loop to avoid unnecessary comparisons. To get a better understanding of what's actually happening, here is a diagram with an example:

Selection Sort

Best/Worst: O(N^2)

The basic idea behind the selection sort algorithm is that is finds the minimum value in the data structure, places it in the first position, finds the second minimum value, places it in the second position, and so on.



function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}

The following diagram acts as an example of the selection sort algorithm in action:

Insertion Sort

Best: O(N), Worst: O(N^2)

The insertion sort algorithm builds the final sorted array one value at a time. The process looks something like this:

Assume the first element is already sorted.
Compare the first and second elements - should the second value stay in its place or be inserted before the first value?
Next, you can do a similar comparison with the third value - should it be inserted in the first, second, or third position? And so on...



function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

Refer to this diagram for an example of insertion sort in action:

The insertion sort algorithm has a better performance than the selection and bubble sort algorithms when sorting small arrays though again, I wouldn't really recommend using it outside educational purposes.

Merge Sort

Best/Worst: O(N Log N)

The merge sort algorithm is a divide-and-conquer algorithm. In other words, it divides the original array into smaller arrays until each small array has only one position, then it merges the smaller arrays into a bigger one that is sorted.

The implementation here is recursive and consists of two functions, one to divide the arrays into smaller ones and one to perform the sort:



function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

Here's a diagram to visualize the process:

Quick Sort

Best/Average: O(N Log N), Worst: O(N^2)

The quick sort is one of the most used sorting algorithm. Similar to the merge sort, the quick sort also uses the divide-and-conquer approach. Let's break the process down into steps to understand it a little better since it's a bit more complex than the previous sorts we've covered:

Select a value from the array that we will call pivot, generally the value at the middle of the array.
Perform the partition operation which will result in an array with values lesser than the pivot on the left and greater on the right.
Repeat the first two steps for each subarray (left and right) until the arrays are completely sorted.



function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

Bucket Sort

Best/Average: O(N + k), Worst: O(N^2)

The bucket sort algorithm is a distributed sorting algorithm that separates the elements into different buckets, or smaller arrays, and then uses a simpler sorting algorithm good for sorting small arrays, such as insertion sort, to sort each bucket.



function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}

Note that the bucket sort works best when the elements can be distributed into buckets evenly. If the elements are largely sparse, then using more buckets is better, and vice versa.

The following diagram demonstrates the bucket sort algorithm in action:

Conclusion

We have covered some of the most common sorting algorithms. There are a lot more sorting algorithms I didn't get to go over in this article so let me know if you would like me to write a second part. Either way, I plan to write about searching algorithms soon so stay tuned!

Below are some reference material (the sound of sorting video is my favorite!):

Big O Notation Cheat Sheet
The Sound of Sorting (Full Video) by Timo Bingmann
Implementations in multiple languages from freeCodeCamp
Sorting Visualization Tool from Visualgo
Comedic Sorting Algo Webcomic from xkcd

Creating the Dictionary Class with JavaScript

Christina — Fri, 31 Jul 2020 20:12:20 +0000

To continue my exploration of data structures, I wanted to write this article on creating our own dictionary class in JavaScript.

A dictionary, also known as a map, is used to store [key, value] pairs, where the key can be used to look up a particular element. Dictionaries are often used to store the reference address of objects or for a project like an actual dictionary or an address book, for example.

Creating the Dictionary class

The base structure of our Dictionary class will look like this:

import { defaultToString } from '../util';

export default class Dictionary {
    constructor(toStrFn = defaultToString) { // defaultToString below
        this.toStrFn = toStrFn;
        this.table = {};
    }
}

As you can see, we are storing the elements of the Dictionary class in an Object instance and the [key, value] pairs are being stored as table[key] = {key, value}.

Ideally, we would be storing keys of type string and any type of value but because JavaScript is not strongly typed, we cannot guarantee the key will be a string. Thus, we will have to transform whatever object is passed as the key into a string to make it easier to search and retrieve values. For this reason, we are passing in a function which will look something like this:

export function defaultToString(item) {
    if (item === null) {
        return 'NULL';
    } else if (item === undefined) {
        return 'UNDEFINED';
    } else if (typeof item === 'string' || item instanceof String) {
        return `${item}`;
    }
    return item.toString();
}

Over the course of this article, we will cover the following methods for our dictionary:

hasKey(key): return true if the key exists in the dictionary.
set(key, value): add a new element to the dictionary. If the key already exists, the existing value will be overwritten with the new one.
remove(key): remove the value from the dictionary.
get(key): return the value associated with the passed key.
keys(): return an array of all the keys the dictionary contains.
values(): return an array of all the values of the dictionary.
keyValues(): return an array of all [key, value] pairs of the dictionary.
size(): return the number of values the dictionary contains.
isEmpty(): return true if the size equals zero.
clear(): remove all values from the dictionary.
forEach(callBackFn): iterate every value pair in the dictionary and perform the call back function.

Verify a key exists in the dictionary

The first method we will cover is the hasKey(key) method since we will need it for other methods.

hasKey(key) {
    return this.table[this.toStrFn(key)] != null;
}

Set a key and value in the dictionary

Next up, the set(key, value) method which can be used to add a new value or update an existing one:

set(key, value) {
    if (key != null && value != null) {
        const tableKey = this.toStrFn(key);
        this.table[tableKey] = new ValuePair(key, value);
        return true;
    }
    return false;
}

As you can see, we instantiated the class ValuePair which we define as follows:

class ValuePair(key, value) {
    constructor(key, value)  {
        this.key = key;
        this.value = value;
    }

    toString() {
        return `[${this.key}: ${this.value}]`;
    }
}

Remove a value from the dictionary

The remove method is pretty straight forward at this point, especially with the help of the JavaScript delete operator:

remove(key) {
    if (this.hasKey(key)) {
        delete this.table[this.toStrFn((key))];
        return true;
    }
    return false;
}

Retrieve a value from the dictionary

Next, we will write the get method in order to search for a particular key and retrieve its value:

get(key) {
    const valuePair = this.table[this.toStrFn(key)];
    return valuePair == null ? undefined : valuePair.value;
}

keyValues, keys, and values methods

Now we will create some more supplementary but nevertheless useful methods. The valuePairs method will return an array with all ValuePair objects in the dictionary, using the built-in values method from the JavaScript Object class:

keyValues() {
    return Object.values(this.table);
}

Next, we will write the keys method which returns all the original keys used to identify a value in the Dictionary class:

keys() {
    return this.keyValues().map(valuePair => valuePair.key);
}

The values method will look similar to the keys method, returning an array of all values stored in the dictionary:

values() {
    return this.keyValues().map(valuePair => valuePair.value);
}

Iterating each ValuePair of the dictionary

Let's write a forEach method that will iterate each ValuePair in the dictionary and evoke a callback function for each iteration:

forEach(callbackFn) {
    const valuePairs = this.keyValues();
    for (let i = 0; i < valuePairs.length; i++) {
        const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
        if (result === false) {
            break;
        }
    }
}

size, isEmpty, clear, and toString methods

size() {
    return this.keyValues().length;
}

Note we could have evoked the Object.keys method instead (return Object.keys(this.table).length).

Now we can use our size method for isEmpty:

isEmpty() {
    return this.size() === 0;
}

As expected, clear is very simple:

clear() {
    this.table = {};
}

Finally, the toString method:

toString() {
    if (this.isEmpty()) {
        return '';
    }
    const valuePairs = this.keyValues();
    let objString = `${valuePairs[0].toString()}`;
    for (let i = 1; i < valuePairs.length; i++) {
        objString = `${objString}, ${valuePairs[i].toString()}`;
    }
    return objString;
}

Conclusion

I hope this article helped you gain a better understanding of dictionaries and the common methods associated with it. I sort of considered this to be a warm up for a later article I plan to write soon on Hash Tables so stay tuned for more!

Creating Dictionary using Object by Ismail Baydan of Poftut

Self-Balancing Trees

Christina — Sun, 26 Jul 2020 23:39:03 +0000

After getting great feedback from my last post on binary search trees (BST), I felt inspired to dive in even further by taking a look at self-balancing trees.

The Problem with Binary Search Trees

Depending on how many nodes you add to a BST, one of the edges of the tree can be very deep, as shown in the diagram below:

This can cause performance issues when manipulating or searching for a node on a particular edge of the tree. If you take a look at the Big-O Algorithm Complexity Cheat Sheet, you can see that the worst case time complexity of BST operations is O(h) where h is the height of the tree. Therefore, having the height be as small as possible is better when it comes to performing a large number of operations. That's where self-balancing binary search trees come in since their average and worst case time complexities are O(log n).

Solution: Self-Balancing Trees

In this article, we will learn about the Adelson-Velskii and Landi's tree (AVL tree) which is a self-balancing BST. This basically means that the height of the left and right subtrees of any node will differ by 1 at most. AVL trees have a worst case lookup, insert and delete time of O(log n). AVL trees are particularly helpful for quick searches of large amounts of data which is especially important in data analysis and data mining for example.

Let's begin by creating an AVLTree class which will be an extension of the BinarySearchTree class we wrote in my last blog post:

class AVLTree extends BinarySearchTree {
    constructor() {
        this.root = null;
    }
}

We will only need to overwrite the methods which will help maintain the AVL tree's balance: insert, insertNode, and removeNode. All the others will be inherited.

Before we get into writing our methods, let's review some terminology and the AVL tree's rotation operations.

Height of a Node and the Balancing Factor

As a reminder, the height of a node is defined as the maximum number of edges from the node to any of its leaf nodes.

The code to calculate the height of a node looks like this:

getNodeHeight(node) {
    if (node === null) {
        return -1;
    }
    return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}

When it comes to inserting and removing nodes in an AVL tree versus a BST, the key difference is that we will need to verify its balance factor. The balance factor for a node is the difference between the height of the left and right subtrees. A binary tree is said to be balanced if the balance factor is -1, 0, or 1.

Balance Factor = Height of Left Subtree - Height of Right Subtree

Here are three examples of balanced trees with just their balance factors displayed:

Next, let's write the code to calculate the balance factor of a node and return its state:

getBalanceFactor(node) {
    const heightDif = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
    switch (heigthDif) {
        case -2: 
            return BalanceFactor.UNBALANCED_RIGHT; 
        case -1: 
            return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
        case 1: 
            return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
        case 2: 
            return BalanceFactor.UNBALANCED_LEFT;
        default: 
            return BalanceFactor.BALANCED;
    }
} 

const BalanceFactor = {
    UNBALANCED_RIGHT: 1, 
    SLIGHTLY_UNBALANCED_RIGHT: 2, 
    BALANCED: 3, 
    SLIGHTLY_UNBALANCED_LEFT: 4, 
    UNBALANCED_LEFT: 5
}

We will go into detail about what each heightDif means in the subsequent sections...

Balancing Operations: AVL Rotations

After inserting or removing nodes from the AVL tree, you will need to verify whether the tree needs to be balanced. We will go over four scenarios involving two balancing processes: simple rotation and double rotation.

Left Rotation (LL)

If a tree becomes unbalanced when a node is inserted into the right subtree, you can perform a single left rotation, as shown in the diagram below:

The following code exemplifies this process:

rotationLL(node) {
    const temp = node.left;
    node.left = temp.right;
    temp.right = node;
    return temp;
}

Right Rotation (RR)

The right rotation is the inverse of the left rotation so I won't go into detail but the diagram and code will look like this:

rotationRR(node) {
    const temp = node.right;
    node.right = temp.left;
    temp.left = node;
    return temp;
}

Left Right Rotation (LR)

This case occurs when the height of the node's left child becomes greater than that of the right child's and the left child is right-heavy. We can fix this case by performing a left rotation on the left child, which produces the LL case, and then doing a right rotation on the unbalanced node. Refer to the diagram and code below:

rotationLR(node) {
    node.left = this.rotationRR(node.left);
    return this.rotationLL(node);
}

Right Left Rotation (RL)

Again, the right left rotation is the inverse of the left right rotation:

rotationRL(node) {
    node.right = this.rotationLL(node.right);
    return this.rotationLL(node);
}

Insert a Node in the AVL Tree

In an AVL tree, he process of inserting a node can be broken down into four steps:

Insert the new element using BST insertion logic.
Check the balance factor of every node.
If the balance factor of every node is 0, 1, or -1, skip step 4.
Otherwise, the tree is unbalanced so you will need to perform the appropriate rotation to make it balanced.

insert(data) {
    let newNode = new Node(data);

    if(this.root === null) {
        this.root = newNode;
    } else {
        this.insertNode(this.root, newNode); // helper method below
    }
}

insertNode(node, newNode) {
    // insert node as in BST tree (step 1)
    if (newNode.data < node.data) {
        if (node.left === null) {
            node.left = newNode;
        } else {
            this.insertNode(node.left, newNode);
        }
    } else {
        if (node.right === null) {
            node.right = newNode;
        } else {
            this.insertNode(node.right, newNode);
        }
    }

    // check balance factor of every node (step 2)
    const balanceFactor = this.getBalanceFactor(node);

    // balance if necessary (steps 3 & 4)
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
        if (newNode.data < node.left.data) {
            node = this.rotationLL(node);
        } else {
            return this.rotationLR(node);
        }
    }
    if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
        if (newNode.data > node.right.data) {
            node = this.rotationRR(node);
        } else {
            return this.rotationRL(node);
        }
    }
    return node;
}

Remove a Node from the AVL Tree

Again, we'll break down removing a node into steps:

Remove the node using BST deletion logic.
Verify whether the tree is balanced. If it is, skip step 3.
Otherwise, apply the appropriate rotations.

removeNode(node, data) {
    // remove the node (step 1)
    node = super.removeNode(node, data); // from BinarySearchTree super class
    if (node === null) {
        return node; // no need to balance
    }

    // verify tree is balanced (step 2)
    const balanceFactor = this.getBalanceFactor(node);

    // balance if necessary (step 3)
    if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
        const balanceFactorL = this.getBalanceFactor(node.left);
        if (balanceFactorL === BalanceFactor.BALANCED || balanceFactorL === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
            return this.rotationLL(node);
        }
        if (balanceFactorL === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
            return this.rotationLR(node.left);
        }
    } else if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
        const balanceFactorR = this.getBalanceFactor(node.right);
        if (balanceFactorR === BalanceFactor.BALANCED || balanceFactorR === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
            return this.rotationRR(node);
        }
        if (balanceFactorR === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
            return this.rotationRL(node.right);
        }
    }
    return node;
}

Rotations Cheat Sheet

Here's a cheat sheet for quicker reference and as an overview of when to use the four rotation types:

if tree is right heavy {
    if right subtree is left heavy {
        Perform LR rotation
    } else {
        Perform LL rotation
    }
} else if tree is left heavy {
    if left subtree is right heavy {
        Perform RL rotation
    } else {
        Perform RR rotation
    }
}

Conclusion

I hope you found this article helpful in understanding the basics of self-balancing trees. I used the AVL tree as an example but there are other types of self-balancing trees out there to learn about if you are interested. Here are a few resources that I used to write this article and for you to continue your own studies.

AVL Tree Visualization by David Galles
Step-by-step Rotations from Tutorials Point

Also, if you are interested in learning about another popular type of self-balancing tree, check out this article on the Red-Black Tree by GeeksforGeeks.

Understanding Binary Search Trees

Christina — Fri, 17 Jul 2020 22:29:16 +0000

As promised in my last post on recursion, which I recommend reading before this article as we will be using it a lot in my examples, I want to take a closer look at the tree data structure in this article. Trees are a non-sequential data structure that is useful for storing information that needs to be found easily. In other words, they are an abstract model of a hierarchical structure (think of a family tree). Trees consist of nodes with a parent-child relationship.

Binary Tree and Binary Search Tree

A node in a binary tree has at most two children: a left and a right child. This definition allows you to write algorithms to insert, search, and delete nodes more efficiently. Refer to the image above to see a binary tree and the key vocabulary that I will be using in this article.

As you can probably guess, a binary search tree (BST) is a binary tree. The key difference is that a BST only allows you to store nodes with lesser value on the left side and nodes with greater value on the right. In case you didn’t notice, this is exemplified in the image above. If you’re having a difficult time understanding how the image is ordered, don’t worry, we’ll go into more detail in the next sections!

Creating the Node and BST Classes

As usual, I highly encourage you to code along with me and to continuously test/play around with whatever we write. To start, we will create our Node class which will represent the nodes in our BST:

class Node {
    constructor(data) {
        this.data = data; // node value
        this.left = null;   // left node child reference
        this.right = null; // right node child reference
    }
}

Next, we will declare the basic structure of our BinarySearchTree class:

class BinarySearchTree {
    constructor() {
        this.root = null; // root of bst
    }
}

Our next step will be to implement some methods. Here’s what we’ll cover:

insert(data)
inOrderTraverse()
preOrderTraverse()
postOrderTraverse()
search(data)
remove(data)

Inserting a Node into a BST

To insert a new node into a tree, there are two steps we will follow:

Verify whether the insertion is a special case. In other words, we need to check if the node we are trying to add is the first one in a tree. If it is, we simply need to point the root to this new node by creating an instance of the Node class and assigning it to the root property.
Add the node to a different position than the root.

insert(data) {
    let newNode = new Node(data);

    if(this.root === null) {
        this.root = newNode;
    } else {
        this.insertNode(this.root, newNode); // helper method below
    }
}

insertNode(node, newNode) {
    if(newNode.data < node.data) {
        if(node.left === null) {
            node.left = newNode;
        } else {
            this.insertNode(node.left, newNode);
        }
    } else {
        if(node.right === null) {
            node.right = newNode;
        } else {
            this.insertNode(node.right, newNode);
        }
    }
}

To summarize, insert(data) creates a new Node with a value of data and if the tree is empty, it sets that node as the tree’s root, otherwise it calls insertNode(this.root, newNode). insertNode(node, newNode) is our helper method which is responsible for comparing the new node data with the data of the current node and moving left or right accordingly recursively until it finds a correct node with a null value where the new node can be added.

As an example, if we were to execute the following code...

const BST = new BinarySearchTree();
BST.insert(11); // establishes root node 
BST.insert(7);
BST.insert(9);
BST.insert(15);
...
BST.insert(6);

...we can illustrate the last insert with this diagram:

Traversing the BST

Traversing a tree is the process of visiting all the nodes in a tree and performing an operation at each node. The big question is, how should we go about this? There are three common approaches: in-order, pre-order, and post-order.

In-Order Traversal

An in-order traversal will visit all nodes in ascending order, starting from a given node (optional), and perform the given callback function (also optional). Again, we will use recursion here:

inOrderTraverse(node, callback) {
    if(node != null) {
        this.inOrderTraverse(node.left, callback);
        callback(node.data);
        this.inOrderTraverse(node.right, callback);
    }
}

The following diagram shows the path that our inOrderTraverse takes:

Pre-Order Traversal

A pre-order traversal visits the node prior to its descendants. Take note of the pretty subtle difference the the order in the code and in the diagram:

preOrderTraverse(node, callback) {
    if(node != null) {
        callback(node.data);
        this.preOrderTraverse(node.left, callback);
        this.preOrderTraverse(node.right, callback);
    }
}

Post-Order Traversal

If you haven't guessed already, a post-order traversal visits the node after its descendants. You can probably guess how the code will differ here but be sure to double check yourself with the diagram:

postOrderTraverse(node, callback) {
    if(node != null) {
        this.postOrderTraverse(node.left, callback);
        this.postOrderTraverse(node.right, callback);
        callback(node.data);
    }
}

Searching for Values in a BST

In our implementation, node represents the current node and data represents the value we are searching for:

search(node, data) {
    if(node === null) {
        return null;
    } else if(data < node.data) {
        return this.search(node.left, data);
    } else if(data > node.data) {
        return this.search(node.right, data);
    } else {
        return node;
    }
}

I encourage you to give test your code here and you can add in a console.log so you can see which nodes are visited. Even if you aren't coding along, go ahead and trace one of the diagrams in this article and predict the method's path when searching for a particular value. You'll notice how easy it is to find the max and min values too!

Removing a Node from a BST

The remove method is the most complex method we will cover in this article. It's complexity is due to the different scenarios that we need to handle and because it is recursive.

remove(data) {
    this.root = this.removeNode(this.root, data); // helper method below
}

removeNode(node, data) {
    if(node === null) {
        return null;
    // if data to be deleted is less than the root's data, move to the left subtree
    } else if(data < node.data) {
        node.left = this.removeNode(node.left, data);
        return node;
    // if data to be deleted is greater than the root's data, move to the right subtree
    } else if(data > node.data) {
        node.right = this.removeNode(node.right, data);
        return node;
    // if data is similar to the root's data, delete the node
    } else {
        // delete node with no children (leaf node)
        if(node.left === null && node.right === null) {
            node = null;
            return node;
        }

        // delete node with one child
        if(node.left === null) {
            node = node.right;
            return node;
        } else if(node.right === null) {
            node = node.left;
            return node;
        }

        // delete node with two children
        // minimum node of the right subtree is stored in newNode
        let newNode = this.minNode(node.right);
        node.data = newNode.data;
        node.right = this.removeNode(node.right, newNode.data);
        return node;
    }
}

If we end up finding the matching node to be deleted, there are three scenarios to handle which we will discuss in more detail below. These scenarios can be found in the big else statement in the code.

Removing a Leaf Node

The first scenario involves a leaf node which does not have a left or right child. In this case, we will need to remove the node by assigning null to it. However, don't forget that we will also want to take care of the references from the parent node. Refer to the diagram which shows the removal of a leaf node:

Removing a Node with One Child

The second scenario involves a node that has a left of right child. As you can see in the diagram below, we will need to skip matching node and assign the parent pointer to the child node:

Removing a Node with Two Children

The third and final scenario involves a node with both let and right children. To remove such a node, follow these steps:

Once you find the node to be removed, find the minimum node from its right edge subtree (refer to shaded area in the diagram below).
Next you can update the value of the node with the key of the minimum node from its right subtree. With this action, you are replacing the key of thenode, which means it is effectively removed.
Now you have two nodes in the tree with the same key which cannot happen (refer to the two 18s in the diagram). Thus, you need to remove the minimum node from the right subtree since you moved it to the place of the removed node.
Finally, return the updated node reference to its parent.

Conclusion

In this article, we covered the algorithms to add, search for, and remove nodes from a binary search tree as well as treee traversal.

For some additional fun, I came across this interesting tool where you can play around with an interactive BST along with many other data structures, created by David Galles. And if you want to learn more about the cover image and how it relates to binary trees, check out this explanation of symmetric binary trees by Larry Riddle (be warned it's pretty math heavy but there are some cool illustrations)!

Recursion Explained (with Examples)

Christina — Wed, 08 Jul 2020 00:12:15 +0000

“To understand recursion, one must first understand recursion” - Unknown

Recursion is a method of solving problems where you solve smaller portions of the problem until you solve the original, larger problem. A method or function is recursive if it can call itself.



function understandRecursion(doIUnderstandRecursion) {
    const recursionAnswer = confirm('Do you understand recursion?');
    if(recursionAnswer === true) { // base case
        return true;
    }
    understandRecursion(recursionAnswer); // recursive call
}

For the example above, notice the base case and recursive call which make this a recursive algorithm. Recursive functions must have a base case, or a condition in which no recursive call is made. I think the best way to understand recursion is to look at examples so let’s walk through two common recursive problems.

Example 1: Calculating the Factorial of a Number

Calculating the factorial of a number is a common problem that can be solved recursively. As a reminder, a factorial of a number, n, is defined by n! and is the result of multiplying the numbers 1 to n. So, 5! is equal to 5*4*3*2*1, resulting in 120.

Let’s first take a look at an iterative solution:



function factorial(num) {
    let total = 1;
    for(let n = num; n > 1; n--) {
        total *= n;
    }
    return total;
}

The iterative solution above is fine but let’s try rewriting it using recursion. When we think about solving this problem recursively, we need to figure out what our subproblems will be. Let’s break it down:

We know factorial(5) = 5 * factorial(4) aka 5! = 5 * 4!.
To continue, factorial(5) = 5 * (4 * factorial(3)) which equals 5 * (4 * (3 * factorial(2)) and so on…
...Until you get 5 * 4 * 3 * 2 * 1 and the only remaining subproblem is 1!.
factorial(1) and factorial(0) always equals 1 so this will be our base case.

Using this line of thinking, we can write a recursive solution to our factorial problem:



function factorial(n) {
    if(n === 1 || n === 0) { // base case
        return 1;
    }
    return n * factorial(n - 1); // recursive call
}

Example 2: Fibonacci Sequence

Another fun problem that can be solved using recursion is the Fibonacci sequence problem. As a reminder, the Fibonacci sequence is a series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The pattern involves totaling the two previous numbers so 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, etc. In other words, the Fibonacci number at position n (for n > 2) is the Fibonacci of (n - 1) plus the Fibonacci of (n - 2).

Again, I think it’s helpful to see an iterative solution first:



function fibonacci(n) {
    if(n === 0) return 0;
    if(n === 1) return 1;

    let fibNMinus2 = 0;
    let finNMinus1 = 1;
    let fibN = n;

    for(let i = 2; i <= n; i++) { // n >= 2
        fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
        fibNMinus2 = fibNMinus1;
        fibNMinus1 = fibN;
    }
    return fibN;
}

As you’ll see, the recursive solution looks much simpler:



function fibonacci(n) {
    if(n === 0) return 0; // base case 1
    if(n === 1) return 1; // base case 2

    return fibonacci(n - 1) + fibonacci(n - 2); // recursive call
}

If you were to call fibonacci(5), the following represents the calls that would be made:

Fibonacci with Memoization

I wanted to take this opportunity to mention another approach to this problem, called memoization. Memoization consists of an optimization technique that stores the values of the previous results, similar to a cache, making our recursive solution faster. If you look back at the calls made to compute fibonacci(5) in the image above, you can see that fibonacci(3) was computed twice, so we can store its result so that when we compute it again, we already have it.

Take a look at how our fibonacci solution changes when we add memoization:



function fibonacci(n) {

    const memo = [0, 1]; // cache all computed results here

    const fib = (n) => {

        if(memo[n] != null) return memo[n]; // base case

        return memo[n] = fib(n - 1, memo) + fib(n - 2, memo); // recursive call

    };

        return fib(n);

}

Why Use Recursion?

To be completely frank, a recursive solution is almost always slower than an iterative one. That being said, if you look back at our Fibonacci solutions, the recursive solution is much easier to read plus memoization can help bridge the gap in speed. Recursion is generally easier to understand and usually requires less code.

Conclusion

Now that we’ve gone over some examples, I hope recursion is a little easier for you to grasp and that you can see why we would use it. In a future post, I plan to take a look at the tree data structure which uses recursion in many of its methods so stay tuned! This article only scratches the surface of recursion’s potential so here are a few resources you might find helpful if you want to continue your studies.

Practice with Recursive Problems via HackerRank
Famous Recursive Problems via Princeton

Implementing Stacks with JavaScript

Christina — Thu, 02 Jul 2020 00:18:25 +0000

While arrays allow us to add or remove elements at any index, sometimes we need a data structure where we have more control over adding and removing items. In this article, I am going to explain what stacks are, how we can use them to address this sort of problem, and provide examples of implementation.

What is a Stack?

A stack is an ordered collection of items that follows the last in, first out (LIFO) principle. In other words, the addition and removal of items happen at the same end. The newest elements are near the top of the stack and the oldest are near the base. You can think of a stack as a stack of books or even your browser history (the browser’s back button).

The Pros and Cons of Stacks

Stacks allow for constant time when adding and removing elements. This is due to the fact that you don’t need to shift elements around to add and remove them from the stack.

The downside of stacks is that they don’t offer constant-time access to the nth element in the stack, unlike an array. This means it could take O(n) time to retrieve an element where n is the number of elements in the stack.

Creating an Array-based Stack Class

I encourage you to try this on your own if you haven’t before since it is a great way to learn about how stacks work and to experiment with this essential data structure.

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

In our example, we are using an array to store the elements of the stack. Since the stack follows the LIFO principle however, we will need to limit the functionalities that will be available for the insertion and removal of elements. The following methods will be available in the Stack class:

push(element(s)): add an element (or several elements) to the top of the stack.
pop(): remove the top element of the stack and return the removed element.
peek(): return the top element of the stack without modifying the stack itself.
isEmpty(): return true if the stack does not contain any elements, false if the stack’s size is greater than 0.
clear(): remove all elements from the stack.
size(): return the number of elements in the stack (similar to the length property of an array). If you want some practice, I challenge you to implement the methods mentioned above on your own. If you don’t want spoilers, stop scrolling!

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

    push(item) {
        return this.items.push(item);
    }

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

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

    isEmpty() {
        return this.items.length === 0;
    }

    clear() {
        this.items = [];
    }

    size()  {
        return this.items.length;
    }
}

Solving Problems Using Stacks

Stacks can be applied to a variety of real-world problems. They can be used for backtracking problems, remembering paths taken, and to undo actions. I will go over one example and encourage you to try solving others on your own, perhaps through HackerRank.

Convert Decimal Numbers to Binary

To convert a decimal number into a binary representation, we can divide the number by 2 (since binary is a base 2 number system) until the division result is 0. For example:

Here is a solution using a stack:

function decimalToBinary(num) {
    const remStack = [];
    let number = num;
    let rem;
    let binaryString = '';

    while (number > 0) {
        rem = Math.floor(number % 2);
        remStack.push(rem);
        number = Math.floor(number / 2);
    }

    while (remStack.length !== 0) {
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}

In this algorithm, while the division result is not zero, we get the remainder of the division (modulo - mod), and push it to the stack and update the number that will be divided by 2. Then, we pop the elements from the stack until it is empty, concatenating the elements that were removed from the stack to a string.

Conclusion

In this article, we learned about the stack data structure, implemented our own algorithm that represents a stack using arrays, and we did a practice problem. To learn more, I recommend checking out some of these resources:

How to Implement a Stack by Prashant Yadav of freeCodeCamp
Stacks in JavaScript by Loiane Groner from the textbook, Learning JavaScript Data Structures and Algorithms

What you need to know about JavaScript ES6

Christina — Sat, 27 Jun 2020 19:36:27 +0000

JavaScript ES6 has some incredibly useful features that can make your code more modern and readable. In this article, I will go over some of the most essential features of ES6 so you too can write less and do more.

const and let

I won’t go into detail here since I’ve already written another blog post on the uses of var, let, and const here. The gist is that your go-to identifier in Javascript should be const. However, if you know or think you’ll need to reassign it (in a for-loop, switch statement, or in algorithm swapping, for example), use let.

Template Literals

Template literals are very useful because they let you create strings without the need to concatenate the values. For example,

const book = {
    name: 'The Martian'
}
console.log('You are reading ' + book.name + '., \n and this is a new line…'

We can improve the syntax of the previous console.log with the following code:

console.log(`You are reading ${book.name}., 
    and this is a new line…`)

Note that template literals are enclosed in back-ticks. To interpolate a variable value, simply set the variable name inside a dollar sign and curly braces.
As you saw in the example, template literals can also be used for multiline strings. There is no need to use \n anymore. Simply hit Enter on the keyboard to take the string to a new line.

Arrow Functions

Arrow functions are great for simplifying the syntax of functions. For example:

function myFunc(name) {
    return 'Hello' + name
}
console.log(myFunc('World'))

With ES6, we can simplify things like so:

const myFunc = name => {
    return `Hello ${name}`
}

Or if the function has a single statement like our example, you can simplify it even further by omitting the keyword return and the curly brackets like so:

const myFunc = name => `Hello ${name}`

In addition, if the function does not receive any argument, we can use empty parentheses:

const hello = () => console.log('Hello!')

Default Parameters

With ES6, it’s possible to define default parameter values for functions.

function sum(x = 1, y = 2) {
    return x + y
}
console.log(sum(3)) // 5

In the above example, since we did not pass y as a parameter, it will have a value of 2 by default. So, 3 + 2 === 5.

Destructuring

Destruction allows us to initialize multiple variables at once.

let [x, y] = ['a', 'b']

Array destructuring can also be used to swap values at once without the need to create temp variables which is very useful for sorting algorithms.

[x, y] = [y, x]

Another useful functionality is called property shorthand.

let [x, y] = ['a', 'b']
let obj = {x, y}
console.log(obj) // { x: 'a', y: 'b' }

One last functionality we’ll go over is called shorthand method names. This allows us to declare functions inside objects as if they were properties.

const hello = {
    name: 'World', 
    printHello() {
        console.log('Hello')
    }
}
console.log(hello.printoHello())

Spread and Rest Operators

In ES5, we could turn arrays into parameters using the apply() function. ES6 has the spread operator (...) for this purpose. For example, consider a sum function that sums three values:

let params = [3, 4, 5]
console.log(sum(...params))

The spread operator can also be used as a rest parameter like so:

function restParameter(x, y, ...a) {
    return (x + y) * a.length
}
console.log(restParameter(1, 2, 'hello', true, 7)) // 9

Classes

ES6 also introduced a cleaner way of declaring classes. Consider the following:

function Book(title, author) {
    this.title = title
    this.author = author
}
Book.prototype.printTitle = function() {
    console.log(this.title)
}

With ES6, we can simplify the syntax like so:

class Book {
    constructor(title, author) {
        This.title = title
        this.author = author
    }
    printAuthor() {
        console.log(this.author)
    }
}

With ES6, we can use a simplified syntax for inheritance between classes using the keyword extends. As you’ll see in the following example, we can also use the keyword super inside the constructor to refer to the constructor superclass.

class ITBook extends Book {
    constructor(title, author, technology) {
        super(title, author)
        this.technology = technology
    }
}

Conclusion

I hope you found this guide helpful for reviewing some of what I consider to be very useful features of ES6. If you want to read further, here are some resources I’ve found helpful:
ES6 Refresher by Said of freeCodeCamp
JavaScript code with ES6 by Loiane Groner from the textbook, Learning JavaScript Data Structures and Algorithms

Structuring an Informational Interview

Christina — Fri, 19 Jun 2020 20:57:33 +0000

I’ve been getting in the habit of attending at least one virtual meetup every week and this week’s talk was conducted by Flatiron School Career Coach, Cesar Ramirez, on informational interviews.

To be clear, an informational interview is not the same as a job interview. The goal of an informational interview is to have a conversation with someone working in an area or at a company of interest to you. It is an effective research tool that is best done after preliminary research. In this article, I will go over the steps to structuring a successful informational interview.

Benefits of Informational Interviews

Get firsthand, relevant information about working in a particular field or position.
Get tips and insider knowledge about how to prepare for and land your first career position.
Learn about a company of interest including their company culture and values.
Initiate a professional relationship and expand your network in a specific career field.
Meet people who may help you move forward with a job lead in the future.

How to Structure an Informational Interview

Even though it can feel awkward to approach someone you don’t know for an informational interview, I’ve found that a lot of people are happy to share their experience and advice with someone that shows genuine interest and passion. In order to prove your interest though, you will need to do some preparation. To keep things simple, follow these steps to structure a productive informational interview.

1. Research Company of Interest

Gain an understanding of what the company does and what their popular products are.
Read the company about page, looking for their mission and signs of their company culture and values.
If there is a specific role you are interested in, be sure to review the posting and pay attention to what team and/or project you would be working on and what skills they expect of you. If there are any terms or concepts you don’t know, look them up and get at least a basic understanding.
Skim some of their most recent news to make sure you are up to date on company news.
Feel free to write down any questions you have during this process.

2. Identify People to Interview

Pursue your own contacts. If you know anyone at the company, these should be the first people you contact.
If you don’t know anyone personally, use LinkedIn to find people you have something in common with such as going to the same school or having a common connection.
If neither of above are the case, look for who you think would be a part of your hiring process or someone who is currently in the role that you are interested in. Prepare for Interview and Initiate Contact Once you’ve found someone to contact, send your LinkedIn request and be sure to include a message or send an email. You should definitely review their profile before sending your message and include your commonality or something that intrigued you about their profile in your message. If sending an email, you can write a longer message and include your portfolio and/or resume for them to review before your meeting. Two LinkedIn request message examples:

Hi [connection name], It was great meeting you at the [event title] today. It was great hearing your perspective on [common topic]. I’d love to hear more about your experience as a [position] at [company]. Let me know if you have a few minutes to chat!

Hi [connection name], I recently graduated from [school and program]. I’m intrigued by [company and recent accomplishment or product]. Would you have a few minutes to chat about what it’s like to work at [company]?

Your message should ideally include why you are reaching out to them specifically and a personal touch like a commonality. Then you can ask to connect and chat.
Once connected and they agree to chat, you can be more specific about setting up a call. Set up a time and tell them what you hope to talk about generally.
Based on your research, prepare questions

3. Conduct the Informational Interview

Arrive on time or a few minutes early.
Bring your list of questions and something for notes. Some sample questions:

How did you get into [field or position]? How do you like being a [role] at [company]? How would you describe the company culture at [company]? What do you think sets candidates apart in the hiring process at [company]? Do you have any advice for someone looking to break into the [field] industry?

Start with some small chat to make it feel more like a natural conversation and thank them for taking the time to meet with you.
Within the first 10-15 minutes, make sure to give some version of your elevator pitch to introduce yourself, your experience, and your goals.
Be prepared to direct the interview but also let the conversation flow naturally and encourage the interviewee to do most of the talking.
Respect the person’s time. If you agreed on a 20 minute chat, stick to that.
Ask the person if you may contact them in the future if you have more questions.
Ask for names of other people to meet so as to gain additional perspectives.

4. After the Interview

Review and add to your notes while things are still fresh in your mind. Feel free to write down any additional questions you have or couldn’t get to in the interview.
Send a thank you note within 1-2 days to express your appreciation for the time and information given. Mention something specific in your thank you from the interview to show that you are genuine. If you mentioned getting back to them with something that came up during the interview, send that now to show you follow through with what you say.
Keep in touch with the person, especially if you have a particularly nice interaction. If you followed through with some of their advice, feel free to tell them about it and the outcome or if you come across an article that you think they would like, keep the conversation going by sending it to them.

Conclusion

If you’re lucky, the person you interview may offer to refer you or connect you with other people for another information interview. This is all about getting information and creating connections.

Let me know if you found this guide helpful and if there is anything you would add.