First Slice Of Interview Cake

I mentioned Interview Cake in my previous post. Parker Phinney, an ex-Google engineer created Interview Cake as a study tool that preps software engineering candidates for coding interviews.

After a 3 year stint as an Amazon engineer, I have no particular desire to work for one of the 'big three' at the moment. However, I do find these isolated, algorithm based coding problems interesting.

So here goes my attempt at the first question Interview Cake decided to throw at me.

The Problem

You have an array of integers, and for each index you want to find the product of every integer except the integer at that index. Write a function that takes an array of integers and returns an array of the products.

For example, given:

[1, 7, 3, 4]

your function would return:

[84, 12, 28, 21]

by calculating:

[7*3*4, 1*3*4, 1*7*4, 1*7*3]

Do not use division in your solution.

My Solution

My solution was designed as follows:

  • Iterate the array of integers creating a temporary array of all integers except the current index.

  • Pass each temporary array to a function that returns the product of all it's integers.

  • Push the product of each temporary array in to an output array.

var getProductsOfAllIntsExceptAtIndex = function (ints) {

    var productArr = [];

    // return the product of the integers in an array
    function multiply(a) {
        var product = 1;
        for (var i=0; i<a.length; i++) {
            product *= a[i];
        }
        return product;
    }

    // for each index in the original array
    // create a temp array containing all integers except the index
    for (var i=0; i<ints.length; i++) {
        var tempArr = ints.filter(function(item) {
            return item != ints[i];
        });

        // push the product of each temp array to our output array
        productArr.push(multiply(tempArr));
    }

    return productArr;
}

If we pass an array of integers to getProductsOfAllIntsExceptAtIndex()

var ints = [1, 7, 3, 4];  
var result = getProductsOfAllIntsExceptAtIndex(ints);  
console.log(result);  

We will get the expected result:

// returns
[84, 12, 28, 21]

This solution works great. It's readable, concise and returns the correct data but I'm using nested loops. Nesting loops is undesirable because it effects the scalability of an algorithm.

Big O Notation

The simplest explanation of Big O Notation is:

Big O notation is the language we use for articulating how long an algorithm takes to run.

The way we express Big O Notation makes it look intimidating but it's actually much simpler than it looks. Interview Cake provides a great, in-depth explanation that helped me understand.

My solution runs in quadratic time so it has a runtime of O(n2). Basically, it uses a nested loop, which makes the number of operations grow exponentially in terms of space and time when the input array gets larger.

The Optimal Solution

While my own solution was correct, it was obvious to me that it was inefficient. I spent another 20 minutes trying to write a solution that runs in linear time or O(n) and failed miserably.

If we look at the answer provided by Interview Cake, we'll see it uses a greedy approach. This eliminates the repeated calculations by moving through the problem space, storing results as it goes and piecing them together at the end.

The solution was written in Python so I translated to Javascript for consistency:

var getProductsOfAllIntsExceptAtIndex = function (intArr) {

    // we make an array with the length of the input array to
    // hold our products
    var productsOfAllIntsExceptAtIndex = [];

    for (var i=0; i<intArr.length; i++) {
        productsOfAllIntsExceptAtIndex.push(1);
    }

    // for each integer, we find the product of all the integers
    // before it, storing the total product so far each time
    var product = 1;
    i = 0;

    while (i<intArr.length) {
        productsOfAllIntsExceptAtIndex[i] = product;
        product *= intArr[i];
        i += 1;
    }

    // for each integer, we find the product of all the integers
    // after it. since each index in products already has the
    // product of all the integers before it, now we're storing
    // the total product of all other integers
    product = 1;
    i = intArr.length - 1;

    while (i >= 0) {
        productsOfAllIntsExceptAtIndex[i] *= product;
        product *= intArr[i];
        i -= 1;
    }

    return productsOfAllIntsExceptAtIndex;
};

var intArr = [1, 7, 3, 4];  
var result = getProductsOfAllIntsExceptAtIndex(intArr);  
console.log(result);  

Benchmarking

If we use jsperf to benchmark the two solutions, we will see that the solution that runs in quadratic time is 36% slower and it would only continue to get slower if the inital input array was larger.

jsperf benchmarking results

Conclusion

My solution probably deserves no more than a B-. It was fun to kill some time solving the problem but the real benefit comes from learning a new concept (Greedy Algorithms) and improving my understanding of Big O Notation.

Hopefully, I'll nail the next one...