3
\$\begingroup\$

I have a strange programming prompt. I managed to complete an algorithm to solve smaller test entries (which i'll post). One of my test cases has to complete a 200,000 int input and my algorithm isn't practical. I'll post the prompt and my algorithm. How should I go about optimizing the performance to handle large input sizes?

Prompt:

You and your friend combine your prize tickets at a carnival. You plan to get 2 prizes whose total price is exactly M, M-1, or M-2 tickets (in that order) if possible. M is how many tickets you decide to spend. If there are several prizes that satisfy this condition, you want to minimize the difference between ticket cost.

For example, say you're given M = 5, and prize values of [2,1,4,3].. the output would be 2+3=5.

My SLOW solution:

#sequence actually has +2 values. [0] is how many prizes and [last] is M
#ignore the setting
def checkForPrizes(seq):
    M = seq[len(seq)-1] #priori
#    print("M:",M)
    n = seq[0] #number of inputs

    seq = strip2(seq) #removes the +2 from the "n+2" inputs
    quick_sort(seq) #sorts the prize values
#    print("seq:",seq)
    returnList = []
    leftList = seq[0:int(len(seq)/2)]
    rightList = seq[int(len(seq)/2):len(seq)]

    current = seq[int(len(seq)/2)]
    print("current=",current)

#    print("left half:",leftList)
#    print("right half:",rightList)

    s1 = 0 #prize1
    s2 = 0 #prize2

    flag = False #checks the conditions in order

    if (flag is False):
        for i in range(len(leftList)):
            s1 = leftList[i]
            for j in range(len(rightList)):
                s2 = rightList[j]
                if(s1 + s2 == M):
                    returnList = [s1,s2]
 #                   print("[",s1,",",s2,"] ","is exactly M!",sep="")
                    flag = True

    if(flag is False): #try M-1
        for i in range(len(leftList)):
            s1 = leftList[i]
            for j in range(len(rightList)):
                s2 = rightList[j]
                if(s1 + s2 == (M-1)):
                    returnList = [s1,s2]
#                    print("[",s1,",",s2,"] ","is exactly M-1!",sep="")
                    flag = True

    if(flag is False): #try M-2
        for i in range(len(leftList)):
            s1 = leftList[i]
            for j in range(len(rightList)):
                s2 = rightList[j]
                if(s1 + s2 == (M-2)):
                    returnList = [s1,s2]
#                    print("[",s1,",",s2,"] ","is exactly M-2!",sep="")
                    flag = True

    if(flag is False):
        print("NO")
    else:
#        print("sol:",returnList)
        dispVal(returnList[0],returnList[1])
\$\endgroup\$
1
\$\begingroup\$

You have still some work to do to get correct results in all cases. Consider M=3 and prizes [2,1,4,3]. Your algorithm sorts the list, splits it in two and considers pairs where one item is from the left half and the other from the right. You will not find the sum 1+2 because both numbers will be in the left half.

\$\endgroup\$

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.