A unique JavaScript interview challenge

What’s up team?! Welcome back to Code Review, a series of coding interview challenges and career related content released weekly exclusively on Dev.to. I’m Elisabeth Gross and you might know me from the work I do on Coderbyte, a site dedicated to helping developers of any level get their next engineering job. Or, you may have heard of me via Breadwinnerss, a tool that helps users request intros for whichever roles they're interested in across dozens of companies.

The best part about writing this series is getting to know you all as a community of driven and excited developers, passionate about leveling up their coding skills. If you want more tips and tricks along with some developer lifestyle content, give me a follow on Instagram @elisabethgross568. I’ll be posting about what coffee shops I love to work at in NYC, some of my favorite playlists to listen to while coding and more! I can’t wait to engage with you all more. Alright, enough chit chat - let’s jump into the solution for last week’s challenge.

The solution

This solution finds how much volume of water can exist in a horizontal plane and then sums each layer to get the total volume. At each horizontal level, we can find the peaks, or the bounds where water can exist between, and subtract the indices of each peak to get the space between them where water can collect. This might be easier to visualize with some code!

Pro Tip

This problem is a GREAT opportunity to build some helper functions. Often, when solving an algorithm challenge where a lot is going on, it is helpful to start with the more general concepts, stubbing in helper functions that you can work on as the interview goes on. This communicates two things to your interviewer. First, you understand the larger concept of the problem and can build a mini roadmap for yourself made up of the smaller building blocks of the puzzle that will ultimately become your algorithm. And second, you don’t get bogged down with the details. Too often when I am interviewing someone, they get caught up in a small part of the algorithm early on and we never make it to the real meat of the algorithm. Stubbing in helper functions allows you to focus on the basic structure right off the bat, and then gives you opportunity to fill in those helper functions with the time you have left.

function totalWaterVolume(arr) {

    // first, we find the 'maxHeight’ which is the highest peak in the water collector
    const maxHeight = Math.max(...arr)

    let totalVolume = 0

    // this loop starts at the maxHeight then decrements the height
    for (let horizontalLevel = maxHeight; horizontalLevel > 0; horizontalLevel--) {

        // 'peaksAtHorizontalLevel' is set to the return value of our first helper function 'peakIndicesMaker' which will be an array of indices of rain collector walls that exist at that level
        var peaksAtHeightLevel = peakIndicesMaker(arr, horizontalLevel)

        // 'vol' is then incremented by the volume that exists at that level, returned from our second helper function 'volAtLevel'
        totalVolume += volAtLevel(peaksAtHeightLevel)
    }

    // total volume is returned
    return totalVolume
}

Let’s take a look at an example to help illustrate what we have so far.

Given the array [0, 3, 0, 1, 0, 0, 0, 1, 0, 2], our rainwater collector will look like this-

First we get the maxHeight which will be 3 in our example. We’ll start looping through each horizontal level beginning with 3.

Let’s start to build out the peakIndicesMaker function! Remember, this function should return the peaks at each horizontal layer of the rain catcher.

/* This function takes the original array, as well as the height level we are looking at, and returns an array of indices where reservoir walls exist */
function peakIndicesMaker(arr, level) {

    const peakIndices = []

    // loop over the entire array
    for (let i = 0; i < arr.length; i++) {

        // if the wall height present at each index is at least the height of the given level then that index is pushed to the output array
        if(arr[i] >= level) {
            peakIndices.push(i)
        }
    }

    // array of indices is returned
    return peakIndices
}

For our example, level 3 will return [1] (just one peak at index 1), level 2 will return [1, 9] (two peaks at index 1 and 9) and level 1 will return [1, 3, 7, 9] (four peaks at index 1, 3, 7, and 9).

Getting the indices of the peaks at each level will allow us to find the space between them which will ultimately give us the volume of water that will collect there! Let’s look at how that will look in code.

/* The distance between the two walls at the same height will also be the volume of water held between them. */
function volAtLevel(peakIndices) {

    let levelVol = 0

    // if there is only one wall at the height currently being calculated, there cannot physically be any water at that level. In this case, we return 0 volume.
    if (peakIndices.length === 1) {
        return 0
    } else {

        // levelVol is incremented for each 'pair' of walls at that level. It is important to note that we are comparing each wall to its adjacent neighbor located at the next index in the array. Therefore the last element in the array could not possibly hold water to its right.  This is because no wall exists at that level beyond the last wall
        for (let i = 0; i < peakIndices.length-1; i++) {

            // Measure the right side of one wall (this is why we look at peakIndices[i] + 1 and not just peakIndices[i]) to the left side of its neighbor
            levelVol += (peakIndices[i + 1] - (peakIndices[i] + 1))

        }
    }

    // the level volume is then returned after all pairs have been summed.
    return levelVol
}

For our example, at the first horizontal level (height = 3), we return 0 because there is only one peak index.

For the next level (height = 2), we have two peaks [1, 9]. We subtract 2 (the index of the first peak plus 1) from 9 (the index of the second peak) and get 7.

For the next level (height = 1), we have 4 peaks [1, 3, 7, 9]. We subtract 2 (the index of the first peak plus 1) from 3 (the index of the second peak) and get 1. We then subtract 4 (the index of the second peak plus 1) from 7 (the index of the third peak) and get 3. And finally we subtract 8 (the index of the third peak plus 1) from 9 (the index of the fourth peak) and get 1.

The total volume will be the sum of all the volumes at each layer which in this case will be 12. And that’s it! Hope you enjoyed this problem as much as I did :) See you next week!