这个问题出现在 Amazon.com 面试的在线测试中。确切的问题是:
Given a list of test results (each with a test date, Student ID, and the student’s Score), return the Final Score for each student. A student’s Final Score is calculated as the average of his/her 5 highest test scores. You can assume each student has at least 5 test scores.
Use the following skeleton for your solutions
class TestResult{
int studentId;
Date testDate;
int testScore;
}
public Map<Integer, Double> getFinalScores(List<TestResult> resultList){
return null;
}
我的解决方案是这样的:
- 我创建了一个
HashMap<Integer, SortedSet<TestResult>
称为 studentIdToResultSet。 - Comparator 将比较结果中的 testScore,并为较高的分数返回 1,以便从高到低排序。
- 遍历给定的结果列表并将所有测试结果放入映射中(检查条目是否存在,如果存在:添加到集合中,如果不存在:使用新集合创建条目并将结果添加到列表中。
- 遍历 HashMap,对于每个条目,我遍历前 5 个集合条目并获取平均值,将其放入另一个 HashMap,最终返回。
现在这是我的问题:
- 我不知道我的解决方案的复杂性 (O) 是多少。我最好的猜测是它是 O(n+n),但我不确定。
- 这个问题是否有更优的解决方案?
- 如果我向问题添加一个约束条件,即返回的 map 必须按照学生排名的顺序进行迭代,会怎样?
附言之前看到有人问过这个问题@Calculating the average?但他很不清楚,也没有提供骨架。如有违反发帖规则,敬请见谅。
最佳答案
使用大小为 5 的 minHeap
。
复杂度:O(klogn),k =5 ==> O(logn)。和 O(n+m) ,通常 = O(max(n,m) 。在你的情况下它是 O(n)。
关于java - Amazon.com 学生最终成绩,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15072245/