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學生最終得分

回答

相關問題