From a mock interview question

above_average_subarrays.py

"""
Above-Average Subarrays
You are given an array A containing N integers. Your task is to find all subarrays whose average sum is greater 
than the average sum of the remaining array elements. You must return the start and end index of each subarray in sorted order.
A subarray that starts at position L1 and ends at position R1 comes before a subarray that starts at L2 and ends at 
R2 if L1 < L2, or if L1 = L2 and R1 ≤ R2. Note that we'll define the average sum of an empty array to be 0, and 
we'll define the indicies of the array (for the purpose of output) to be 1 through N. A subarray that contains a 
single element will have L1 = R1.

Signature
  Subarray[] aboveAverageSubarrays(int[] A)

Input
  1 ≤ N ≤ 2,000
  1 ≤ A[i] ≤ 1,000,000

Output
  A Subarray is an object with two integer fields, left and right, defining the range that a given subarray covers. 
  Return a list of all above-average subarrays sorted as explained above.

Example 1
  A = [3, 4, 2]
  output = [[1, 2], [1, 3], [2, 2]]
  The above-average subarrays are [3, 4], [3, 4, 2], and [4].
"""

import unittest


class Solution:
    def above_average_subarrays(self, n, arr):
        above_average = []

        for idx in range(len(arr)+1):
            for jdx in range(idx):
                # get the sum of a sub array slice between jdx and idx
                a_sub = arr[jdx:idx]
                a_avg = sum(a_sub)/len(a_sub)

                # create copy of main array and remove sub array slice
                # to get sum of left over elements
                b_avg = arr.copy()
                del b_avg[jdx:idx]

                # if empty list, b_sum is 0
                if b_avg:
                    b_avg = sum(b_avg)/len(b_avg)
                else:
                    b_avg = 0

                # compare and add if sub array average is higher
                if a_avg > b_avg:
                    above_average.append([jdx+1, idx])

        return sorted(above_average)


class TestSolution(unittest.TestCase):
    def test_first(self):
        solution = Solution()
        array = [3, 4, 2]
        answer = [[1, 2], [1, 3], [2, 2]]
        self.assertEqual(
            solution.above_average_subarrays(len(array), array),
            answer
        )


if __name__ == '__main__':
    unittest.main()