DEV Community: Michael Stromberg

How to Create a Memoization Function in JavaScript

Michael Stromberg — Sun, 22 Dec 2024 19:30:54 +0000

What is Memoization?

In software programming, memoization is a technique used to make applications run faster. If you have a function with high time complexity that blocks execution for too long, or your application has a function that is invoked frequently such that a small optimization in time complexity results in a much faster overall runtime, memoization can shorten execution times and improve user experiences.

Outside of software engineering, there are many examples in the real world that are analogous to memoization. Frequently Asked Question (FAQ) pages are a perfect example of where certain questions are asked so often that sites will dedicate resources to preemptively provide those answers to their users so they don’t have to search for them.

How Memoization Optimization Works

In software, optimization often comes in two forms: reducing superfluous complexity or substituting one complexity for another. Memoization optimizes for runtime by utilizing more memory. Therefore, memoization often decreases the time complexity of an algorithm by increasing the space complexity.

Under the hood, the logic is actually quite simple. For any memoized function, we first check if that function has been invoked with the current parameters. If it hasn’t, we compute the resultant value, store the input/output pair in a cache, and return the value from the function. On the other hand, if the function has already been invoked with the given parameters, the resultant value will already be cached. So in this case, the function will simply return the cached value without recomputing.

An illustration of memoization logic

In the illustration above, the left side shows how the basic flow logic of a function invocation while the right side illustrates memoization. Without memoization, the flow logic for each function invocation is identical: invoke, compute, then return. In contrast, with memoization, there is an intermediate step involving the cache. If the function has yet to be invoked with the parameter permutation, the flow logic is: invoke, check cache, compute, cache result, then return. However, if the function has already encountered these parameters previously, the flow simplifies to: invoke, check cache, then return. Notice that the expensive “compute” step is bypassed on the second invocation. That is the crux of memoization; if the function is computationally expensive, memoization will bypass that step on subsequent invocations.

The logic behind memoization is actually quite simple itself, but it builds upon a few important concepts that are fundamental.

Deterministic Functions

In mathematics and computer science, a function is considered deterministic if the function repeatably produces the same result for a given set of parameters. If a function is not deterministic, memoization can’t be used because the cached value would only reflect the first invocation for a given parameter set. A nondeterministic function is one that depends on something that changes to produce its resultant value.

function deterministicFunc(x) {
  return x + 2;
}

function nonDeterministicFunc(x) {
  return x + Date.now();
}

Examples of a deterministic function and a non-deterministic function

In the example above, the deterministicFunc function will always produce the same result for the same given parameter (and the same runtime environment). For example, when deterministicFunc is passed x = 2, it will always return 4. However, the nonDeterministicFunc function doesn’t work the same way. Because the Date.now invocation will return the current timestamp in milliseconds, this function will return a new value each time. Go ahead and try it out; if you’re in a Chrome browser, hit command + option + j to open the dev tools (control + shift + j on a PC), paste in the functions, and invoke them with a parameter.

Function Closures

Function closures are a fundamental pillar of computer science and a powerful feature of JavaScript where an inner function retains access to variables from its outer (enclosing) function, even after that outer function has finished executing. This works because JavaScript functions create their own scope, and closures let inner functions access variables from their parent scope. Closures are crucial for data encapsulation, maintaining state, and creating more sophisticated constructs like memoization.

When a function is returned from another function, it “closes over” the variables in its scope, preserving their values. This behavior enables developers to maintain private variables and state within functions, which is useful for tasks such as caching results or handling asynchronous operations.

function outerFunction() {
  let counter = 0; // This variable is part of the closure
  return function innerFunction() {
    counter++;
    console.log(`Counter value: ${counter}`);
  };
}

const incrementCounter = outerFunction(); // Create a closure
incrementCounter(); // Output: Counter value: 1
incrementCounter(); // Output: Counter value: 2

An example of a function closure in JavaScript

In this example, the outerFunction defines a local variable counter, the innerFunction is returned and maintains access to the counter variable through a closure, and even though outerFunction has finished executing, the counter variable remains accessible whenever incrementCounter is called. Closures are particularly useful for memoization because they allow functions to “remember” previous inputs and outputs, enabling efficient caching.

Higher Order Functions

Higher order functions are those that take one or more functions as arguments, return another function, or do both. This concept is a cornerstone of functional programming, enabling flexible, reusable, and composable code. Higher-order functions treat functions as first-class citizens, meaning functions can be stored in variables, passed as arguments, and returned from other functions.

Higher-order functions and closures are foundational to implementing memoization in JavaScript. They enable memoization by wrapping a function with caching logic without changing its core behavior. A memoization function takes another function as input, adds caching, and returns an optimized version for reuse across multiple scenarios.

function applyOperation(array, operation) {
  // Applies the passed function to each element
  return array.map(operation);
}

// Example usage
const numbers = [1, 2, 3, 4];
const square = (x) => x * x;

const squaredNumbers = applyOperation(numbers, square);
console.log(squaredNumbers); // Output: [1, 4, 9, 16]

An example of a higher order function in JavaScript

Here, the applyOperation function is a higher-order function because it takes another function (operation) as an argument. The operation function is applied to each element of the array using the map method. By passing a specific operation like square, we can easily customize the behavior of applyOperation without changing its implementation.

Memoization Implementation in JavaScript

In software development, we usually try to avoid reinventing the wheel. However, in software interviews, we’re often tasked with doing exactly that. Let’s reinforce our understanding of memoization through JavaScript examples.

A Basic Implementation of a Memoization Function

At its core, a memoization function needs to track if a function has been invoked with the same given parameters previously and return that cached value if it has. Let’s create a function in JavaScript that does exactly that.

function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    } else {
      const result = fn(...args);
      cache.set(key, result);
      return result;
    }
  };
}

There are four main aspects of this function that warrant discussion:

Cache Storage: The Map object is used to store cached results, with keys derived from the function arguments.
Key Generation : The arguments are converted to a unique string key using JSON.stringify.
Cache Check : If the key exists in the cache, the function retrieves and returns the cached result.
New Computations : If the key isn’t found in the Map lookup, the result is computed, cached, and returned.

This approach makes the function reusable and efficient, especially for computationally expensive tasks with repeated inputs.

An Advanced Implementation of a Memoization Function

The simple implementation works great if our function only accepts simple parameters, like primitives. If we want our memoization function to work with more complex parameters like objects, we’ll need to adjust how we handle these parameters.

However, attempting to memoize functions that accept complex data structures as parameters is more complicated than it may seem initially. This is because data structures are usually mutable — they are often used to dynamically store data — and if the output of your memoized function depends on those data structure properties, you’ll need to serialize all of those to see if they’ve changed between invocations.

So, while memoization is not reliable for data structures that are storing data dynamically, there are scenarios where memoization makes sense for object parameters. Examples of this are when you know your object won’t be mutated, or if an object is immutable like when using Object.freeze() for static data. Let’s take a look at the implementation of the enhanced memoization function to handle object types.

function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    let currentCache = cache;

    for (const arg of args) {
      const key = typeof arg === 'object' && arg !== null
        ? arg
        : JSON.stringify(arg);

      if (!currentCache.has(key)) {
        currentCache.set(key, new Map());
      }

      currentCache = currentCache.get(key);
    }

    if (currentCache.has('result')) {
      return currentCache.get('result');
    } else {
      const result = fn(...args);
      currentCache.set('result', result);
      return result;
    }
  };
}

The key improvements of this enhanced version are:

Nested Map Structure : Arguments are stored hierarchically in nested Map objects, avoiding reliance on stringifying objects.
Object Keys : Objects are directly used as keys when possible, leveraging JavaScript’s ability to store object references in Map.
Improved Cache Robustness : Handles complex arguments and avoids issues with JSON.stringify.

Conclusion

Memoization is a powerful programming technique that optimizes function performance by caching the results of expensive computations and reusing them when the same inputs occur. This approach significantly improves efficiency, especially for functions with repetitive and deterministic calculations, by reducing redundant processing.

Memoization is most effective for computationally expensive operations with repeated inputs, such as recursive algorithms or data-heavy tasks. However, it may not be suitable for functions with highly dynamic inputs or when memory usage is a concern, as caching can increase memory consumption.

When working with data structures like Map, Set, or objects as parameters, memoization faces limitations. Cache consistency depends on whether inputs are handled by reference or through serialization. Using references limits reuse to identical instances, while serialization can be computationally expensive and may not handle complex cases like circular references. Understanding these trade-offs helps determine when memoization is the right tool for the job.

The post How to Create a Memoization Function in JavaScript first appeared on Coding Bootcamp Guides.

Solving the “Longest Increasing Subsequence” Problem in JavaScript

Michael Stromberg — Mon, 18 Nov 2024 04:07:46 +0000

Photo by Thomas Serer on Unsplash

Tackling algorithmic challenges is a crucial part of coding interviews, particularly for software engineering roles at top tech companies such as Google, Meta, and Amazon. Although these problems may not represent the daily tasks of an engineer, or reliably forecast long-term performance, thorough preparation remains essential.

Regular practice, familiarity with common problem-solving strategies, and the ability to explain the pros and cons of your solutions are vital for securing job offers in a competitive market or being accepted into a respected coding bootcamp. Mastering time and space complexity analysis, and clearly communicating your approach will set you apart in these evaluations.

The “Longest Increasing Subsequence” Problem on LeetCode in JavaScript

The Longest Increasing Subsequence problem on LeetCode says that: given an integer array nums, return the length of the longest strictly increasing subsequence. In this instance, a subsequence is an array that can be derived from another array by deleting zero or more elements without changing the order of the remaining elements.

For example, given the array [10, 9, 2, 5, 3, 7, 101, 18], one of the longest increasing subsequences is [2, 3, 7, 101], and the length of this subsequence is 4.

Solving the Longest Increasing Subsequence Problem Using A Brute Force Approach

The first approach that comes to mind is an iterative, dynamic programming solution where we compare each element with all previous elements. If the current element is larger than a previous one, it might contribute to forming a longer subsequence. We’ll keep track of the length of the longest increasing subsequence that ends at each index of the given array, and after we finish iterating through every possible subsequence, we’ll circle back and report the length of the largest one we found.

Building a Mental Model for the Brute Force Approach

Sometimes building a mental model for dynamic programming algorithms can be a little difficult. Let’s take a look at a visual representation to make this algorithm more mentally digestible.

A visual representation of a brute force approach to solving the Longest Increasing Subsequence problem

