3
\$\begingroup\$

This is an interview question from Interview Cake:

Given a list_of_ints, find the highest_product you can get from three of the integers. The input list_of_ints will always have at least three integers.

I'm looking for feedback on how to improve readability, space, time complexity, using Python idiomatic code and general feedback.

import unittest


def highest_product(list_of_ints):
    pos = [0, 0, 0]
    neg = [0, 0]

    for x in list_of_ints:
        if x > 0 and x > pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x > 0 and x > pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x > 0 and x > pos[2]:
            pos[2] = x
        elif x < 0 and x < neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x < 0 and x < neg[1]:
            neg[1] = x

    if neg[1] < 0:
        max_product = max([x * neg[0] * neg[1] for x in pos])
        max_product = max(pos[0] * pos[1] * pos[2], max_product)
    else:
        max_product = pos[0] * pos[1] * pos[2]

    return max_product


class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)


if __name__ == '__main__':
    unittest.main(verbosity=2)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I would suggest you look at what @mdfst13 suggested if you care about memory and code complexity. Since with this implementation, you already got O(n) code complexity and memory usage as constant. If you want to make this code pretty and short, you will have to sacrifice some memory and complexity. \$\endgroup\$
    – Alex
    Oct 26, 2016 at 12:07

5 Answers 5

4
\$\begingroup\$

First, I'm not a Python guy, so please don't use anything I say to suggest style. I'm trying to copy the style that you used with minor algorithmic differences. I apologize if I make a mistake in doing so.

        if x > 0 and x > pos[0]:
            pos[2], pos[1], pos[0] = pos[1], pos[0], x
        elif x > 0 and x > pos[1]:
            pos[2], pos[1] = pos[1], x
        elif x > 0 and x > pos[2]:
            pos[2] = x
        elif x < 0 and x < neg[0]:
            neg[1], neg[0] = neg[0], x
        elif x < 0 and x < neg[1]:
            neg[1] = x

The x > 0 and x < 0 will have the same result throughout. So we can do just one of each.

        if x > 0:
            if x > pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x > pos[1]:
                pos[2], pos[1] = pos[1], x
            elif x > pos[2]:
                pos[2] = x
        elif x < 0:
            if x < neg[0]:
                neg[1], neg[0] = neg[0], x
            elif x < neg[1]:
                neg[1] = x

Now we do at most four comparisons and may do as few as two. The original also did at least two and could do as many as eight (if greater than 0 but smaller than the three largest positive values).

We can actually reduce that and keep the same behavior

        if x > pos[2]:
            if x > pos[0]:
                pos[2], pos[1], pos[0] = pos[1], pos[0], x
            elif x > pos[1]:
                pos[2], pos[1] = pos[1], x
            else:
                pos[2] = x
        elif x < neg[1]:
            if x < neg[0]:
                neg[1], neg[0] = neg[0], x
            else:
                neg[1] = x

Still the same minimum of two, but the maximum drops to three. We get the same behavior because both values are initialized to 0 and only move in one direction from there. So if x > pos[2], it will also be greater than 0. And x < neg[1] means that it is less than 0.

Perhaps you've noticed a problem though. This code does not solve the problem correctly. But it does produce the same result as your original code, so the bug is in the original code.

Bug

You have one unit test:

class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)

But what if you add a second that says

        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

Your code will fail, returning 0 instead of -2. This is because you initialize the arrays to 0, but you don't verify that there are non-negative members of the array. 0 is not a valid answer here.

If all the numbers are negative, then max_product is negative when

        max_product = max(pos[0] * pos[1] * pos[2], max_product)

So the first product is 0 * 0 * 0, which is 0. 0 will be greater than the product of any three negative numbers. This incorrect answer will hide any possible correct answer.

        max_product = max([x * neg[0] * neg[1] for x in pos])

This is also wrong. Even if you fix the other line, this may multiply the wrong three numbers. For example, consider the input above. The neg variable would hold -6 and -2 (the two smallest negative numbers). So the max product would be -6 * -2 * -1 = -12. But the actual answer should be -2 * -1 * -1 = -2, which is the product of the three largest numbers.

