[Challenge] Max Product Finder

#Code Challenge #10: June 14, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Google:


###Basic Difficulty

Given an array of integers, write a function, maxProductFinder, that finds the largest product that can be obtained from any 3 integers in the array.

  • Function Name: maxProductFinder
  • Input: int[] - an array of integers
  • Output: an integer – the maximum product found from any three integers in the array
  • Example: maxProductFinder([-8, 6, -7, 3, 2, 1, -9]) => 432
  • You may assume that the array contains at least three integers
  • Please run the following array as a test: [-6, -8, 4, 2, 5, 3, -1, 9, 10]

#####Find out more about basic challenges.


###Intermediate difficulty

Given an array of integers, write a function, maxProductFinderK, that can be obtained from any k integers in the array.

  • Function Name: maxProductFinderK
  • Input: int[] - an array of integers and an integer k where k is the number of ints that can be used
  • Output: an integer – the maximum product found from any k integers in the array
  • Example: maxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 2) => 72
  • You may presume that the length of the array of integers is greater or equal to k

#####Find out more about intermediate challenges.

###Hard Difficulty

Write maxProductFinder and maxProductFinderK as efficiently as possible.

#####Find out more about hard challenges and Big O

####As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.

Reply to this thread with a link to your code on repl.it to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.


The fine print:

Click the links to find out more about:

Decided to practice my javascript for the basic difficulty.
https://repl.it/Il2i/53
I actually found out about the spread syntax when writing my solution, which was very useful.

Basic Difficulty, Python 3

# function to find the greatest product of any three terms
def maxProductFinder(sequence):
    # function to create a generator of pair combination products
    def gen_pair_prods(seq):
        for i, x in enumerate(seq):
            for j in range(i + 1, len(seq)):
                yield x * seq[j]
    # define a max value cache and set a comparison value
    prod = 0
    # iterate input
    for item in sequence:
        # clone input
        temp = sequence[:]
        # remove current item in clone sequence
        temp.remove(item)
        # call for a generator and times its max value by current item
        temp = max(gen_pair_prods(temp)) * item
        # update the cached max value
        prod = temp if temp > prod else prod
    return prod

print (maxProductFinder([-6, -8, 4, 2, 5, 3, -1, 9, 10]))
# memory leakage ? Zero at this point

https://repl.it/IkCJ/0

Since the goal is to find the product of any three members, my thinking was to iterate through the input sequence, copy the sequence and remove the current item from the copy. With the remaining sequence, create a generator that finds the product of all possible pairings. From that find the maximum product and multiply it by the item. Cache the greater of that value and the current value in the cache.

3 Likes

Basic Difficulty in Ruby

https://repl.it/ImAq/1

1 Like

Intermediate/Hard Difficulty in Javascript.

Codecademy Challenge - Max Product Finder

Intermediate/Hard, Python 3

import itertools

def MaxProductFinderK(sequence, k):
    largest = 0

    # create all combinations with k length
    combinations = itertools.combinations(sequence, k)      

    # go through each combination
    for combination in combinations:
        i = 0
        temp = 1
        # multiply each number in the combination
        while i < (k):
            temp = combination[i] * temp
            i+=1
        # find largest product
        if temp > largest:
            largest = temp
    
    return(largest)

print(MaxProductFinderK([-8, 6, -7, 3, 2, 1, -9], 2))

https://repl.it/ImH2/0

I found itertools and it works perfect for this, it groups all possible combinations of any length in a list. Then all I did was multiply the combinations together to find the largest product.

Here’s my code:
https://repl.it/ImDh/25

I believe I have the basic and intermediate difficulties working. I’m not sure about hard difficulty.

Ruby

def maxProductFinder(a)
  a.combination(3).to_a.map{|e1,e2,e3| e1*e2*e3}.max
end
1 Like

We previously decided that itertools can not be used since one line solutions are very easy with it and all the work is done for you. Sorry we forgot to mention this in the initial post.

3 Likes

Basic Difficulty, Python 3
https://repl.it/ImRM/3