A JavaScript Implementation of a Brute Force Solution to the Longest Increasing Subsequence Problem

Now that our mental model is solidified, let’s see what this looks like in code. I always recommend working through a mental model prior to coding because it removes a layer of complexity while you’re designing your algorithm.

function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;

    const maxSubsequenceLengths = new Array(nums.length).fill(1);

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                const currentMax = maxSubsequenceLengths[i];
                const newMaxCandidate = maxSubsequenceLengths[j] + 1;

                maxSubsequenceLengths[i] = Math.max(
                  currentMax,
                  newMaxCandidate
                );
            }
        }
    }

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

Handle empty array: Our base algorithm isn’t set up to handle an empty nums array parameter, so we’ll add the if statement at the beginning of the function to short-circuit the algorithm and return 0.
Initialize our maximum subsequence counter : Here, we instantiate a new array with a length that matches the length of the incoming nums array. Then, we fill it with 1 values so as to initialize every maximum subsequence length to be 1—the smallest possible subsequence length.
Setting up the iteration parameters : In this part of the algorithm, we set up our loops such that we iterate through the entire nums array, and for each step in that loop, we also march through each item in the array from index 0 up to the current item in the array. So, for each subsequent step in the outer loop, we’re iterating through a large subset of the array.
Conditionally updating the maximum subsequence counter: This is the heart of the algorithm and potentially the most important. We check if the current item from the outer loop is greater than the current item from the inner loop. If so, we know that the longest subsequence is at least as long as one more than the longest subsequence that was possible at the inner loop index. Let that sink in. If the current value is larger than the value at the inner loop index, that means that we can add the new value onto the longest subsequence at the inner loop index. After, we’ll update our counter at that index to be the larger of the existing value there and the length of the subsequence we just calculated.
Final results: Finally, we can find the largest subsequence length in our counter array and return that.

Time and Space Complexity

This solution has a time complexity of O(n²) where n is the number of elements in the input array nums. This is because we have a nested loop: the outer loop runs through each element, and the inner loop compares it with all previous elements.

Solving the Longest Increasing Subsequence Problem Using An Optimized Approach

Although the dynamic programming approach works, there’s an even more optimized solution using a combination of binary search and dynamic programming that can bring the time complexity down even further.

Use a helper array (sub) that will store the smallest possible tail value for increasing subsequences of different lengths. For each element in nums, use binary search to find its position in the sub array and either replace an existing value or append the new value, ensuring that sub always remains sorted.

Building a Mental Model for the Optimized Approach

Again, building a mental model is important step in algorithm design, so we’ll build one in a similar style to prior one so we can compare.

A visual representation of an optimized approach to solving the Longest Increasing Subsequence problem

A JavaScript Implementation of an Optimized Solution to the Longest Increasing Subsequence Problem

Admittedly, it’s a little difficult to illustrate the entire algorithm in our mental model diagram. While we could have easily added the binary search portion of the routine to the illustration, it might have reduced overall clarity and been counterproductive. Instead, let’s look at the code and we’ll address the binary search routine below.

function lengthOfLIS(nums) {
  const sub = [];

  for (let num of nums) {
    // Find the position of 'num' in the sub array using binary search
    let left = 0, right = sub.length;
    while (left < right) {
        let mid = Math.floor((left + right) / 2);

        if (sub[mid] < num) {
          left = mid + 1;
        } else {
          right = mid;
        }
    }

    // If 'num' is larger than any element in sub, append it to the end
    // Otherwise, replace the element at position 'left'
    if (left >= sub.length) {
      sub.push(num);
    } else {
      sub[left] = num;
    }
  }

  return sub.length;
}

sub array We’ll instantiate an array to store our ongoing longest increasing subsequence. As an aside, you’ll notice we instantiate the array using the const keyword instead of let or var. Although, we’ll push items into the array and potentially overwrite items as we go along, we’ll never reassign the variable, and therefore, we can use const for a bit of static testing.
for loop This may seem a bit obvious, but there’s no way around iterating through the entire array. Because each subsequent item in the array could be larger in value, we’ll need to check every single item.
while loop In order to optimize the runtime of this algorithm, we can’t use nested for loops like in our brute force approach. Instead, our inner loop will be a while loop that implements a binary search to find where the current num value would be sorted into our sub array. Because our binary search eliminates half of the items from consideration on each iteration, our while loop will be less than O(n) time complexity.
num placement This is where the magic happens. The sub array keeps track of potential end values of increasing subsequences of different lengths, and by replacing the values using binary search, we efficiently find the best place for each element in the subsequence. This ensures that we are able to maintain a valid increasing subsequence while reducing the overall complexity.

Time and Space Complexity

Time Complexity Because a binary search is performed on n elements, the time complexity of this algorithm is O(n x log n). That is to say, for all n elements of the nums array, we perform an O(log n) operation, and therefore, the total time complexity becomes O(n x log n).
Space Complexity Similarly to the brute force approach, the space complexity is O(n)because we store information of length n—the same length as the numsarray.

Edge Cases to Consider

Empty Array When the nums array is empty (i.e. has a length of 0), the algorithm should return 0. Our algorithms handle this by initializing the sub array as an empty array and returning the length of that array.
All Array Items Are Equal In the event that all items in the nums array for equal (e.g. [7, 7, 7, 7]), the algorithm needs produce 1, since that is the longest subsequence.
Array Contains Negative Numbers Negative numbers are valid, and the algorithm should handle them correctly.

Variants of the Number of Islands Problem

Length of the longest decreasing subsequence Exactly as it sounds, this variant asks you to find the longest decreasing subsequence instead of increasing.
Find the longest increasing subsequence itself, not just the length In this case, the brute force approach will not work and you will need to track the actual subsequence like in the optimized approach.

When To Use Brute Force Versus an Optimized Solution

When solving the Longest Increasing Subsequence problem, the choice between the brute force solution and the optimized solution depends on the context, including the input size, performance constraints, and whether the goal is simply to understand the problem or to solve it efficiently. For large input arrays or where performance is critical, implementing the optimized solution makes sense. If performance isn’t critical and simplicity and clarity are more important, using the brute force solution may be advantageous.

Conclusion

We’ve covered two approaches to solving the “Longest Increasing Subsequence” problem: the dynamic programming solution with a time complexity of O(n²) and the optimized binary search approach that reduced the time complexity to O(n x log n). Both of these approaches use similar memory (O(n)), but which approach you choose depends on your specific scenario. If you’re asked this question in an interview or any other high-pressure scenario, implement the solution that you’re most comfortable with. Happy coding!

The post Solving the “Longest Increasing Subsequence” Problem in JavaScript first appeared on Coding Bootcamp Guides.

Solving the “Number of Islands” Problem in JavaScript

Michael Stromberg — Sat, 19 Oct 2024 17:26:34 +0000

Photo by Cyrus Crossan on Unsplash

Algorithmic problem-solving is central to coding interviews, especially for software engineering roles at major tech companies like Google, Facebook, and Amazon. While these challenges might not fully reflect day-to-day engineering work or predict long-term success, preparing for them is critical.

Consistent practice, recognizing common problem-solving patterns, and being able to explain the efficiency and trade-offs of your solutions are key to landing a job offer in a competitive hiring environment or gaining admissions to a reputable coding bootcamp. Demonstrating a clear understanding of time and space complexity and articulating your approach effectively will help you excel in these assessments.

The “Number of Islands” Problem on LeetCode in JavaScript

The Number of Islands problem on Leetcode asks you to determine the number of distinct islands in a 2D grid, where each island is represented by connected groups of “1”s (land), and “0”s represent water. Two pieces of land are connected if they are adjacent either horizontally or vertically (i.e. diagonal adjacency doesn’t count). The toy problem requires you to count how many separate islands exist in this grid.

Problem Description

Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Solving the Number of Islands Problem Using Depth First Search (DFS)

Since we’ll need to check every cell in the matrix while also comparing the relative positions of cells (i.e. if a land cell adjacent to another land cell), using graph traversal will come in handy. Every cell has adjacent cells, and those cells have their own adjacent cells, so designing this algorithm around a graph structure will be optimal. I find DFS easier to conceptualize and more intuitive than Breadth First Search (BFS), so we’ll begin there.

Building a Mental Model for the Depth First Search Solution

Although graph traversal can be a little intimidating at first, having a strong mental model can make things a lot easier. I like to visualize the algorithm with diagrams.

A diagram illustrating a depth-first search solution to the Number of Islands problem

In our DFS implementation, we’ll iterate through each row of the matrix until we find a land cell — or a cell with a value of “1”. We’ll then increment our island count by one and change that cell’s value to “0” to indicate that we’ve already checked it. Then, we’ll recursively check that cell’s adjacent cells — up, down, left, and right — to see if those cells contain land. We’ll continue to recursively check for land until all directions lead to water.

From there, we’ll continue to iterate through the matrix from where we left off, checking for land along the way. We’ll use the same steps as before when we encounter land, and the algorithm will terminate once we have no cells left to check.

A JavaScript Implementation of Depth First Solution to the Number of Islands Problem

function calculateIsWaterCell(grid, rowIndex, columnIndex) {
  const rowCount = grid.length;
  const columnCount = grid[0].length;
  const isRowOutOfBounds = rowIndex < 0 || rowIndex >= rowCount;
  const isColumnOutOfBounds =
    columnIndex < 0 ||
    columnIndex >= columnCount;
  const isWaterCell =
    isRowOutOfBounds ||
    isColumnOutOfBounds ||
    grid[rowIndex][columnIndex] === '0';

  return isWaterCell;
}

function searchGridForLand(grid, rowIndex, columnIndex) {
  const isWaterCell = calculateIsWaterCell(grid, rowIndex, columnIndex);

  if (!isWaterCell) {
    grid[rowIndex][columnIndex] = '0';

    searchGridForLand(grid, rowIndex - 1, columnIndex);
    searchGridForLand(grid, rowIndex + 1, columnIndex);
    searchGridForLand(grid, rowIndex, columnIndex - 1);
    searchGridForLand(grid, rowIndex, columnIndex + 1);
  }
}

function countIslands(grid) {
  let islandCount = 0;

  if (grid.length > 0) {
    for (let i = 0; i < grid.length; i++) {
      for (let j = 0; j < grid[0].length; j++) {
        const cell = grid[i][j];
        if (cell === '1') {
          islandCount += 1;
          searchGridForLand(grid, i, j);
        }
      }
    }
  }

  return islandCount;
}

