# [Challenge] Max Product Finder

#1

#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:

Essential Information on Code Challenges
#2

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.

#3

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.

#5

Basic Difficulty in Ruby

https://repl.it/ImAq/1

#6

Intermediate/Hard Difficulty in Javascript.

Codecademy Challenge - Max Product Finder

#7

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.

#8

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.

#11

Ruby

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

#12

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.

#13

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.

#14

#15

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
``````

#16

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')
``````

#17

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]);
}

#18
``````# 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()

``````

#19

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?

#20

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

#21

Basic Difficulty, Python 3

https://repl.it/IoJD/1

#22

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.

#23

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.