Highest Product of Three Numbers – Practice Questions for the Amazon Interview

Interviewing for a software engineering position at Amazon? Start with our practice programming interview questions. We’ve helped several engineers get the job at Amazon already.

Highest Product of Three Numbers

Given a list of integers, find the highest product you can get from three of the integers.

The input list_of_ints will always have at least three integers.

Gotchas

Does your function work with negative numbers? If list_of_ints is [-10, -10, 1, 3, 2][−10,−10,1,3,2] we should return 300300 (which we get by taking -10 * -10 * 3−10∗−10∗3).

We can do this in O(n)O(n) time and O(1)O(1) space.

Breakdown

To brute force ↴ an answer we could iterate through list_of_ints and multiply each integer by each other integer, and then multiply that product by each other other integer. This would probably involve nesting 3 loops. But that would be an O(n^3)O(n3) runtime! We can definitely do better than that.

Because any integer in the list could potentially be part of the greatest product of three integers, we must at least look at each integer. So we’re doomed to spend at least O(n)O(n) time.

Sorting the list would let us grab the highest numbers quickly, so it might be a good first step. Sorting takes O(n\lg{n})O(nlgn) time. That’s better than the O(n^3)O(n3) time our brute force approach required, but we can still do better.

Since we know we must spend at least O(n)O(n) time, let’s see if we can solve it in exactly O(n)O(n) time.

A great way to get O(n)O(n) runtime is to use a greedy ↴ approach. How can we keep track of the highest_product_of_3 “so far” as we do one walk through the list?

Put differently, for each new current number during our iteration, how do we know if it gives us a new highest_product_of_3?

We have a new highest_product_of_3 if the current number times two other numbers gives a product that’s higher than our current highest_product_of_3. What must we keep track of at each step so that we know if the current number times two other numbers gives us a new highest_product_of_3?

Our first guess might be:

  1. our current highest_product_of_3
  2. the three_numbers_which_give_highest_product

But consider this example:

  list_of_ints = [1, 10, -5, 1, -100]

Right before we hit -100−100 (so, in our second-to-last iteration), our highest_product_of_3 was 1010, and the three_numbers_which_give_highest_product were [10,1,1][10,1,1]. But once we hit -100−100, suddenly we can take -100 * -5 * 10−100∗−5∗10 to get 50005000. So we should have “held on to” that -5−5, even though it wasn’t one of the three_numbers_which_give_highest_product.

We need something a little smarter than three_numbers_which_give_highest_product. What should we keep track of to make sure we can handle a case like this?

There are at least two great answers:

  1. Keep track of the highest_2 and lowest_2 (most negative) numbers. If the current number times some combination of those is higher than the current highest_product_of_3, we have a new highest_product_of_3!
  2. Keep track of the highest_product_of_2 and lowest_product_of_2 (could be a low negative number). If the current number times one of those is higher than the current highest_product_of_3, we have a new highest_product_of_3!

We’ll go with (2). It ends up being slightly cleaner than (1), though they both work just fine.

How do we keep track of the highest_product_of_2 and lowest_product_of_2 at each iteration? (Hint: we may need to also keep track of something else.)

We also keep track of the lowest number and highest number. If the current number times the current highest—or the current lowest, if current is negative—is greater than the current highest_product_of_2, we have a new highest_product_of_2. Same for lowest_product_of_2.

So at each iteration we’re keeping track of and updating:

  • highest_product_of_3
  • highest_product_of_2
  • highest
  • lowest_product_of_2
  • lowest

Can you implement this in code? Careful—make sure you update each of these variables in the right order, otherwise you might end up e.g. multiplying the current number by itself to get a new highest_product_of_2.

Solution

We use a greedy ↴ approach to solve the problem in one pass. At each iteration we keep track of:

  • highest_product_of_3
  • highest_product_of_2
  • highest
  • lowest_product_of_2
  • lowest

When we reach the end, the highest_product_of_3 is our answer. We maintain the others because they’re necessary for keeping the highest_product_of_3 up to date as we walk through the list. At each iteration, the highest_product_of_3 is the highest of:

  1. the current highest_product_of_3
  2. current * highest_product_of_2
  3. current * lowest_product_of_2 (if current and lowest_product_of_2 are both low negative numbers, this product is a high positive number).
  def highest_product_of_3(list_of_ints):    if len(list_of_ints) < 3:
        raise ValueError('Less than 3 items!')

    # We're going to start at the 3rd item (at index 2)
    # so pre-populate highests and lowests based on the first 2 items.
    # We could also start these as None and check below if they're set
    # but this is arguably cleaner
    highest = max(list_of_ints[0], list_of_ints[1])
    lowest  = min(list_of_ints[0], list_of_ints[1])
    highest_product_of_2 = list_of_ints[0] * list_of_ints[1]
    lowest_product_of_2  = list_of_ints[0] * list_of_ints[1]

    # Except this one--we pre-populate it for the first *3* items.
    # This means in our first pass it'll check against itself, which is fine.
    highest_product_of_3 = list_of_ints[0] * list_of_ints[1] * list_of_ints[2]

    # Walk through items, starting at index 2
    for i in xrange(2, len(list_of_ints)):
        current = list_of_ints[i]

        # Do we have a new highest product of 3?
        # It's either the current highest,
        # or the current times the highest product of two
        # or the current times the lowest product of two
        highest_product_of_3 = max(highest_product_of_3,
                                   current * highest_product_of_2,
                                   current * lowest_product_of_2)

        # Do we have a new highest product of two?
        highest_product_of_2 = max(highest_product_of_2,
                                   current * highest,
                                   current * lowest)

        # Do we have a new lowest product of two?
        lowest_product_of_2 = min(lowest_product_of_2,
                                  current * highest,
                                  current * lowest)

        # Do we have a new highest?
        highest = max(highest, current)

        # Do we have a new lowest?
        lowest = min(lowest, current)

    return highest_product_of_3

Complexity

O(n)O(n) time and O(1)O(1) additional space.

Bonus

  1. What if we wanted the highest product of 4 items?
  2. What if we wanted the highest product of kk items?
  3. If our highest product is really big, it could overflow. ↴ How should we protect against this?

What We Learned

Greedy ↴ algorithms in action again!

That’s not a coincidence—to illustrate how one pattern can be used to break down several different questions, we’re showing this one pattern in action on several different questions.

Usually it takes seeing an algorithmic idea from a few different angles for it to really make intuitive sense.

Our goal here is to teach you the right way of thinking to be able to break down problems you haven’t seen before. Greedy algorithm design is a big part of that way of thinking.

For this one, we built up our greedy algorithm exactly the same way we did for the Apple stocks question. By asking ourselves:

“Suppose we could come up with the answer in one pass through the input, by simply updating the ‘best answer so far’ as we went. What additional values would we need to keep updated as we looked at each item in our set, in order to be able to update the ‘best answer so far’ in constant time?”

For the Apple stocks question, the only “additional value” we needed was the min price so far.

For this one, we needed four things in order to calculate the new highest_product_of_3 at each step:

  • highest_product_of_2
  • highest
  • lowest_product_of_2
  • lowest
Practice Questions for the Amazon Interview Review:

In our experience, we suggest you solve this Practice Questions for the Amazon Interview and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Practice Questions for the Amazon Interview

Find on Interview Cake

Conclusion:

I hope this Practice Questions for the Amazon Interview would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions

Leave a Reply

Your email address will not be published.