Once our mental model is solidified, codifying this algorithm becomes much easier. For clarity, I’ve abstracted out the algorithm logic into three sections:

calculateIsWaterCell This function is solely focused on determining whether or not a cell is a water cell. Most of the logic is concerned with checking if the cell is out of bounds (outside the body of the grid) because the problem states that the grid itself is surrounded by water. The function also checks if the current cell’s value is “0”. One could make an argument that this function should not have knowledge of the grid at all, and the function should be further abstracted. I generally agree with that notion, however, readability is important in a tutorial and excessive abstraction works against that goal.
searchGridForLand Again, we are mixing concerns about grids and what constitutes a water cell here, but this is done for clarity. That aside, we’re primarily focused on recursion with this function. The logic checks for land, and if the current cell is land, it will toggle that cell to be water to indicate we’ve already traversed it and then it will recursively check all four directions for adjacent land. Subsequently, if any of those recursive calls also find land, they will continue down the graph with more recursive calls of searchGridForLand.
countIslands This is the entry point to the algorithm, and it is responsible for counting islands and iterating through the cell matrix. When we do encounter land, we’ll increment our islandCount variable and then recursively check for adjacent land cells.

Time and Space Complexity

Time Complexity The time complexity of this solution is considered O(m × n), where m is the number of rows and n is the number of columns in the grid. For clarity, you can think of this complexity as O(n²) because m and n are effectively equal as they both approach infinity. In the worst case, we may need to visit all cells, and each cell is visited only once, so the complexity is proportional to the number of cells.
Space Complexity This algorithm is considered to have O(m × n) space complexity. Due to the recursion stack used by DFS — particularly if the grid is filled with land cells forming a single large island — the stack depth could equal the total number of cells.

Solving the Number of Islands Problem Using Breadth First Search (BFS)

Breadth First Search (BFS) is an important concept to learn and can be a useful tool in certain situations, but I find it more complicated to understand and unnecessary in most cases. Nonetheless, we’ll take this opportunity to show you the difference and examine its efficiency.

Building a Mental Model for the Breadth First Search Solution

A diagram illustrating a breadth-first search solution to the Number of Islands problem

Similarly to the DFS implementation, we’ll start by iterating through each row of the matrix until we find a land cell (“1”). We also increment our island count at this level, but you’ll notice we check the entire “level” — also sometimes “layer” or “depth” — and we enqueue each of those cells before we dive deeper into them to check their descendants for land.

A JavaScript Implementation of Breadth First Solution to the Number of Islands Problem

function calculateIsWaterCell(grid, rowIndex, columnIndex) {
    const rowCount = grid.length;
    const columnCount = grid[0].length;
    const isRowOutOfBounds = rowIndex < 0 || rowIndex >= rowCount;
    const isColumnOutOfBounds = columnIndex < 0 || columnIndex >= columnCount;
    const isCellWater = 
        isRowOutOfBounds ||
        isColumnOutOfBounds ||
        grid[rowIndex][columnIndex] === '0';

    return isCellWater;
}

function searchGridForLand(grid, rowIndex, columnIndex) {
    const queue = [[rowIndex, columnIndex]];
    grid[rowIndex][columnIndex] = '0';

    while (queue.length > 0) {
        const [i, j] = queue.shift();
        const newCellsToCheck = [
            [i - 1, j],
            [i + 1, j],
            [i, j - 1],
            [i, j + 1]
        ];

        for (let [newI, newJ] of newCellsToCheck) {
            const isCellWater = calculateIsWaterCell(grid, newI, newJ);

            if (!isCellWater) {
                queue.push([newI, newJ]);
                grid[newI][newJ] = '0';
            }
        }
    }
}

function countIslands(grid) {
    let islandCount = 0;

    if (grid.length > 0) {
        for (let i = 0; i < grid.length; i++) {
            for (let j = 0; j < grid[0].length; j++) {
                const cell = grid[i][j];
                if (cell === '1') {
                    islandCount += 1;
                    searchGridForLand(grid, i, j);
                }
            }
        }
    }

    return islandCount;
}

You’ll notice in this implementation that the code for the countIslands and calculateIsWaterCell functions are identical to their respective DFS versions. That is because I purposefully separated concerns and abstracted out the core responsibilities into isolated functions. Now, it makes it easier to swap out the graph traversal logic — the code body inside of the searchGridForLand function — and for others to easily read and digest the algorithm.

Let’s break down the logic piece by piece:

First, we create a bare-bones queue and initialize it with the indices of the current cell we’re examining. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle — where elements are added at the back (enqueue) and removed from the front (dequeue) — ensuring that the first element inserted is the first one to be processed. We also mark this cell as already traversed by setting its value to “0” like we did in our DFS implementation.
Next we loop through the contents of the queue, check all adjacent cells for land, and enqueue any new land cells we find along the way. Since our logic is constructed using a while loop, we can keep enqueuing more cells to check and the algorithm will continue until the queue is not empty. In this portion of the function, we also dequeue each cell as we go along so that are while loop knows when to conclude and we also mark visited cells as water like before.

Time and Space Complexity

Time Complexity Similarly to the DFS solution, the time complexity of this solution is considered O(m × n), where m is the number of rows and n is the number of columns in the grid. This is because we still need to iterate through all of the cells, and there isn’t any reason to believe that checking each level completely first before examining their descendant nodes would be any faster.
Space Complexity This algorithm is considered to have O(m × n) space complexity. Due to the recursion stack used by DFS — particularly if the grid is filled with land cells forming a single large island — the stack depth could equal the total number of cells.

Edge Cases to Consider

Empty Grid If the grid is empty, the number of islands should be 0. This is handled by checking if the grid length is 0 at the start.
All Water If the grid contains no “1”s, the function should return 0 since there are no islands to count.
All Land If the grid consists entirely of land, the algorithm should handle this case by correctly counting either one island.

Variants of the Number of Islands Problem

Number of Closed Islands A close variant of the Number of Islands problem is where an island is only counted if it is completely surrounded by water on all four sides. This is an awesome variant to practice because it involves using the returned values from the recursive calls.
Number of Distinct Islands Another variant where islands that have the same shape (regardless of their orientation) are considered identical and counted only once.

When To Use Depth First Search Versus Breadth First Search

Choosing between DFS and BFS depends on the problem at hand and the structure of the graph or tree you are traversing. DFS is well-suited for problems where you need to explore all possible paths or “dig deep” into one branch before backtracking. It’s commonly used in scenarios like finding connected components in a graph, solving maze or puzzle problems, or performing topological sorting on a Directed Acyclic Graph (DAG). A real-world example is web crawling, where DFS can explore a website’s structure deeply before moving on to other pages.

On the other hand, BFS excels when the shortest path or minimum number of steps is important. BFS explores nodes level by level, making it ideal for shortest path problems in unweighted graphs, such as finding the minimum distance between two points in a grid or map. It’s often used in real-world scenarios like GPS navigation systems, where you want the shortest route to a destination, or in social network analysis to find the shortest connection between people. In general, use BFS when proximity is important and DFS when deep exploration or pathfinding is needed.

Conclusion

This problem is an excellent introduction to graph traversal techniques like DFS and BFS, often used in interviews to test a candidate’s understanding of recursive algorithms and grid-based problem-solving.

The post Solving the “Number of Islands” Problem in JavaScript first appeared on Coding Bootcamp Guides.

Solving the “Two Sum” Problem in JavaScript

Michael Stromberg — Thu, 03 Oct 2024 23:28:50 +0000

Photo by Ben Wicks on Unsplash

Algorithm design plays a crucial role in coding interviews, especially for software engineering roles. While some companies place more emphasis on algorithmic challenges than others, they are particularly important for larger tech companies like Google, Facebook, and Amazon. Even though solving algorithm problems during an interview may not fully represent your day-to-day performance as an engineer or predict long-term career success, it’s essential to prepare thoroughly.

To succeed, you must practice regularly, familiarize yourself with common patterns and principles, and be able to articulate the efficiency and trade-offs of your solutions. Understanding how to approach these problems, explain your reasoning, and discuss time and space complexities is a key component of standing out in competitive technical interviews.

The “Two Sum” Problem on LeetCode in JavaScript

The Two Sum problem is one of the most popular coding interview questions and is a great introduction to working with arrays, hashing, and optimization in algorithms. The problem is defined as follows:

Problem Description

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.

Solving the Two Sum Problem Using Brute Force

Building a Mental Model for the Brute Force Solution

There are multiple ways to solve the Two Sum problem, but the most optimal solution involves using a hash map (or an object in JavaScript) to track the indices of the elements we’ve seen so far, allowing us to check for the complement of each number efficiently. We’ll walk through this solution as well as the brute force solution for comparison.

A diagram illustrating a brute force method to solving the Two Sum problem

Much like all brute force method solutions, this implementation indiscriminately iterates through every number pair combination. At each iteration, the sum of each pair will be checked to see if it equals target, and if it does, the algorithm should return the indices of those two numbers.

The idea is simple enough, so let’s take a look at an JavaScript implementation of this solution.

A JavaScript Implementation of a Brute Force Solution to the Two Sum Problem

Let’s walk through the code. In this implementation, I chose to use for loops to iterate through the array of numbers. While it may be considered more idiomatic to use array methods like array.prototype.forEach here, the 2nd loop in this case is looping through a smaller and smaller subset of the original nums array each iteration. This means that I would need to perform some operation on the array to shorten it on each step, or I would need to iterate through the entire array in the second loop. Both of these add time complexity.

Note that you could potentially break out of the nested forEach calls by throwing an exception, but I would argue that is more complex and difficult to understand than the for loop solution, and therefore defeats one the main purposes of idiomatic programming.

Time and Space Complexity of the Brute Force Solution

With regards to time complexity, this solution is considered O(n²) because it the typical and worst-case scenarios, the algorithm needs to iterate through the length of the nums array in a nested fashion. Even if our target pair is found midway through the array, as n approaches infinity, n / 2 is still infinity. While this is definitely a brute force solution, one benefit of this solution is that its space complexity is constant, or O(1).

Solving the Two Sum Problem Optimized for Time

Now, that we’ve worked through the brute force solution, let’s examine an optimization to speed up the algorithm. If you’re in an interview and you have time left after solving a toy problem, your interviewer will sometimes ask you if there is a more efficient way to implement your algorithm. It’s always a good idea to be prepared to discuss the efficiency of your solution and the possibility of making it better.

Building a Mental Model for the Optimized Solution