I'll leave it up to you to think through the ramifications of possible fixes. You may want to consider when

        max_product = pos[0] * neg[0] * neg[1];

will give a different result than checking every x. Also, how do you tell when pos[0] * pos[1] * pos[2] should and should not be zero? In particular, consider if it matters if those three values are positive.

To what else could you initialize pos other than 0?

\$\endgroup\$
2
\$\begingroup\$

Your code is not readable at all, due to the use of the fairly non-descriptive variables pos and neg and in general how dense it is, with pos[foo] and neg[bar] everywhere.

Something that would assist in the readability, and make it more idiomatic would be to use combinations from the itertools module to generate the 3-integer sublists of the list_of_ints, and then process the sublists (that part is fairly simple btw).

I don't know how this more readable algorithm would perform, but the complexity of operations being done are simple enough that the difference between more time-efficient algorithms and it are miniscule.

\$\endgroup\$
2
\$\begingroup\$

I don't want to repeat mdfst13's very good answer. So I'll skip changing the if and start from:

if x > pos[2]:
    if x > pos[0]:
        pos[2], pos[1], pos[0] = pos[1], pos[0], x
    elif x > pos[1]:
        pos[2], pos[1] = pos[1], x
    else:
        pos[2] = x
elif x < neg[1]:
    if x < neg[0]:
        neg[1], neg[0] = neg[0], x
    else:
        neg[1] = x

If we were to ignore algorithmic complexity, you can think of this as pos.insert. If x > pos[0] the index is 0. If x > pos[1] then the index is 1, otherwise it's 2. But as this increases the size of the array you'd have to remove an item, say through del pos[3:]. And so you can get:

if x > pos[2]:
    index = next(i for i, v in enumerate(pos) if x > v)
    pos.insert(index, x)
    del pos[3]
elif x < neg[1]:
    index = next(i for i, v in enumerate(neg) if x < v)
    neg.insert(index, x)
    del neg[2]

This is a bit long-winded, and so we can look at bisect. This works in almost the same way as above. And so we could change the code to:

if x > positive[0]:
    bisect.insort(positive, x)
    del positive[0]
elif x < negative[-1]:
    bisect.insort(negative, x)
    del negative[2]

This is much simpler than the original, but still requires del. This makes me think that it's not as efficient as yours was. As we now have at least two more operations than yours did. As the code shifts data to a new index, and then we remove that index. This reminds me of how you create an insertion sort.

So we could change this to use a heap queue via heapq. Which can further simplify the code:

if x > positive[0]:
    heapq.heapreplace(positive, x)
elif x < 0 and -x > negative[0]:
    heapq.heapreplace(negative, -x)

With both the above you may need to change the second part of your code slightly.


In all the above methods we're creating a priority queue. And so the maximum should always be in a constant place. Of either positive[0] or positive[-1]. Excluding the bug. To get the largest product you either use all positive numbers, or two negatives and the largest positive. And so you shouldn't need to create a product for all the positive numbers.

I'd also make a function product, which multiplies all the numbers passed into it together.

And so I'd use:

from heapq import heapreplace
from functools import reduce
from operator import mul

def product(nums):
    return reduce(mul, nums)

def max_product(numbers):
    positive = [0, 0, 0]
    negative = [0, 0]
    for x in numbers:
        if x > positive[0]:
            heapreplace(positive, x)
        elif x < 0 and -x > negative[0]:
            heapreplace(negative, -x)

    return max(product(positive[-1:] + negative), product(positive))
