Amazon SDE Intern India [under process]

Round 1

Questions:

1. Question 1: Maximize Memory Points
   An array of integers (memory) was provided. Our task was to maximize the memory points. For each memory point in the array, we must consider all the previous memory points as well. We can take any permutation of the memory array that maximizes the total memory gained.

   Example:
   memory = [3, 4, 5]

   • Permutation 1: [3, 4, 5]
     Memory points = 3 + (3 + 4) + (3 + 4 + 5) = 3 + 7 + 12 = 22
   • Permutation 2: [4, 3, 5]
     Memory points = 4 + (4 + 3) + (4 + 3 + 5) = 4 + 7 + 12 = 23
   • Permutation 3: [5, 4, 3]
     Memory points = 5 + (5 + 4) + (5 + 4 + 3) = 5 + 9 + 12 = 26

   In Permutation 3, we get the maximum memory points = 26, which is the correct and expected answer.

   My Solution: (Passed all test cases)

   def maximizeTotalMemory(memory):
       memory.sort(reverse=True)
       result = 0
       curr_sum = 0
       for num in memory:
           curr_sum += num
           result += curr_sum
       return result

2. Question 2: Count Offer Periods
   An array of integers (sales) was provided. Our task was to count all "offer periods." An offer period is a range (i - j) such that (i < j), (0 <= i < n), and (i + 1 <= j < n), which satisfies the following condition:

   • min(sales[i], sales[j]) > max(sales[i + 1], sales[i + 2], ..., sales[j - 1])

   We need to return the count of all such offer periods.

   Example:
   sales = [3, 2, 8, 6]

   • Range [0, 2]:
     min(3, 8) = 3 and max(2) = 2
     Since 3 > 2, it's an offer period.
   • Range [0, 3]:
     min(3, 6) = 3 and max(2, 8) = 8
     Since 3 < 8, it's not an offer period.
   • Range [1, 3]:
     min(2, 6) = 2 and max(8) = 8
     Since 2 < 8, it's not an offer period.

   The total number of offer periods is 1, which is the correct answer to return.

   My Solution: (Passed most test cases, but 5 failed due to time complexity)

   def getTotalOfferPeriods(sales):
       offer_periods = 0
       max_value = None
       for i in range(len(sales)):
           if i < len(sales) - 1:
               max_value = sales[i + 1]
           for j in range(i + 2, len(sales)):
               min_value = sales[i]
               if sales[j] < min_value:
                   min_value = sales[j]
               if min_value > max_value:
                   offer_periods += 1
               if sales[j] > max_value:
                   max_value = sales[j]
       return offer_periods