Amazon.com学生最终得分

这个问题是在Amazon.com面试的在线测试中。确切的问题是：Amazon.com学生最终得分

给出测试结果列表（每个测试结果都包含测试日期，学生ID和学生分数），返回每个学生的最终分数。学生的最终分数是以他/她的5个最高考试分数的平均值计算的。你可以假设每个学生至少有5个考试成绩。

使用下面的骨架为您的解决方案

class TestResult{ 
    int studentId; 
    Date testDate; 
    int testScore; 
} 

public Map<Integer, Double> getFinalScores(List<TestResult> resultList){ 
    return null; 
}

我的解决办法是这样的：

我创建了一个名为HashMap<Integer, SortedSet<TestResult> studentIdToResultSet。
比较器将比较结果中的testScore，并返回1以获得更高的分数，以便它将排序从最高到最低。
遍历给定的搜索结果列表，并把所有的测试结果在地图（检查是否存在条目，如果是：添加设置，如果没有：创建新组项目，并在列表中添加的结果
遍历HashMap的，因为我遍历第5个集条目，并获得平均每个条目，把在另一个HashMap的，这是我最终回归

现在，这里是我的问题：

我不知道我的解决方案的复杂性（O）是什么，我最好的猜测是它是O（n + n），但我不确定。
有没有更好的解决这个问题的方法？
如果我为问题添加了一个约束，返回的地图必须按照学生排名的顺序进行迭代，该怎么办？

P.S.我看到有人在@Calculating the average?之前问过这个问题，但他还不太清楚，并没有提供骨架。如果这违反了发布规则，我提前道歉。

来源

2013-02-25 Eki

O（N + N）降低到O（n）的 – 2013-02-25 17:06:01

为什么排序？ – SparKot 2013-02-25 17:18:29

的名单？让五最高的测试结果......最后的分数意味着是“五个最佳”场景...... – Eki 2013-02-26 01:09:21

使用大小5.

复杂的minHeap：O（klogn）中，k = 5 ==> O（logn）时间。和O（n + m），一般= O（max（n，m）。在你的情况下它的O（n）。

来源

2013-02-25 17:07:05 h4ck3d

In当然，堆是空的，我们有一个大小= 5.每次我们看到标记<堆[root]，我们将推它并heapify。 – h4ck3d 2013-02-25 17:11:53

你说得对。这是保证每个堆操作时间不变的正确方法。喜欢。 – 2013-02-25 17:12:39

谢谢！ MinHeap是否有Java实现？我甚至没有想到写我自己的结构。此外，感谢您对复杂性的说明 – Eki 2013-02-26 01:17:53

你的算法似乎有O（nLog（n）可以有任意大小，包括n在最坏的情况下，而不是使用树，你可以为每个学生id使用一个最小堆，每次你添加第六个项时，之后删除最小值，以便它始终保持最佳状态5分。

这样你保证n的线性时间，因为Droider解释。

来源

2013-02-25 17:14:54

并跟踪最小值。只有当它大于设定的最小值时，分数才会被替换。 – SparKot 2013-02-25 17:17:27

@DoSparKot：我看不到这个优化的真正收益（具体而言，不是时间复杂度） – 2013-02-25 17:19:22

是的，它并不影响时间复杂度。 – SparKot 2013-02-25 17:30:44

Amazon.com学生最终得分

回答

相关问题