Find the maximum average score of students

Example,

Question: Return the maximum average score of students
Input: [[“ann”, 40], [“ann”, -20], [“cat”, 50], [“cat”, 60], [“tom”, 30]]
Output: 55

Solution 1: Group all the scores of the same student in a dictionary, then run through dictionary to find the max average score

time complexiity: O(n)
space complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import sys

def maxAverageScore(scores):
if len(scores) == 0:
return 0

scoreHashtable = {}

for i in scores:
name = i[0]
score = i[1]
if scoreHashtable.get(name):
scoreHashtable[name].append(score)
else:
scoreHashtable[name] = [score]

maxAverageScore = -sys.maxsize - 1
for j in scoreHashtable.values():
currentAverageScore = sum(j) / len(j)
if maxAverageScore < currentAverageScore:
maxAverageScore = currentAverageScore

return maxAverageScore


scores = [["ann", 40], ["ann", -20], ["cat", 50], ["cat", 60], ["tom", 30]]

print(maxAverageScore(scores)) # 55.0

Solution 2: Sort the scores by name, then go through the scores again to find the maximum score

time complexiity: O(nlogn)
space complexity: O(1) because we sort in place

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys

def maxAverageScore(scores):
if len(scores) == 0:
return 0

scores.sort(key=lambda x: x[0])
totalScore = 0
count = 1
maxAverageScore = -sys.maxsize - 1

for i in range(len(scores)):
isLastValue = i == len(scores) - 1
isStudentDifferent = (
scores[i][0] != scores[i + 1][0] if i < len(scores) - 1 else True
)
if isLastValue or isStudentDifferent:
totalScore += scores[i][1]
currentAverageScore = totalScore / count
if maxAverageScore < currentAverageScore:
maxAverageScore = currentAverageScore
count = 1
totalScore = 0
else:
count += 1
totalScore += scores[i][1]

return maxAverageScore

scores = [["ann", 40], ["ann", -20], ["cat", 50], ["cat", 60], ["tom", 30]]

print(maxAverageScore(scores)) # 55.0

Interesting,

I should learn more built in functions.