def maxProductFinder(array):
  # define a stand-in array to avoid operating directly on the input
  standInArray = array
  newArray = []
  # iterate through standInArray
  for i in standInArray:
    # define a new array that contains all numbers in standInArray except i
    otherNumbers = standInArray
    otherNumbers.remove(i)
    # iterate through otherNumbers
    for g in otherNumbers:
      # find all combinations of i and otherNumbers for every value of i
      newArray.append(i*g)
  # find the maximum of newArray and then multiply it by the max of the given array
  # also multiply the minimum values of both arrays, to account for negative values
  finalArray = [max(newArray)*max(standInArray), min(newArray)*min(standInArray)]
  # find the max of finalArray
  q = max(finalArray)
  return q
  
maxProductFinder([-6, -8, 4, 2, 5, 3, -1, 9, 10])  

My thinking was to first find all of the different combinations of two numbers in the array, then multiply the maximum value of the resulting array by the maximum value of the input array to find the maximum product.

1 Like

Basic Challenge

Basic Difficulty, Python 3.5

I used numpy to sort the inputted array of integers. Knowing that the max product would occur by multiplying the largest numbers (absolute value), I created end3_product, which would multiply the largest 3 positive numbers, and front2_back1_product, which would multiply the 2 smallest numbers (which would be largest in terms of absolute value, if negative, and the two negatives would cancel each other out to become positive) and the largest positive number. Whichever combo is larger will be returned by the if, else statement

import numpy

def maxProductFinder(int_array):
    length = int_array.size
    sorted = numpy.sort(int_array)
    end3_product = sorted[length-1]*sorted[length-2]*sorted[length-3]
    front2_back1_product = sorted[0]*sorted[1]*sorted[length-1]
    if end3_product > front2_back1_product:
        return end3_product
    else:
        return front2_back1_product

Hard Difficulty -

Python 3:

https://repl.it/InFi/24

from time import time

def maxProductFinder(array):
    # Sort the array in ascending order
    array.sort()
    # If all the integers in the array are negative, maximum product is product of 3 largest integers (smallest absolute value)
    if array[-1] < 0:
        return array[-1]*array[-2]*array[-3]
    # Multiply the largest product of two integers(excluding the largest integer) to the largest integer in the array
    # The product of two negative or two positive integers is positive
    else:
        return array[-1]*(array[0]*array[1] if (array[0]*array[1] > array[-2]*array[-3]) else array[-2]*array[-3])
    
    
def maxProductFinderK(array, K):
    # Sort the array in ascending order
    array.sort()
    product = 1
    # If all integers in the array are whole numbers, the product of K integers from the end of sorted array is largest
    if array[0] >= 0:
        for x in range(int(K)):
            product *= array[-(x+1)]
        return product
    # Check if number of integers to be used to find the product is odd or even
    elif K%2:
        # If largest integer in the array is zero, maximux product of odd number of integers is zero
        if array[-1] == 0:
            return 0
        # If all integers in the array are negative and K is odd, then the product of K integers from the end of sorted array is largest(whose absolute value is smallest)
        elif array[-1] < 0:
            for x in range(int(K)):
                product *= array[-(x+1)]
            return product
        else:
            product *= array[-1]
            # Remove the largest integer to make the required number of integers in the product left even
            del array[-1]
            K -= 1
    # If all integers in the array are negative and K is even, then the product of K integers from the start of sorted array is largest(whose absolute value is is also largest)
    elif array[-1] < 0:
        for x in range(int(K)):
            product *= array[x]
        return product
    # Since the required number of integers in the product are even, in loop find the largest product of two numbers till all K integers are used to get product
    while K:
        # largest product of two numbers can be either at the begining(if negative integers) or last
        if array[0]*array[1] > array[-2]*array[-1]:
            product *= array[0]*array[1]
            del array[0]
            del array[0]
        else:
            product *= array[-2]*array[-1]
            del array[-1]
            del array[-1]
        K -= 2
        
    return product
    
    