Here, our mental model requires us to visualize how our map works. On each iteration through our array, we do a lookup on our map for the matching value needed to sum to our target value. If it doesn’t exist, we’ll add the current value and its index to the map, and continue on with the next array iteration. We continue this process until we find a matching sum. When we find it, we return the corresponding indices.

A JavaScript Implementation of a Brute Force Solution to the Two Sum Problem

Let’s analyze the JavaScript implementation to make sure all of the details are clear.

Create a map object that we can use to map values to indices. As described previously, we’ll use this to track which values we’ve already encountered.
Iterate through the array, and for each number, compute the “complement” (target — num). The compliment is the value needed to pair with the current number so that the sum equals the target.
Check if the complement exists in the map. If it does exist, return the current index and the stored index of the complement. However, if it doesn’t exist, add the current number and its index in the map for future reference.
Continue this process until you find the pair.

Time and Space Complexity of the Optimized Solution

This approach leverages the efficiency of hash maps, allowing us to solve the problem in one pass through the array and reducing the time complexity of our algorithm to O(n).

However, this improved time efficiency comes at a cost. Since we are storing a reference to the current index for every iteration that doesn’t produce a match, we are increasing our space complexity to O(n), or linear.

Edge Cases to Consider

Whether working on production code or solving toy problems during an interview, it’s always important to handle edge cases.

If no solution exists The problem explicitly states that there is always exactly one solution, so we don’t need to handle the case of no solution. However, if this weren’t guaranteed, you should consider handling that scenario. This type of variation might be incorporated in an interview.
Negative numbers and zeroes The algorithm handles negative numbers and zeroes naturally since it treats all integers the same when calculating the complement.
Duplicate numbers If the array contains duplicate numbers, the algorithm will still function correctly as it tracks indices, not just values. Keep in mind, it will report the first occurrence of the solution.

Variants of the Two Sum Problem

The Two Sum problem has several common variants, each of which requires slight modifications to the approach. Below are some examples you should consider practicing, or at the vary least, conceptualize how you would solve them as a thought exercise.

Two Sum With the Input Array Sorted In this variant, the input array is already sorted, allowing us to use a two-pointer technique to reduce the space complexity to O(1) while maintaining the linear time complexity.
Three Sum Here, the task is to find three numbers in the array that add up to a target. This can be solved using nested loops like our brute force scenario or a two-pointer technique that can obtain O(n²) time complexity.
Four Sum Similar to the Three Sum problem, the Four Sum problem can be solved using the same techniques. The time complexity for the optimal solution is O(n³).
Two Sum Less Than K Instead of finding an exact sum, this variant asks for the pair whose sum is the largest but less than a given target K. It can also be solved using sorting and a two-pointer approach.

When To Use Brute Force Versus the Optimized Solution

Ultimately, deciding which approach to use depends on your specific scenario. If you’re developing a solution in a real-world, production application, you should consider the bounds of your problem. How large can n be? Is speed critical in this feature or are will this algorithm run in the background? Does the elegant solution compromise readability for your other developers that may need to work on your code in the future?

Most frequently, however, you’ll only encounter this particular challenge in a contrived environment like an interview. In this case, do what you feel confident in completing in the short timeframe that you have. If you don’t feel comfortable implementing the time-optimized solution, state that to your interviewer. Complete the brute force solution and explain that you believe you can optimize that solution to reduce time complexity by tracking the values you’ve already iterated through. This will go a long way with your interviewer.

Conclusion

The Two Sum problem, like many toy problems, can be solved in multiple ways. It’s worthwhile to try implementing a brute force solution as well as a more optimized one. Trading off space efficiency for time efficiency is a common practice in toy problems and in production code, so familiarizing yourself with the practice will set you up for success.

The post Solving the “Two Sum” Problem in JavaScript first appeared on Coding Bootcamp Guides.

Recursion Explained in JavaScript

Michael Stromberg — Sat, 07 Sep 2024 19:50:05 +0000

Image generated using Google Gemini

Recursion is a programming technique where a function calls itself to solve a particular problem. It’s especially effective for problems that can be divided into smaller, similar subproblems. By breaking down a complex problem in this way, recursion can often lead to elegant and concise solutions.

A recursive function repeatedly calls itself with smaller versions of the problem until it reaches a simple, solvable base case. This self-referential approach is a powerful tool for tackling problems that have a recursive structure.

A Real-Life Analogy of Recursion

Photo by Alicia Christin Gerald on Unsplash

While the concept can be challenging to grasp, recursion can be likened to solving a jigsaw puzzle. Some puzzle solvers might start by connecting a few pieces together that have similar colors, and they might do so until they have a few groupings of puzzle pieces. They might then connect those groupings into one larger grouping. This strategy can go on until the entire puzzle is completed.

Recursion Fundamentals

For some, it can be easier to learn by reading code, but before we can demonstrate recursion by programming out an example, we need to explain some fundamental concepts of recursion.

In recursion, “cases” are the different scenarios that dictate how a recursive function behaves. These cases logically guide the function on whether to continue recursing or to terminate. Correctly identifying and implementing these cases is essential to ensuring that a recursive function works as intended and doesn’t fall into an infinite loop.

There are typically two primary cases in recursion: the base case and the recursive case.

Base Case

The base case is the condition under which the recursive function stops calling itself. It is the simplest instance of the problem that can be solved directly without further recursion, and it is critical because it prevents infinite recursion by providing a stopping point. The base case stops the recursion when the problem has been reduced to its simplest form or has reached the end of the sequence.

Recursive Case

The recursive case is the condition under which the function continues to call itself with modified arguments. In these scenarios, the function makes progress towards the base case by simplifying or reducing the problem with each recursive call. The recursive case helps to break the problem into smaller sub-problems that have the same structure as the original problem, but with simpler or reduced inputs.

Recursion in JavaScript

Let’s recreate the Math.pow method, which calculates the power of a number, using recursion in JavaScript. The Math.pow(base, exponent) function computes the result of raising thebase value to the power of an exponent.

Recursive `Math.pow` Implementation

To implement this method using recursion, we’ll use two main cases:

Base Case: If the exponent is 0, the result is 1 because any number raised to the power of 0 is 1.
Recursive Case: Multiply the base by the result of the function with the exponent decremented by 1.

Here’s the JavaScript implementation:

function recursivePow(base, exponent) {
  if (exponent === 0) {
    return 1;
  } else if (exponent < 0) {
    return 1 / recursivePow(base, -exponent);
  } else {
    return base * recursivePow(base, exponent - 1);
  }
}

Explanation of the Code

Base Case: If the exponent is 0, the function returns 1. This stops the recursion from continuing indefinitely.
Edge Case: If the exponent is negative, the function inverts the base (i.e. calculates 1 / base) and calls itself with the positive value of the exponent. This allows the function to correctly compute the result for negative exponents.
Recursive Case: If the exponent is positive and greater than 0, the function multiplies the base by the result of calling itself with the exponent decremented by 1. The decrementing by one is critical because this causes the recursive calls to home in on base case (i.e. reducing the exponent by 1 until it reaches 0).

How the Recursion Unfolds

A flow diagram visualizing a recursive implementation of Math.pow

Let’s walk through an example where we invoke the recursive power function with a base of 2 and a power of 3 (recursivePow(2, 3)). Note, in the illustration above, I’ve omitted the edge case logic for visual clarity.

recursivePow(2, 3) returns 2 * recursivePow(2, 2)
recursivePow(2, 2) returns 2 * recursivePow(2, 1)
recursivePow(2, 1) returns 2 * recursivePow(2, 0)
recursivePow(2, 0) returns 1 (base case)
As the call stack unwinds and the function invocations return their values, the result is equivalent to: 2 * 2 * 2 * 1 = 8.

This implementation of Math.pow using recursion is a great way to illustrate the power of recursion by breaking down problems into smaller sub-problems, solving them recursively, and combining the results to obtain the final solution.

The Pros and Cons of Using Recursion

Pros of Using Recursion

Optimal Technique: For problems that involve manipulating or iterating through dynamic data structures—such as traversing through a tree or linked list—or while designing solutions that involve sorting or using a divide-and-conquer strategy, recursion naturally lends itself to elegant implementations in these scenarios.
Brevity: Recursion can often require fewer lines of code compared to their equivalent iterative solutions, which can make the codebase less verbose and cleaner.

Cons of Using Recursion

Performance Overhead: Recursion can be less memory-efficient than iterative solutions due to the overhead of multiple function calls. Each recursive call adds a new frame to the call stack, which can lead to excessive memory usage and a higher space complexity.
Risk of Stack Overflow: Anyone first learning about recursion has probably caused a stack overflow. If the recursion depth becomes too deep, it can lead to a stack overflow error, especially in languages with limited stack size. This happens when there are too many nested function calls before reaching the base case. While tail call optimization —where the recursive case is in the tail position and therefore could optimized to not grow the call stack—few JavaScript engines have implemented support for this ECMAScript 6 feature.
Debugging Difficulty: Recursive functions can be harder to debug and trace, especially if the base case is not correctly defined, leading to infinite recursion.

When to Use Recursion

Recursion is particularly useful when dealing with problems that have a natural recursive structure, such as:

Tree Traversal: Traversing hierarchical data structures like binary trees or graphs is more intuitive with recursion.
Divide and Conquer Algorithms: Algorithms like QuickSort and MergeSort benefit from recursion as they divide the problem into smaller subproblems.
Dynamic Programming: Some dynamic programming problems, such as calculating Fibonacci numbers, can be solved using recursion (though they may require memoization to optimize performance).

Conclusion

Recursion is a powerful tool in a programmer’s toolkit that allows for elegant and concise solutions to complex problems. However, it’s essential to understand when and how to use recursion effectively, considering both its advantages and potential pitfalls. By carefully structuring recursive functions and being mindful of base cases and stack depth, you can harness the full potential of recursion in your software projects.

If you enjoyed this article, check out How to Build a Hash Table in JavaScript.

The post Recursion Explained in JavaScript first appeared on Coding Bootcamp Guides.

10 Things I Learned as a Coding Bootcamp Grad

Michael Stromberg — Mon, 02 Sep 2024 22:01:37 +0000

Photo by Hack Capital on Unsplash

I was working in the hard disk drive industry as a Senior Research and Development Engineer when I knew that I wanted to work on software. I had a degree in Mechanical Engineering and an established career with six years of experience, but the idea of switching careers this late in the game was daunting. Could I really handle going back to school? Is it a bad idea to leave my old career behind and start again from the beginning? These are questions that were racing through my head as I was trying to figure out my future.

