find subarray at a given length with the maximum average

Question

Anonymous · Accepted Answer

1. create a queue with a size of k ( subarray length), the queue cant contains more than k elements, in new on is entered the last is out.
2.  The queue should be with the current sum
3. loop the array and add the first k elements to the queue 
4. now each new element :
   - add new element to the queue (the queue should remove the last one)
   - check if sum is bigger, if yes save the queue elements as maxsubarray

return maxsubarray

Anonymous · Answer

def find_max_sub_array(array: List, n: int):
    current_index, current_sum, max_index = 0
    max_sum = float("-inf")
    for num in array:
        current_sum += num
        if current_index >= n:
            current_sum -= array[current_index-n]
        if current_sum > max_sum and current_index >= n-1:
            max_sum = current_sum
            max_index = current_index
        current_index += 1
    return max_sum/n, max_index-n+1

caracol · Answer

class Avg_obj():
    def __init__(self,array,amount):
        self.numbers= amount
        print(array)
        print(amount)
        if ((array==None) or (len(array)= len(arr)) and (amount>0) ):
        return

    elif (amount==0):
        tmp_avg= sum / curr_max_obj.numbers
        if (tmp_avg > curr_max_obj.max_avg):
            curr_max_obj.max_avg= tmp_avg
        return
    else:
        # dont take to sum
        maxAvg(arr,amount,indx+1,sum,curr_max_obj)

        # take to sum
        sum+=arr[indx]
        indx+=1
        maxAvg(arr,amount-1,indx,sum,curr_max_obj)


# "unit tets"
ar_0= None
am_0= 5
try:
    wrapAvg(ar_0,am_0)
    print("Failed, should've rais exception")
except Exception as inst:
    print("test 0 OK")

ar_1= [1,2,3,4,5,6,7]
am_1=8
try:
    wrapAvg(ar_1,am_1)
    print("Failed, should've rais exception")
except Exception as inst:
    print("test 1 OK")

ar_2= [1,2,3,4,5,6,7]
am_2=3
assert(wrapAvg(ar_2,am_2) == 6), "test 2, shouldve printed 6"

ar_3= [1,2,3,4,5,6,7]
am_3=7
assert(wrapAvg(ar_3,am_3) == 4), "test 3, shouldve printed 4"

ar_4= [1,2,3,4,5,6,7]
am_4=0
try:
    wrapAvg(ar_4,am_4)
    print("Failed, should've rais exception")
except Exception as inst:
    print("test 4 OK")

caracol · Answer

The above answer assumes subarray can be any combination of indexes, not necessarily a "window".

Amazon

Amazon interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches