# 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