I needed to figure out what it is that I wanted, and only then figure out how I was going to get there.

I decided to make the switch, but it wasn’t easy. Big life decisions require lots of thought and research, but they also require you to follow your heart. My background in engineering prepared me for problems of this magnitude. I had learned over the years that the best way to tackle a large project or problem is to break it down into its components. And if possible, make these components independent of each other so that you can work on them separately.

So I decided to split up my large, daunting decision into two smaller, manageable decisions. I needed to figure out what it is that I wanted, and only then figure out how I was going to get there. I wanted to make a career out of working on software projects I cared about. So once I decided that’s what I was going to do, a huge weight was lifted off of my shoulders. I was now energized to figure out how I was going to reach that goal.

Fast forward to now, I’m a Senior Software Engineer with about 5 years of experience under my belt. At the time, my journey to becoming a software engineer by attending a coding bootcamp was very new and uncommon. Today, it’s a much more popular route, and so I’d like to share a few things I learned along the way.

Photo by Philippe Bout on Unsplash

1. Bootcamps can help you learn what you’re capable of

Throughout my life, I’ve always pushed myself to work hard and achieve my goals. I graduated with honors in three years with my Mechanical Engineering degree. I started an apparel printing small business for fun while in grad school. I successfully flipped a property with no prior experience in carpentry or real estate. But completing the Hack R eactor bootcamp may have been the most challenging of them all.

On average, I was in class or studying for 12 to 14 hours per day, 6 days per week, for 3 months straight. Every 2 days we learned about a new technology and how to use it. It was mentally and physically exhausting, while also testing you emotionally. Being away from your friends, family, and normal life for 3 months is no joke. Even if you’re doing a full remote bootcamp, you have almost no free time.

Bootcamps put you under somewhat artificial pressure by using aggressive deadlines and pushing lofty goals. This pressure will make or break you. I’ve seen a few people fold under the pressure, but for the most part, students are generally able to rise to the challenge and come out well-equipped to handle anything.

Photo by Noah Silliman on Unsplash

2. Bootcamps are not for everyone

Not everyone is meant to be a software engineer, and I think that needs to be said. While I think that given enough time and resources everyone can learn to code, that doesn’t mean that everyone should. Being a software engineer means shifting your mindset to programmatic thinking. If that’s a big, unnatural shift for you, you’re probably not going to have a smooth career trajectory.

Even more so, not everyone is going to be able to successfully complete and thrive in a coding bootcamp. This is because as I mentioned before, bootcamps are physically, mentally, and emotionally demanding. This type of fast-paced, rapidly changing environment can be difficult in general, not just for people trying to break into software development. Some current software engineers wouldn’t thrive in this type of scenario, and similarly, if this format were applied to a different profession, I think it would also prove to be challenging for many.

The inherent complexity of software engineering curriculum combined with the strenuous nature of the bootcamp format produces an entirely new dimension of education difficulty. It’s not for everyone, but for whom it does appeal to, it can easily be the best option to crack into software development.

Photo by Siora Photography on Unsplash

3. Bootcamps don’t really teach you much and that’s okay

Syllabi vary from bootcamp to bootcamp, but to become a passable software engineer, you have to code. A lot. You have to code all day, every day. That’s one thing that all bootcamps have in common: they know how much you need to code. That doesn’t leave a lot of time for lecturing, one-on-one tutoring, or much of anything else.

Hack Reactor was structured with 2-day “sprints” for the first half of the bootcamp. For the most part, the beginning of each sprint began with a short lecture where a new technology or concept was introduced. The rest was coding. And these introductions weren’t deep dives, they were just enough to get you going or to point you in the right direction. The value of the bootcamp isn’t in its lecture time or its world-renowned staff. The primary value is derived from two different sources: the brand name and the power to produce autonomous engineers.

At first, the brand name didn’t mean much. Without a Computer Science (CS) degree, you were going to have a difficult time getting an interview anywhere. As bootcamps kept producing quality engineers, the brand name became another layer of authentication. Now employers know if you graduate from Hack Reactor, you’ve been put through the wringer.

Given enough time and resources, you can learn anything.

Bootcamps can help you become autonomous. Along the journey you’ll get stuck, you’ll feel lost or burnt out, and you’ll likely get a heavy dose of impostor syndrome. But with small nudges in the right direction, you’ll realize the answer is always in the code, you’ll be able to Google your way out of dead-ends, and you’ll start to use computer science principles to write better code. At the end of the bootcamp, you’ll start to understand that given enough time and resources, you can learn anything.

Photo by Randy Fath on Unsplash

4. Imposter Syndrome is real and never really goes away

Most people will experience imposter syndrome at some point in their lives. There will always be someone smarter or who knows the subject matter better than you, and it will make you feel like an imposter. Bootcamps are no exception. In fact, they are little imposter syndrome factories.

Bootcamps help you become comfortable with being uncomfortable.

The nature of a bootcamp is to move fast and figure things out as you go. So you’re essentially guaranteed to feel uncomfortable, and that’s by design. There is always something else to learn, and the assignments always have stretch goals for you to take on if you finish early. Bootcamps help you become comfortable with being uncomfortable.

So when you land your first job and all of the engineers around you know more than you, you feel like an impostor. But you don’t sweat it because you’ve been there before and you can handle much more than being a little uncomfortable. Imposter syndrome doesn’t go away, it just changes its appearance.

Photo by Markus Spiske on Unsplash

5. New software technologies emerge often and curriculum needs to adapt to keep up

Getting a traditional university Computer Science degree is a great way to land a software engineering job. They help you build a strong technical foundation from the ground up, and the prestige associated with several of the programs out there will give you a leg up on the competition.

However, universities move at the speed of universities: slow. To be accredited, colleges have to teach certain curriculum standards and meet other comprehensive requirements. CS programs also don’t typically have a lot of incentive to innovate and reevaluate their standards frequently. They historically only really compete amongst other university programs, and the prestige of a program is often established by its research and famous faculty.

Coding bootcamps operate on a different model. They look to fill the void that traditional CS programs left behind by teaching and stressing technologies that are often only touched upon in elective classes at university. The general CS degree model is to teach fundamentals and use optional elective classes to explore new technologies and trends. Bootcamps invert that model. They stress new technologies and trends and only briefly touch upon fundamentals. This model has proven to be successful because bootcamp graduates:

have proven they can flourish in a stressful environment,
have tons of hands-on experience with in-demand technologies, and
are entering a field that has a rapidly growing demand for their skillset.

Photo by Ethan Sykes on Unsplash

6. Some bootcamps will fail you and kick you out

When I attended Hack Reactor’s onsite bootcamp in San Francisco, I had no idea you could fail and get kicked out. I knew there was a midterm exam at the halfway point of the course, but I didn’t know the gravity of the situation.

Along the way, I saw some of my classmates burn out from the extreme pace of the program. I saw another get sick, miss one day, and be so far behind that he never caught up and ended up dropping out. I saw another classmate be told that she didn’t have what it took to succeed in interviews, failed after the midterm exam, only to be reinstated after she complained to them about their assessment of her.

Overall, I had a great experience at Hack Reactor, and the program went a long way to set me up for success afterward. However, it was frankly unethical to not emphasize the possibility of failure and expulsion from the program before we accepted our invitations. Hopefully, they’ve changed their process and this is no longer a problem.

Photo by John Schnobrich on Unsplash

7. Communication is key

Software engineers are often portrayed in mainstream media as introverted lone wolves that exude a quiet genius as they work on cutting-edge systems. While that may be accurate in some cases, that couldn’t be further from the truth for the majority of software engineers. Yes, a disproportionate amount of software engineers might be introverted, but that doesn’t mean they don’t have to effectively communicate. Communication is essential in software engineering, and successful coding bootcamps are acutely aware of this.

The first half of the Hack Reactor program is entirely pair programming, where they take the “driver and navigator” approach. This helps you practice translating your thoughts to speech and also translating someone else’s direction into code. This provides you the opportunity to practice critiquing someone else’s work which can be difficult to do without stepping on toes or hurting egos.

The second half of the Hack Reactor program consists of mostly group projects. You get to establish team member roles, dole out responsibilities, practice an effective version management workflow, and many other aspects of working on a team. There is a big difference between working by yourself on a project and working on a team, and in most professional settings you’ll be working on a team.

Additionally, all along the way, you’re practicing whiteboarding. The practice of simultaneously thinking about how to solve a problem, verbalizing those thoughts, and writing them on a whiteboard feels very unnatural. Hack Reactor provided lots of whiteboarding practice time which not only helped prepare me for interviews but made me a more effective communicator.

Photo by Scott Graham on Unsplash

8. Outcomes are just as important as learning to code

Don’t get me wrong, it will be nearly impossible to land a software engineering job if you don’t know how to code. But let’s consider the scenario where two programmers land entry-level job offers at similar companies. The first is a very talented programmer but doesn’t know their worth nor is an effective negotiator. The second programmer is an average entry-level developer but has been coached on their worth and compensation negotiation. Now let’s imagine they accept approximately the same compensation package as the other. Would you consider this a success for the talented programmer?

Outcomes are just as important as learning to code. By reframing the goal from “becoming a software engineer” to “becoming an appropriately compensated software engineer”, bootcamps can set you up for long-term success that you didn’t even know you cared about.

Photo by Matt Duncan on Unsplash

9. The bootcamp is just the beginning

Graduating from a coding bootcamp was one of the most validating experiences I’ve had in my lifetime. It took a lot of willpower, and I assumed a lot of risk, but it paid off exactly how I imagined it. However, the bootcamp was just the beginning.

Most bootcamp students are looking to land a job after they graduate. Software engineering interviews are some of the most stressful and comprehensive interviews in the job market today. You’ll likely have algorithm questions, whiteboarding, system design questions, and behavioral interviews just to start. You might have take-home projects, purposefully arbitrary riddle-like questions, and much more. This means that you have to study a lot. Bootcamps often prepare you for these sorts of interviews, but it takes practice to become good at them.

Even after you land a job, you’re likely still an entry-level engineer with zero years of experience and a porous knowledge of computer science fundamentals at best. Your intense journey will continue well into your first year on the job. You’ll need to strengthen your core understanding of well-established programming principles that you only truly understand once you have experience not following them. Concepts like Don’t Repeat Yourself (DRY), Single-Responsibility Principle (SRP), and Single Source of Truth (SSOT) are just a few that don’t really hit home until you’ve seen their benefits take shape firsthand.

