3

この質問は、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 という名前を作成しました。
  • Comparator は結果の testScore を比較し、スコアが高いほど 1 を返すため、最高から最低へと並べ替えられます。
  • 指定された結果リストを反復処理し、すべてのテスト結果をマップに配置します (エントリが存在するかどうかを確認し、存在する場合: セットに追加し、存在しない場合: 新しいセットでエントリを作成し、結果をリストに追加します。
  • HashMap を反復処理し、エントリごとに最初の 5 つのセット エントリを反復処理して平均を取得し、それを別の HashMap に入れ、それを最終的に返します。

ここに私の質問があります：

  1. ソリューションの複雑さ (O) がどの程度かはわかりません。私の最善の推測は、それが O(n+n) であるということですが、よくわかりません。
  2. この問題に対するより最適な解決策はありますか?
  3. 質問に制約を追加して、返されるマップが生徒のランキング順に繰り返されるようにするとどうなるでしょうか?

PS @平均を計算する前に誰かがこの質問をしているのを見ましたか? しかし、彼はまったく不明確で、骸骨を提供しませんでした。投稿ルールに反する場合は、あらかじめお詫び申し上げます。

4

2 に答える 2

3

minHeapサイズ 5の a を使用します。

複雑さ : O(klogn) 、k =5 ==> O(logn)。そして O(n+m) 、一般に = O(max(n,m) 。あなたの場合、その O(n)。

于 2013-02-25T17:07:05.370 に答える
1

あなたのアルゴリズムはO（nLog（n））時間計算量を持っているようです。最悪の場合はnを含め、ツリーのサイズは任意です。ツリーを使用する代わりに、学生IDごとに最小ヒープを使用できます。6番目のアイテムを追加するたびに、後で最小値を削除して、常に最高の5スコアを保持するようにします。

このようにして、Droiderが説明するように、n単位の線形時間を保証します。

于 2013-02-25T17:14:54.070 に答える