print(f'maxProductFinder([-6,-8,4,2,5,3,-1,9,10]) => {maxProductFinder([-6,-8,4,2,5,3,-1,9,10])}')
print(f'maxProductFinderK([-8,6,-7,3,2,1,-9], 2) => {maxProductFinderK([-8,6,-7,3,2,1,-9], 2)}')

t = 0

for x in range(1000000):    # 1 million iteration
    start =  time()
    maxProductFinderK([-8,6,-7,3,2,1,-9], 2)
    end = time()
    t += end - start

print(f'Time taken to run maxProductFinderK million times is {t} seconds')
2 Likes

implemented for basicdifficulty
i used c language to implement maxproductfinder,here i used two arrays one is set of integers given by user and other array is used to find first three maximum integers from 1st array

int maxProductFinder(int a)
{
int t[2],max=a[0];
t[0]=a[0];t[1]=a[1];t[2]=a[2];
for(i=0;temp[i]!=NULL;i++)
{
for(j=3;a[j]!=NULL;j++)
{
if(t[0]<t[1] && t[0]<t[2])
tmin=t[0];
elseif(t[1]<t[0] && t[1]<t[0])
tmin=t[1];
else
tmin=t[2];
if(tmin<a[j])
{
if(tmin==t[0])
t[0]=a[j];
if(tmin==t[1])
t[1]=a[j];
if(tmin==t[2])
t[2]=a[j];
}
}
}
return (t[0]*t[1]*t[2]);
}

# Code Challenge #10: June 14, 2017


# Intermediate Difficulty
def maxProductFinderK(inputList, k):
    if k > len(inputList):
        print("Size too big")
        return

    returnValue = 1
    numbersUsed = 0
    rightSide = len(inputList) - 1
    leftSide = 0

    inputList.sort()

    while numbersUsed + 1 < k and leftSide < rightSide:
        if inputList[leftSide] * inputList[leftSide + 1] > inputList[rightSide] * inputList[rightSide - 1]:
            returnValue *= inputList[leftSide] * inputList[leftSide + 1]
            leftSide += 2
            numbersUsed += 2
        else:
            returnValue *= inputList[rightSide]
            rightSide -= 1
            numbersUsed += 1

    while numbersUsed < k:
        returnValue *= inputList[rightSide]
        rightSide -= 1
        numbersUsed += 1

    return returnValue


# Hard Difficulty
def maxProductFinder(inputList):
    returnValue = 1
    rightSide = len(inputList) - 1
    leftSide = 0

    inputList.sort()

    while inputList[rightSide] > 0:
        returnValue *= inputList[rightSide]
        rightSide -= 1

    while leftSide < rightSide:
        returnValue *= inputList[leftSide] * inputList[leftSide + 1]
        leftSide += 2

    return returnValue


def main():
    print("maxProductFinderK([-6, -8, 4, 2, 5, 3, -1, 9, 10], 3) =>", maxProductFinderK([-6, -8, 4, 2, 5, 3, -1, 9, 10], 3))
    print("maxProductFinderK([-6, -8, 4, 2, 5, 3, -1, 9, 10], 4) =>", maxProductFinderK([-6, -8, 4, 2, 5, 3, -1, 9, 10], 4))
    print("maxProductFinderK([-6, -8, 4, 2, 5, 3, -1, 9, 10], 5) =>", maxProductFinderK([-6, -8, 4, 2, 5, 3, -1, 9, 10], 5))
    print("maxProductFinder([-6, -8, 4, 2, 5, 3, -1, 9, 10]) =>", maxProductFinder([-6, -8, 4, 2, 5, 3, -1, 9, 10]))

if __name__ == "__main__":
    main()

It’s been awhile since I’ve been in a math class. does the “larger product” have to be positive? Or is -5 larger than 3?

Question: How can you link an interpreter for code execution on the website?

Basic Difficulty, Python 3

https://repl.it/IoJD/1

Hmmm… You’re kidding, right?

Sorry to be snide, but it would be an arbitrary world that could change the laws of number for convenience. It’s why I asked. Nothing more.

1 Like

If you were comparing a positive number with a negative number, then yes, the larger number (product) would be positive. Also the multiplication of two negative numbers can produce a positive number.

2 Likes