Things change once you get a year of experience under your belt. A tidal wave of recruiters will drop upon you like you couldn’t imagine, and lots of doors will open for you. You’ve been battle-tested and are starting to proactively learn and improve your skillset like a more senior engineer. But after all of this, your journey is still ongoing. Software engineers are always learning and keeping up with the latest technologies and trends.

Photo by Simon Abrams on Unsplash

10. Coding bootcamps are here to stay

When I first started my journey to become a software engineer, I was very skeptical of coding bootcamps. How could one possibly learn enough from an unaccredited school to become a software engineer in 3 months? How could bootcamp grads compete with candidates who have 4-year computer science degrees? It turns out that the answer to both of those questions is “demand”.

Software is always on the cutting edge and often disrupting the status quo. New technologies and patterns emerge all of the time. Just during my short time on this journey, I’ve already seen the rise of Single-Page Applications, Microservices, Cryptocurrencies, Non-Fungible Tokens (NFTs), and Micro-Frontends just to name a few. The rise in these new technologies means there must also be a proportional rise in demand for people to develop using those technologies. If the demand isn’t being fulfilled by traditional routes, alternative education solutions will arise to fill in that void.

Bootcamps are also a part of a larger trend of moving away from universities and their traditional education models. Universities are expensive, bulky, and generally slow to react to the latest demands. Sure they develop new curriculum and periodically review their standards, but software moves much faster than most other industries. On top of that, universities force you to satisfy several different general education requirements. Maybe these requirements help you become a more well-rounded human being and give you a perspective you might not otherwise achieve in your lifetime. But is it absolutely necessary to become a software engineer? No, it’s not. The more economical solution to meet the growing demand is to train people directly in the areas they need to learn to get a job. This vocational school approach is gaining more popularity as universities continue to become financially out of reach for most people.

Conclusion

Bootcamps can help you transform your career in a way that hasn’t been seen before. They move fast and work along the cutting edge of the software engineering industry. Bootcamps are fueled by the rising demand for software engineers that isn’t being satiated elsewhere. While not for everyone, they can provide a more logical and economical approach to education than you might otherwise be afforded.

If you’re thinking about joining a coding bootcamp and are starting to study, check out some of these tutorials.

The post 10 Things I Learned as a Coding Bootcamp Grad first appeared on Coding Bootcamp Guides.

Understanding Imperative vs. Declarative Programming in JavaScript

Michael Stromberg — Thu, 22 Aug 2024 04:28:33 +0000

Photo by Markus Spiske on Unsplash

In the world of software engineering, understanding different programming paradigms is crucial for writing efficient and maintainable code. One of the most fundamental paradigm decisions to make is the choice between using imperative versus declarative programming. While both approaches can achieve the same outcomes, they do so in fundamentally different ways. We’ll explore the differences between these two patterns, with a focus on JavaScript, and provide examples to illustrate the pros and cons of each.

Imperative vs. Declarative: A Real World Example

Understanding the benefits and drawbacks of these programming concepts is best achieved through hands-on experience. Imagine the challenges of debugging complex, imperatively written code, or the frustration of navigating over-engineered, overly abstract solutions. While these experiences can be invaluable, a real-world analogy can provide a helpful starting point for understanding the differences between imperative and declarative programming.

The first analogy I heard to describe the imperative/declarative relationship was using an automobile’s air conditioner control panel, so let’s explore that in depth.

Imperative Design of an Automobile A/C Control Panel

1970 Chevrolet A/C Control Panel | Source: ChevyHardcore.com

Description: In the past, some cars’ A/C controls used imperative design, where the user set a fan level, selected a vent, and decided a heating/cooling level.
Usage: Using this system isn’t too complicated, but it requires an understanding of how all three settings work and how different combinations of settings translate to getting the car to the desired temperature. Not only that, but if the weather or conditions change, the user needs to adjust the settings according. If the weather gets colder or hotter, or if the driver takes a weekend trip out of town, those settings might not be appropriate. Heating the car while on a trip to the desert or cooling the car in the cold mornings don’t make much sense.
In other words: The user tells the car how to cool or heat the vehicle.

Declarative Design of an Automobile A/C Control Panel

A Tesla Model 3 Control Panel | Source: Motor Trend

Description: Modern cars, like the Tesla Model 3, have more declarative temperature controls. While the user may dive in and adjust the A/C settings more granularly, the main control is a just a left arrow, a right arrow, and the temperature display.
Usage: By providing controls to adjust the temperature, the user gets to focus on the desired output rather than the underlying mechanics. The user sets the cabin temperature and the car’s sensors and controllers will adjust the underlying settings to maintain the desired output. The user only needs to be concerned about concepts they understand, like comfortable temperatures, and can allow the car to be concerned with vents, fans, and HVAC.
In other words: The user tells the car what temperature they want.

What is Imperative Programming?

As discussed above in the analogy, imperative programming is a paradigm that focuses on how to achieve a particular task. It involves explicitly giving the runtime a sequence of commands or steps to follow in order to reach the desired outcome. In imperative programming, you often define the control flow and manage the state of your program as you go.

What is Declarative Programming?

Declarative programming, on the other hand, focuses on what you want to achieve rather than the intricate details of how to achieve it. In this paradigm, you describe the desired outcome, and the underlying system takes care of the rest. The control flow and state management — the parts of the algorithm that can be made generic and reused elsewhere—are often abstracted away from the algorithm at hand.

An Example of Imperative Programming in JavaScript

Let’s look at a classic example, one that many beginning programmers learn in their early software journeys. Say we want to sum all the numbers in an array. An imperative approach in JavaScript would look like the following:

An example of imperative code written in JavaScript

In the example above, we explicitly define every step of the algorithm:

Initialize a sum variable
Loop through each number in the array
Add each number to the sum

An Example of Declarative Programming in JavaScript

Let’s look at a declarative approach to achieve the same desired output. Using the same example of summing numbers in an array, a declarative approach in JavaScript might use the reduce method on the array prototype:

An example of declarative code written in JavaScript

Here, instead of describing the steps to achieve the sum, we declare that we want to reduce the array to a single value by summing its elements. The reduce method abstracts away the loop and state management.

Pros of Imperative Programming

Control: You have precise control over the flow of your program, which can be useful in complex scenarios where you need to manage the state closely.
Performance: Imperative code can sometimes be optimized for performance, as you can fine-tune every step of the process.

Cons of Imperative Programming

Verbosity: Because you must define each step, imperative code can very quickly become verbose, more difficult to read, and even more difficult to code review. These difficulties compound as complexity increases.
Error-Prone: Managing the state manually can lead to bugs, particularly in complicated programs or when operating in lower-level programming languages.
Testing Difficulty: Writing unit tests can sometimes become, by definition, impossible because concerns are intermixed.

Pros of Declarative Programming

Simplicity: Declarative code is often more concise, easier to understand, and easier to read, as it abstracts away the underlying mechanics.
Maintainability: Because you’re focusing on what you want to achieve, the code is typically easier to maintain and less prone to bugs.
Reviewability: Declarative code can be more readable, especially for those who are familiar with the abstractions used. This can make it much easier for code reviews.
Testability: Writing declarative code often involves separating concerns. This allows for individual features to be isolated and tested easily.

Cons of Declarative Programming

Less Control: You have less control over how the task is executed, which can be a drawback if you need fine-tuned performance optimizations.
Over-Abstraction: The abstractions provided by declarative methods might introduce overhead or may not be suitable for all scenarios, particularly when performance is critical.

Conclusion

Choosing between imperative and declarative programming is not a simple choice and often involves consideration. Imperative code can give you a lot of control but often at the expense of simplicity, abstracted code that easy to read and maintain. When you need precise control or performance is an primary focus, an imperative approach might make sense. Most other times it probably makes the most sense to use a declarative approach that can lead to cleaner code. With the advent of bundlers, minification, and other optimization tools, small performance improvements become less impactful. As developers, it’s beneficial to be versatile and comfortable with both paradigms, using each where it best fits the problem at hand.

The post Understanding Imperative vs. Declarative Programming in JavaScript first appeared on Coding Bootcamp Guides.

How to Build a Hash Table in JavaScript

Michael Stromberg — Fri, 02 Dec 2022 22:35:59 +0000

Photo by Z on Unsplash

Whether you’re interviewing for an entry-level software engineering position or building enterprise software at scale, data structures are going to be integral to your success. They are a fundamental pillar of programming and can sometimes be a little tricky to navigate. Data structures are like the tools in your toolbox, you need to know how each tool works in order to decide which one is appropriate for your use case.

JavaScript rose to popularity by being the de facto scripting language of web browsers from very early on. As such, JavaScript was not a fully featured programming language but rather created to add a little bit of dynamic interaction to websites. Its popularity then exploded after cross-JavaScript runtime environments like Node.js allowed developers to build native applications outside of the browser. JavaScript evolved as its use cases evolved, so as time went on, JavaScript began expanding its native data structure support.

While it doesn’t have a native implementation of a pure hash table, JavaScript has a Map class that has similar characteristics. However, the hash table is an incredibly important data structure in software engineering, and understanding how it works will help be essential to have a successful career in software development.

Hash Table

A hash table, also known as a hash map, is a data structure that maps keys to values. They use hashing functions to do the mapping, and in some implementations, the keys can be any arbitrary type. Hash tables have many different uses, most often behind the scenes. They are sometimes used in cache implementations and as the underlying logic to build a set data structure.

Moving forward, we’ll examine the basic anatomy of a hash table, its efficiency, and how to implement one in JavaScript.

Hashing Functions

Hash tables are incredible data structures because not only do they have the benefit of efficient property lookup, but on average, they also have efficient insertion. The way this is accomplished is in part by using a hashing function. The hashing function coerces your key to an index in a way that is repeatable and uniformly distributable. It also reduces a key universe of arbitrary size down to an index universe of fixed size, with a negligible time penalty.

Let’s explain repeatability. A repeatable hashing function is a function that produces the same output every time, given the same input. For example, a function that uses the length of a string input as the output would be considered repeatable. Conversely, a function that adds the length of the string input with the current calendar month number to calculate the output index would not be repeatable. This is because if you invoke the function in January, and then invoke it in February, the indices would be different.

An illustration explaining a repeatable hashing function

As mentioned above, a hashing function’s ability to uniformly distribute its output indices is another critical role it serves. Uniform index distribution means that the output indices have roughly the same probability of landing within any part of the output range as any other. This is to avoid index collisions as much as possible because collisions are expensive to resolve. Let’s illustrate this point, further.