\$\endgroup\$
4
  • \$\begingroup\$ Am I missing something or is deleting entire slices in your first 2 rewrites a mistake? \$\endgroup\$ Oct 26, 2016 at 20:32
  • \$\begingroup\$ @MathiasEttinger How do you mean? BTW they both work fine. \$\endgroup\$
    – Peilonrayz
    Oct 26, 2016 at 21:08
  • \$\begingroup\$ It's just that I thought they would delete more than necessary. I just realized that they are meant to delete only one item each. Why don't you write del positive[0] or del negative[-1] instead? It should be more explicit. \$\endgroup\$ Oct 26, 2016 at 21:48
  • \$\begingroup\$ @MathiasEttinger Yeah that's better than what I have now. It's a bit of a bad habit, 'better safe than sorry'. I'll change it now. Thanks, :) \$\endgroup\$
    – Peilonrayz
    Oct 26, 2016 at 22:41
2
\$\begingroup\$

Seeing as the question on interview cake doesn't mention a requirement for complexity or efficiency, I would default on maximizing code readability and developer time leading to the less efficient version:

import unittest
from itertools import permutations
from operator import mul
from functools import reduce

def highest_product(list_of_ints):
    return max(reduce(mul, seq) for seq in permutations(list_of_ints, 3))


class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)
        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

if __name__ == '__main__':
    unittest.main(verbosity=2)

Edit

This is using combinations instead of permutations thereby increasing efficiency. See comment below.

import unittest
from itertools import combinations
from operator import mul
from functools import reduce

def highest_product(list_of_ints):
    return max(reduce(mul, seq) for seq in combinations(list_of_ints, 3))


class TestHighestProduct(unittest.TestCase):
    def test_highest_product(self):
        self.assertEqual(highest_product([6, -1, -1, -2, 0]), 12)
        self.assertEqual(highest_product([-6, -1, -1, -2]), -2)

if __name__ == '__main__':
    unittest.main(verbosity=2)
\$\endgroup\$
2
  • 2
    \$\begingroup\$ change permutations for combinations, since theres only multiplication of the 3 integers, the order doesn't matter, this will avoid calculating the same integers in different order. \$\endgroup\$
    – Dalvenjia
    Oct 26, 2016 at 21:55
  • \$\begingroup\$ Awesome note. That makes this not so inefficient. \$\endgroup\$
    – iLoveTux
    Oct 27, 2016 at 12:50
1
\$\begingroup\$

You can simplify a building of "pos" and "neg" lists:

  • use list comprehensions to build list of positive/negative integers
  • extend list (minimum length of positive list is 3 / negative is 2). [0] * 3 produce [0, 0, 0]
  • sort positive list in reverse order / negative list in normal order
  • cut positive list to 3 elements / negative list to 2 elements

Code:

pos = [x for x in list_of_ints if x > 0]
pos.extend([0] * 3)
pos.sort(reverse=True)
pos = pos[:3]

neg = [x for x in list_of_ints if x < 0]
neg.extend([0] * 2)
neg.sort(reverse=False)
neg = neg[:2]

  • if length of list_of_ints < 3, extend list_of_ints
  • sort in reverse order - first 3 elements is pos list
  • neg list does not have to be sorted - last 2 elements is neg list
  • because neg list is in reverse order, You must check first element, not last

Code:

list_of_ints.extend([0] * 3)
list_of_ints.sort(reverse=True)
pos = list_of_ints[:3]
neg = list_of_ints[-2:]

if neg[0] < 0:
\$\endgroup\$
4
  • \$\begingroup\$ this will increase code complexity from O(n) to O(n*log(n)) and memory usage from constant to O(n) while it seems like the author cares about it. \$\endgroup\$
    – Alex
    Oct 26, 2016 at 12:02
  • \$\begingroup\$ @Alex first or second? \$\endgroup\$ Oct 26, 2016 at 12:14
  • \$\begingroup\$ They both need O(n) memory because you create new lists there. And in both cases you use sort on a full list which is O(n*log(n)) complexity. \$\endgroup\$
    – Alex
    Oct 26, 2016 at 12:19
  • \$\begingroup\$ @Alex Base algorithm create two lists too and sort lists too. My code is much more readable and is more Pythonic. \$\endgroup\$ Oct 26, 2016 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.