makispaiktis

DCP33 - Medians in Sublists

Sep 21st, 2020
896
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. This problem was asked by Microsoft.
  3. Compute the running median of a sequence of numbers. That is, given a stream of numbers, print out the median of the list so far on each new element.
  4. Recall that the median of an even-numbered list is the average of the two middle numbers.
  5. For example, given the sequence [2, 1, 5, 7, 2, 0, 5], your algorithm should print out:
  6. 2
  7. 1.5
  8. 2
  9. 3.5
  10. 2
  11. 2
  12. 2
  13. '''
  14.  
  15. def median(sublist):
  16.     n = len(sublist)
  17.     sublist = sorted(sublist)
  18.     if n % 2 == 0:
  19.         return 0.5 * (sublist[int(n/2)-1] + sublist[int(n/2)])
  20.     else:
  21.         return sublist[int((n-1)/2)]
  22.  
  23. def medians(myList):
  24.     result = list()
  25.     result.append(myList[0])
  26.     for i in range(1, len(myList)):
  27.         sublist = myList[0:i+1]
  28.         result.append(median(sublist))
  29.     return result
  30.  
  31. # MAIN FUNCTION
  32. print(medians([2, 1, 5, 7, 2, 0, 5]))
  33. print(medians([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))
RAW Paste Data