An illustration explaining the uniform distribution of a hashing function

Collision Resolution

Of course, at a certain point, index collisions are inevitable because you’re reducing a potentially large key universe down to a fixed size. So as your number of properties approaches your total index range, the marginal likelihood of a collision increases. Fortunately, some brilliant people have already thought about this, and there are some techniques to help resolve collisions.

One common method is called “separate chaining”. Instead of inserting a value at the computed index for that key, when there is a collision, those key-value pairs are inserted into a linked list (or another data structure) located at that same index. Then when doing a look-up or insertion at that index, the linked list is linearly traversed until the key is found. If the target key is not found, then the property does not exist in the hash table.

An illustration of Separate Chaining as a collision resolution method

Another popular method for collision resolution in hash tables is called “open addressing”. In this approach, all values are stored in the hash table itself instead of additional linked list data structures. When a collision occurs, an algorithm is used to probe for the next available space to insert the value. Often, this algorithm is just another pass through the hashing function, known as “double hashing,” but there are other algorithms out there as well. Double hashing has the benefit of being fairly optimized against clustering.

Dynamic Resizing

The more index collisions that your hash table needs to resolve, the more costly it becomes to operate your hash table. Thus, it becomes beneficial to resize hash tables when they reach a certain capacity, also known as the “load factor.” While resolving index collisions can be relatively computationally expensive, so is hash table resizing because it involves rehashing all or some of the existing table properties. Additionally, preemptively resizing your hash table to maintain a minimal load factor can unnecessarily consume memory. Thus, dynamic resizing can be required to make the table larger, as well as smaller.

The simplest way to resize a hash table is to completely rehash all existing properties. When the desired load factor is reached, the existing properties are rehashed to a new hash table with the new, appropriate size.

An illustration of complete rehashing during hash table resizing

Sometimes it may not be practical to do a complete rehash of all existing properties when dynamically resizing a hash table. In some real-time applications where time is critical and hash table sizes can be enormous, it can be unacceptable to rehash all properties at once. Instead, incremental rehashing can be a more practical solution. This typically involves creating a new hash table alongside the old hash table, inserting incoming properties into the new hash table, and then incrementally moving a small number of old properties to the new table on every operation. This still has the benefit of amortized efficiency, but it means that during the resizing process, each operation (i.e. insert, find, and remove) may potentially require looking up properties in both tables.

An illustration of incremental rehashing during hash table resizing

Efficiency

When working with any data structure, the primary concern should always be efficiency. There are many different data structures and subsequent variants of those data structures, all of which could potentially be consumed in any given use case, but often times there is a particular data structure that will fit best considering your concerns.

In order to understand how efficient a data structure is, you’ll need to understand the language of efficiency. Big O notation is the standard by which efficiency is determined and it is often used to convey how a data structure will behave in different conditions. When it comes to time complexity, the worst-case and average scenarios are the primary conditions that most engineers will be interested in when deciding which data structure to use for their use case. Space complexity does come into play sometimes, but most data structures have linear space complexity (i.e. O(n)) and memory usage can often easily be scaled, so this is typically overlooked.

In a well-dimensioned hash table, the average time complexity for each lookup, insertion, and deletion is independent of the number of elements stored in the table. In Big O terms, this would be considered O(1), or constant time complexity. This is what makes hash tables so powerful, but the key here is the term “well-dimensioned”. It means that the hash table is sized adequately so that resizing happens rarely. When resizing does occur, it can absorb precious runtime. However, this additional cost can be thought to be amortized across all insertions and deletions and therefore be considered negligible.

Implementation in JavaScript

Hashing Function

First things first, we’ll need a hashing function. As I described earlier, the hashing function is the foundation of this data structure because it coerces your key to an index with effectively no time penalty. We’ll reserve a deep dive into how hashing functions work for another article. For now, take a look at the code below that converts a string to an index in JavaScript.

An example of a hashing function to convert a string to an integer, written in JavaScript

It’s not critical to understand how the “left shift” or “bitwise and” operators work and why they’re used here, but it is useful to know what is going on at a high level.

There are two main things that I’d like you to take away from this function. First, you can see on lines 4 and 5 that we’re incorporating every character from the input string into our final hash index. Because every character is used in the calculation of the hash index, the likelihood of hashing collisions is reduced. Second, you’ll notice on line 10 that we’re using the “remainder” operator on the final hash value. This ensures that the resultant hash index is always less than the maximumInteger value provided to the function invocation.

General Structure

We could use a class type here but there is not much to be gained from doing that. Instead, we’ll use a function and add three properties to its this binding. Take a look:

The general structure of a function to construct a hash table in JavaScript

We initialize a _storage property as an empty array literal, and that’s where we’ll store our hash table properties. For dynamic resizing purposes, we’ll need to track the total number of properties we currently have and the size limit of our hash table. We’ll track the property count using the _count property and update it each time something is added or removed from the hash table. Similarly, we’ll track the size limit with the _limitproperty and update it every time we need to expand or reduce the hash table’s capacity.

In case you were wondering, we can’t simply use the length property on the _storage array to gauge our property count because we’ll be inserting items at indices generated by the hashing function. These indices are unlikely to be sequential, and therefore, we’ll have gaps in the array which won’t be reflected in the length property. Try it out in your browser’s console. Assign an empty array to a variable, insert a value at index 5 or any other non-zero index, and then read the length property on the array. You’ll see that the length property is 6, even though we’ve only inserted one item.

Insert Method

Next, we’ll define the insert method and we’ll attach it to the HashTable prototype so we can consume it.

A JavaScript implementation of an insert function for a hash table

Let’s analyze the code to better understand what’s going on. The function can be broken down into two main parts: adding the property and conditionally resizing the data structure.

To add the property to our data structure, we first compute the index using our hashing function described earlier. This will provide us a value between 0 and the storage limit we defined earlier, _limit. From there, we check our _storage array to see if something already exists at that index. If nothing exists there, we’ll create a tuple from our key and value pair and place that into an array. Otherwise, if something already exists at that index, we’ll traverse the existing array and compare keys. If that key already exists, update the value associated with that key. If not, we’ll add it to the end of the array. Finally, we’ll update that property on the _storagearray and increment our _count value to properly track our current property count.

Now that our _count value is up to date, we need to check if our hash table is properly sized. Deciding when to resize your hash table depends mostly on space versus time considerations, but for the sake of demonstration, we’ve chosen to double in size when the load factor, or the percentage of capacity currently being used, crosses above the 75% threshold. To do this we’ll reset our _storage and _count variables, double our _limit, and most importantly, we’ll rehash our entire inventory of properties. To do the rehashing, we’ll iterate through our nested storage structure, collect all of the pairs into a flat array, and then recursively call our insert method on each pairing.

Retrieve Method

The retrieve method is considerably simpler than our insert method but just as important. To get the value associated with a particular key we need to compute the index using the exact same hashing function (remember, our hashing function is repeatable). We then do a lookup on our _storage array at that index and iterate through the resultant array there to find a matching key. Take a look below to see this implemented in JavaScript.

A JavaScript implementation of a retrieve function for a hash table

Remove Method

The remove method is completely analogous to our insert method described previously. We compute the index, find a matching key if it exists, remove that value from the nested array, and decrement our _count. Then, if the result of a lower property count brings us below our lower bound load factor (in this case 25%), we reduce our storage size in half using a similar recursive algorithm from our insert method. You can see a JavaScript implementation of this below.

A JavaScript implementation of a remove function for a hash table

Conclusion

The hash table is one of the most efficient data structures available to us as developers, and it is used as the foundation of a lot of fundamental technology we use today. Understanding how to build one yourself will give you better insight into how and when to use them in your own code.

If you’re curious about how to build other fundamental data structures in JavaScript, check out this article How to Build a Linked List in JavaScript. Or if you’re thinking about joining a coding bootcamp, 10 Things I Learned as a Coding Bootcamp Grad is a great place to learn a little bit more.

The post How to Build a Hash Table in JavaScript first appeared on Coding Bootcamp Guides.

How to Build a Stack in JavaScript

Michael Stromberg — Sun, 18 Jul 2021 23:15:53 +0000

Photo by Tatiana Rodriguez on Unsplash

Data structures are an integral part of your life, whether you notice them or not. From waiting in line at the grocery store to something more obvious like the glossary in a textbook, they’re everywhere. However, they are especially important in software engineering and the algorithm interview questions that are asked during technical interviews.

Stacks

A stack is an important type of data structure used in engineering and computer science, and it has certain properties that make it especially useful. Stacks can be described as a Last In First Out (LIFO) data structure. This means that each time you want to remove an item, the stack will provide you with the most recently added item. Imagine you work at a restaurant in the kitchen and you need to plate an order. You have a tall stockpile of dinner plates in front of you. Now imagine you grab a plate from the plate pile. What part of the pile did you reach for? Logically you would reach for one from the top and begin arranging the meal on it. While you could have lifted half of the plates, took a plate from the middle, and set the remaining plates back on top of the pile, this would have been a lot more work.

Photo by Mick Haupt on Unsplash

Other good examples of stacks in real life are browser histories, clothing (it would be rather difficult to remove your shirt before you take off your jacket), or anything that is stored vertically like maybe some dining chairs.

Efficiency

Now that we generally understand how stacks work and where they’re used in real life, let’s talk about their efficiency. Data structure efficiency is often measured using Big O notation for both time complexity and space complexity, but we’re generally only concerned with time complexity when simply evaluating data structures. We’re also often only interested in the worst-case scenarios (i.e. when there is a lot of data) because differences in time complexity efficiency for small amounts of data are often trivial or unreliable.

Stacks are well-suited for insertion and deletion because they keep an active reference pointing at the most recent item added. Because of this, their time complexity for insertion and deletion are considered constant time (i.e. O(1)). However, if you need to be able to look up any other item other than the latest item added to the stack, you may want to use a different data structure that is better optimized for that scenario. While you might consider stacks to have linear lookup time complexity (i.e. O(n)), you would need to remove all of the items that were added after your target item in order to read it.

With all of that said, stacks are very efficient when used properly. If you want to see a comparison of common data structures and their efficiencies, you can take a look at this popular cheatsheet.

Implementation in JavaScript

Generally speaking, a stack needs to be able to push and pop the latest item, as well as allow users to read its length. Below is a class implementation of a basic stack in JavaScript.

A class implementation of a stack data structure in JavaScript.

