1
\$\begingroup\$

Given an array of integers, find the highest product you can get from three of the integers.

Input: [1, -4, 3, -6, 7, 0]

Output: 168

I would love to hear from how this might be refactored/improved.

GitHub

public static int highestProduct(int[] numbers) {
    int largest, secondLargest, thirdLargest;
    int smallest, secondSmallest;

    largest = secondLargest = thirdLargest = Integer.MIN_VALUE;
    smallest = secondSmallest = Integer.MAX_VALUE;

    for (int number : numbers) {

        // logic to find the largest numbers
        if (number > largest) {
            thirdLargest = secondLargest;
            secondLargest = largest;
            largest = number;
        } else if (number > secondLargest) {
            thirdLargest = secondLargest;
            secondLargest = number;
        } else if (number > thirdLargest) {
            thirdLargest = number;
        }

        // logic to find the smallest numbers
        if (number < smallest) {
            secondSmallest = smallest;
            smallest = number;
        } else if (number < secondSmallest) {
            secondSmallest = number;
        }
    }

    return Math.max(largest * secondLargest * thirdLargest,
            largest * smallest * secondSmallest);
}





   @Rule
public ExpectedException thrown = ExpectedException.none();

@Test
public void invalidInput() {
    thrown.expect(InvalidArgumentException.class);
    HighestProductOfThree.highestProduct(new int[]{1, 2});
}

@Test
public void allPositiveNumbers() {
    Assert.assertEquals(30000, HighestProductOfThree.highestProduct(new int[]{1, 3, 2, 100, 100}));
    Assert.assertEquals(40, HighestProductOfThree.highestProduct(new int[]{1, 2, 4, 5}));
}


@Test
public void allNegativeNumbers() {
    Assert.assertEquals(-30, HighestProductOfThree.highestProduct(new int[]{-20, -10, -5, -3, -2}));
}

@Test
public void mixedNumbers() {
    Assert.assertEquals(300, HighestProductOfThree.highestProduct(new int[]{-10, -10, 1, 3, 2}));
    Assert.assertEquals(168, HighestProductOfThree.highestProduct(new int[]{1, -4, 3, -6, 7, 0}));
} 
\$\endgroup\$
  • \$\begingroup\$ What about overflow handling? Input [Integer.MIN_VALUE, Integer.MIN_VALUE-1, Integer.MIN_VALUE-2, -1, 0, 1] \$\endgroup\$ – Johnbot Apr 7 '18 at 12:23
  • \$\begingroup\$ That should be Integer.MIN_VALUE + 1 and Integer.MIN_VALUE + 2 not minus. \$\endgroup\$ – Johnbot Apr 7 '18 at 12:33
  • \$\begingroup\$ This looks like Java and should be tagged as such. A source for the question would be nice too. Having the tag for challenge and interview seems redundant. \$\endgroup\$ – yuri Apr 7 '18 at 13:37
1
\$\begingroup\$

Your code is straightforward and easy to read. It also doesn't do anything unnecessary. You chose the variable names perfectly, got the indentation correct and provided good test cases. Since you mentioned in the title that there code needs to run in linear time, it is perfect.

I don't see where you throw the exception to make the first of your tests succeed. I bet that test fails currently. That test also imports InvalidArgumentException from a strange package instead of using the standard IllegalArgumentException. Are you coming from a .NET background?

Your code is rather long. If you prefer maintainability and readability over a few nanoseconds of execution time (complexity \$\mathcal O(n\log n)\$), you should rather write:

int[] nums = numbers.clone();
Arrays.sort(nums);

int n = nums.length;
return Math.max(
    nums[n - 3] * nums[n - 2] * nums[n - 1],
    nums[0] * nums[1] * nums[n - 1]);
\$\endgroup\$
  • \$\begingroup\$ All test passes in my workspace. Oh no, I pasted the code without argument validation :-( Dont think I can update now as it code violate SO policy. \$\endgroup\$ – Exploring Apr 7 '18 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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