3

これはAmazonからのインタビューの質問です。

ある日にWeb ページを訪問した顧客uのリストを指定して、正確な日に Web サイトを訪問し、少なくとも個別のページを訪問したはずの顧客を取得するためのデータ構造を設計します。wdkm

とは大きな数uであると仮定します。wd

この情報をどのように保存しますか? たぶん、ハッシュマップ、ツリーなどを使用できます。

4

3 に答える 3

4

仮定:

いくつかの Web ページを提供し、その Web ページを正確に何日間訪問し、合計で少なくとも個別のページを訪問jしたユーザーのリストを要求するクエリがあります。km

以下では、「map」=「hashmap」と仮定します。これは、理想的には一定時間のクエリを提供します。要素数の対数コストで「ツリーマップ」を使用することもできます。「set」、「hashset」、「treeset」についても同様です。

入力は静的ではないと想定していますが、静的である場合でもアプローチを変更するつもりはありません。

基本的な考え方:

  • 各ユーザーについて、Web ページからカウントと最終訪問日へのマップを作成します。Web ページのマップへのユーザー識別子のマップを作成できます。

  • ユーザーがページにアクセスするたびに:

    • 新しいページの場合は、そのページのカウントを 1 にし、最後にアクセスした日を含むマップ エントリを作成するだけです。

    • それ以外の場合、その日が最後に訪れた日と同じ場合は何もしません。

    • それ以外の場合は、カウントを増やし、最後にアクセスした日を更新します。

    • 更新ごとの合計時間 =O(1)

  • クエリの場合:

    • すべてのユーザーをループ -O(u)

    • そのユーザーのページを検索し、カウントが一致することを確認します -O(1)

    • マップのカウントが>= m-O(1)

    • クエリあたりの合計時間 =O(n)

改良点:

Web ページから一意の ID への別のマップを作成できます(上記のマップでは、URL の代わりに一意の ID を使用することは明らかです)。複雑さを実際に変えることはありませんが、空間と時間の両方の複雑さを一定の要因で改善する必要があります。

かなりのスペースを犠牲にして、次のことができます ( からのマップを取得することに加えてBasic idea)。

  • Web ページごとに、ユーザー ID のセットの配列を持ちます。配列内のインデックスは、正確な日iにそのページを訪れたすべてのユーザーのセットです。i

  • ユーザーがページにアクセスするたびに:

    • と同じことをするBasic idea

    • ユーザーをそのページの現在の訪問数から新しい訪問数に移動します (または、新しい場合は 1 訪問セットに挿入します)。

    • 更新ごとの合計時間 =O(1)

  • クエリの場合:

    • kの正確な日に特定のページにアクセスしたすべてのユーザーを見つけることができますO(1)。

    • ここから、ユーザーの小さなリスト (たとえば、ユーザーがいるpとします) を実行し、各ユーザーのマップの数を確認します ( O(1))。

    • クエリあたりの合計時間 =O(p)

私が何かを見逃した場合は、遠慮なく指摘してください。

于 2013-07-08T14:25:48.160 に答える
1

最も単純な構造は、RDBMS が行うことをエミュレートすることです。

1.すべての基本情報を含むオブジェクトを用意します: (Customer、Days-Count、Distinct-Pages-Count)

2.次に、(Days-Count, Distinct-Pages-Count) をキー (B-tree など) として使用して、インデックスとして機能する Tree を追加します。

3.また、Customer のキーを持つ別のインデックス タイプの構造を持つこともできます。そうすれば、すぐに情報を更新できます

4.最後に、閲覧中のページがユニークかどうかを判断するには、より詳細な情報が必要です。これには、顧客の下に個別のページ情報を保存することが含まれます (これが特定の日またはすべての日に個別であることを意味するかどうかは、質問から明らかではありません)。

于 2013-07-08T14:40:46.263 に答える
1

2 つのハッシュ マップを使用して実装します。

  1. hash map<customerId,HashSet<webpages>>
  2. hash map<customerId,HashSet<days>>

新しい顧客 ID の場合は、新しいハッシュセットを作成してそこに挿入します。それ以外の場合は、その日または Web ページを既存の顧客のハッシュ セットに入れます。

各顧客 ID についてlength>=m、最初のハッシュ マップのセットを参照し、2 番目のハッシュ マップ セットのlength=k出力を顧客に表示します。

于 2013-12-01T15:01:01.223 に答える