Let’s talk about how this works. Here on lines 2 through 5, we initialize our stack class with data and size properties attached to the instance. If the stack is instantiated without any initial data, the data property will be assigned an empty array and the size property will be 0.

You may have noticed that I used arrow function expressions for the instance methods defined on lines 7 and 12. Because arrow function expressions don’t have their own this bindings, the references to this in the function definitions will evaluate to the this found in the scope where the functions were defined. This is a minor convenience here, but I thought it would be worth explaining.

I also want to draw your attention statement on line 15. This shortens the length of the data array and effectively deletes any items that reside at indices beyond that length. Theoretically, this implementation can vary depending on the JavaScript engine being used, and for the sake of this post, I’ve assumed this is a constant time operation. However, since we’re tracking our own size property, we don’t even need to shrink the array when we pop an item off. We could just delete the item in the array and decrement our size variable.

One thing you might also have noticed is that our data and size properties are assigned onto the instance, and this could be considered “leaky.” Some developer could directly mutate the data or size properties and potentially break the stack functionality. Let’s see how we might get around this with a functional implementation.

A function implementation of a stack data structure in JavaScript.

In this implementation, I make use of a JavaScript closure to encapsulate our data and size values. In JavaScript, when a function is declared, it is given access to the lexical environment in which it was created. So by creating local variables within our Stack function and returning an object with methods that reference those variables, we’re in full control of how we allow access and manipulation of those variables. This will help reduce bugs associated with leaky variables, and it’s just as readable and scannable as our class-based solution.

Conclusion

Stacks are very useful data structures in software engineering and in the everyday world. They are particularly efficient for data insertion and deletion when used correctly. Hopefully, you’ve learned a thing or two about how to implement them in JavaScript, but let me know in the comments if you have any questions!

The post How to Build a Stack in JavaScript first appeared on Coding Bootcamp Guides.

Solving the “Merge Sorted Arrays in Place” Problem in JavaScript

Michael Stromberg — Thu, 08 Jul 2021 22:50:12 +0000

Photo by Lance Grandahl on Unsplash

A General Note about Coding Interviews

As usual, I’d like to talk about the nature of coding interviews. They are very analogous to taking the SAT or GRE; sometimes they aren’t necessarily the best reflection of how you’ll perform at your job or in college, but more of a reflection of your preparation and resources.

As long as companies still use these types of problems, you’ll need to prepare for them.

Problem Source / Inspiration

This is a common interview problem.

Asked by: Amazon, Google, Apple, Facebook, Netflix, Microsoft, and many more.

Problem Description

Given two sorted integer arrays A and B, merge B into A as one sorted array. Note, you may assume that A has enough space to hold additional elements from B, and the number of elements initialized in A and B are m and n, respectively.

Problem Solution

Let’s visualize our algorithm, below. By first moving items to the end of the first array, we can minimize the number of cells we need to move (i.e. time complexity) because the extra space is located at the end of the array. If we had started by moving items at the beginning of the first array, we would potentially have to move all of the items in the first array that came after that cell over by one.

A visual representation of merging to sorted arrays in place

Now let’s take a look at the solution to the problem and break down the key aspects.

An implementation of a function to merge sorted arrays in place, in JavaScript.

I chose to create three index variables i, j, and k to point to specific indices of interest. i corresponds to the current item index of the first array, starting with the last item. j corresponds to the current item index of the second array, also starting with the last item. Finally, k corresponds to the index of the cell that needs to be filled, starting with the last index of the first array.

After identifying our pointers, we can begin to iterate. We begin by traversing backwards through the first array. For each iteration, we compare the values at i and j from their respective arrays, and the larger item gets assigned to the cell at k. Each iteration we need to update the appropriate pointers. We decrement k on each loop and also decrement either i or j, depending on which array we took an item from. We also handle edge cases on line 7. If j is less than 0, that means the second array is empty and we only need to draw from the first array. Similarly, if i is less than 0, we only need to draw from the second array.

Conclusion

The main challenge of this problem is to identify the usefulness of moving items to the back of the array where the available space is. You can do it starting from the front, but it makes the logic and code much more complicated. Spending some time to think about time complexity implications like this will save you even more time when it comes to coding it out.

The post Solving the “Merge Sorted Arrays in Place” Problem in JavaScript first appeared on Coding Bootcamp Guides.

Solving the “Staircase with N Steps” Problem in JavaScript

Michael Stromberg — Sun, 13 Oct 2019 18:06:50 +0000

Photo by Jake Hills on Unsplash

A General Note about Coding Interviews

Coding interviews are very analogous to taking the SAT or GRE; sometimes they aren’t necessarily the best reflection of how you’ll perform at your job or in college, but more of a reflection of your preparation and resources.

As long as companies still use these types of problems, you’ll need to prepare for them.

Problem Source / Inspiration

https://www.dailycodingproblem.com

Asked by: Amazon

Problem Description

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time. Generalize your function to take in X.

Problem Solution

These problems can sometimes be hard to conceptualize, especially when using recursion. So with that in mind, I decided to illustrate the initial part of the problem below for n = 4.

A tree diagram of all possible step permutations for 4 total steps and a maximum step size of 2

As you can see from above, in order to solve this problem (without being a mathematician) we can visualize it as a tree-like structure and traverse it to find the branches that satisfy our criteria. I didn’t show all of the failed branches, but you could imagine a branch like 1–2–2 that would fail our criteria of taking exactly 4 steps.

Solution Part #1

Let’s break down the solution to the first part of the problem.

An implementation of a function to count the unique steps by one or two in JavaScript.

When we recurse, we are homing in on a criteria with each successive call of our function. In our problem, we are decrementing the number of total steps left by the step size that we took until there are no steps left.
Our recursive case can be seen on line 7. Here we’re invoking our function with n — 1 and n — 2, respectively. Then we sum the returned values of those subsequent calls.
We still have to handle the cases where we take too many steps. We handle this on lines 2 and 3 by returning 0 if n is negative (i.e. if we’ve taken too many steps).

Solution Part #2

Now let’s take a look at the more complicated scenario.

An implementation of a function to count unique steps by a given step size in JavaScript.

In this case, we’re now expecting an array of valid step sizes. Since, we don’t know the step sizes ahead of time, we can’t hardcode our step size reduction like before.
Instead, we’ll iterate through the stepSizes array, apply our recursion criteria, and then return the sum of the values we produce. To do this, we’ll use Array.prototype.reduce because it allows us to declaratively iterate over an array and accumulate a value.
Our cases are similar to that in Part #1. We handle the cases where we take too many steps on lines 3 and 4, we have our base case on lines 5 and 6, and we handle our recursive case on lines 7 and 8.
In the recursive case, we invoke our function again with a remaining number of steps equal to n — stepSize. We then add the returned value of the function call to our sum variable.

Conclusion

These problem solutions aren’t very verbose; we were able to solve the more complicated part of this problem in 11 easy-to-read lines. The main challenge is to identify the problem as one where you could traverse all possible paths and determine whether each one satisfies the criteria.

The post Solving the “Staircase with N Steps” Problem in JavaScript first appeared on Coding Bootcamp Guides.

DEV Community: Michael Stromberg

How to Create a Memoization Function in JavaScript

What is Memoization?

How Memoization Optimization Works

Deterministic Functions

Function Closures

Higher Order Functions

Memoization Implementation in JavaScript

A Basic Implementation of a Memoization Function

An Advanced Implementation of a Memoization Function

Conclusion

Solving the “Longest Increasing Subsequence” Problem in JavaScript

The “Longest Increasing Subsequence” Problem on LeetCode in JavaScript

Solving the Longest Increasing Subsequence Problem Using A Brute Force Approach

Building a Mental Model for the Brute Force Approach

A JavaScript Implementation of a Brute Force Solution to the Longest Increasing Subsequence Problem

Time and Space Complexity

Solving the Longest Increasing Subsequence Problem Using An Optimized Approach

Building a Mental Model for the Optimized Approach

A JavaScript Implementation of an Optimized Solution to the Longest Increasing Subsequence Problem

Time and Space Complexity

Edge Cases to Consider

Variants of the Number of Islands Problem

When To Use Brute Force Versus an Optimized Solution

Conclusion

Solving the “Number of Islands” Problem in JavaScript

The “Number of Islands” Problem on LeetCode in JavaScript

Problem Description

Solving the Number of Islands Problem Using Depth First Search (DFS)

Building a Mental Model for the Depth First Search Solution

A JavaScript Implementation of Depth First Solution to the Number of Islands Problem

Time and Space Complexity

Solving the Number of Islands Problem Using Breadth First Search (BFS)

Building a Mental Model for the Breadth First Search Solution

A JavaScript Implementation of Breadth First Solution to the Number of Islands Problem

Time and Space Complexity

Edge Cases to Consider

Variants of the Number of Islands Problem

When To Use Depth First Search Versus Breadth First Search

Conclusion

Solving the “Two Sum” Problem in JavaScript

The “Two Sum” Problem on LeetCode in JavaScript

Problem Description

Solving the Two Sum Problem Using Brute Force

Building a Mental Model for the Brute Force Solution

A JavaScript Implementation of a Brute Force Solution to the Two Sum Problem

Time and Space Complexity of the Brute Force Solution

Solving the Two Sum Problem Optimized for Time

Building a Mental Model for the Optimized Solution

A JavaScript Implementation of a Brute Force Solution to the Two Sum Problem

Time and Space Complexity of the Optimized Solution

Edge Cases to Consider

Variants of the Two Sum Problem

When To Use Brute Force Versus the Optimized Solution

Conclusion

Recursion Explained in JavaScript

A Real-Life Analogy of Recursion

Recursion Fundamentals

Base Case

Recursive Case

Recursion in JavaScript

Recursive Math.pow Implementation

Explanation of the Code

How the Recursion Unfolds

The Pros and Cons of Using Recursion

Pros of Using Recursion

Cons of Using Recursion

When to Use Recursion

Conclusion

10 Things I Learned as a Coding Bootcamp Grad

1. Bootcamps can help you learn what you’re capable of

2. Bootcamps are not for everyone

3. Bootcamps don’t really teach you much and that’s okay

4. Imposter Syndrome is real and never really goes away

5. New software technologies emerge often and curriculum needs to adapt to keep up

6. Some bootcamps will fail you and kick you out

7. Communication is key

8. Outcomes are just as important as learning to code

9. The bootcamp is just the beginning

10. Coding bootcamps are here to stay

Recursive `Math.pow` Implementation