8

ソフトウェア エンジニアの就職面接で、この質問の 1 つを読みました。

1000 の Web サイトと 1000 のユーザーがいる場合、リアルタイムで次のクエリを実行できるようにプログラムとデータ構造を作成します。ウェブサイトにアクセスしたすべてのユーザーのリストを取得します。

彼らは一種の疑似コードまたは設計アルゴリズムを望んでいたと思います..

これについて何かヒントを教えてもらえますか？

4

5 に答える 5

3

1つ確かなことは、両方のクエリに回答できるようにするには、ユーザーが特定のWebサイトにアクセスしたことを意味するすべてのペアを保存する必要があります。だから私が提案するのは次のとおりです。

あなたは構造を持っています：

struct VisitPair{
  int websiteId;
  int userId;
  VisitPair* nextForUser;
  VisitPair* nextForWebsite;
};

nextForUserは、指定されたユーザーの次のペアを指します。指定されたユーザーの次のペアがない場合はNULLを指します。同様に、nextForWebsiteはwebSiteの次のペアを指します。ユーザーとウェブサイトは次のようになります。

struct User {
  char* name;
  VisitPair* firstPair;
};

struct Website {
  char* url;
  VisitPair* firstPair;
};

websitesWebサイトとユーザーの両方が配列に格納されていると仮定します。たとえば、これらの配列はとですusers。新しいvisitPairを追加するのは比較的簡単です。

void addNewPair(int siteId, int userId) {
  VisitPair* newPair = (VisitPair*)malloc(sizeof(VizitPair));
  newPair->nextForUser = users[userId]->firstPair;
  users[userid]->firstPair = newPair;
  newPair->nextForWesite = websites[siteId]->firstPair;
  websites[siteId]->firstPair = newPair;
}

WebサイトのすべてのユーザーとユーザーのすべてのWebサイトの印刷は、リストを反復処理するだけで実行できるため、それを実行できるはずです。

要するに、私が作成するのは、2つのリストが統合された構造です。これは答えに関して線形の複雑さを持ち、ペアを追加するための一定の複雑さを持っているので、より複雑な解決策はあり得ないと思います。

お役に立てれば。

于 2012-07-04T07:35:43.870 に答える
3

Web サイトとユーザーごとに、訪問者と訪問した Web サイトのリンク リストをそれぞれ保持します。ユーザーが Web サイトにアクセスするたびに、ユーザー リンク リストと Web サイト リンク リストにエントリを追加します。

これにより、メモリのオーバーヘッドが最小限になり、更新とクエリが高速になります。

于 2012-07-04T07:44:51.493 に答える
3

サイトの数とユーザーの数の両方が制限されており、事前にわかっているため、1000 x 1000 次元の 2D 配列を使用できます。ユーザーは 1 つの次元であり、Web サイトは別の次元です。配列はブール配列になります。

bool tracker[1000][1000] ;

ユーザー x が Web サイト y にアクセスすると、1 ( true ) としてマークされます。

tracker[x][y] = 1;

Web サイト J を訪問したすべてのユーザーを返すには、値が 1 である列 J のすべての値を返します。

ユーザー i が訪問したすべての Web サイトを返すには、値 1 を持つ行 i のすべての値を返します。

ルックアップの複雑さは O(n) ですが、このアプローチはスペース効率が高く、更新は 0(1) です。これは、ユーザーを Web サイトのリンク リストに追加したり、Web サイトを追加したりするのに O(n) の複雑さが必要になるリンク リストとは異なります。ユーザーのリンクされたリストに。

于 2012-07-04T07:56:44.047 に答える
1

投稿された回答の概要は次のとおりです。

mをサイト数、nをユーザー数とします。データ構造ごとに、更新、応答の複雑さを示します。得る。

  • リンクリストの2つの配列。O（1）、それぞれ O（len（answer））。
  • m×n行列。O（1）、それぞれ O（m）またはO（n）。ほとんどのユーザーがほとんどのサイトにアクセスする場合はメモリ使用量が最小になりますが、ほとんどのユーザーが少数のサイトにのみアクセスする場合は、スペースと時間は最適ではありません。
  • セットの2つの配列。O（log m）またはO（log n）、それぞれ。O（len（answer））。

izomorphiusの答えは、リンクリストに非常に近いものです。

O（len（answer））は、回答全体を読み取るのに必要な時間ですが、セットとリストの場合、nextO（1）も保証されるメソッドを持つ0（1）のイテレーターを取得できます。

于 2012-07-05T07:54:49.947 に答える
1

一般に、N人のユーザーとMのサイトには、次のようなクエリ用の 2 つのマップがあります。

map<user, set<site> > sitesOfUser;
map<size, set<user> > usersOfSite;

ユーザーuがサイトsにアクセスすると、これを更新します

sitesOfUser[ u ].insert( s );
usersOfSite[ s ].insert( y );

ここでは、重複を避けるためにsetを使用しています。重複が問題ない場合 (または後で処理する場合)、別のログを一覧表示して更新時間を短縮できます。 この場合、更新にはO( logN + logM )時間 (または単にO( logN )、上記を参照) がかかり、クエリにはO( logN )時間かかります。

特定のケースでは、サイトとユーザーの最大数が多すぎず、事前にわかっている場合 ( Kとしましょう)、次のような 2 つの配列を使用できます。

set<site> sitesOfUser[ K ];
set<user> usersOfSite[ K ];

ここでは、更新にO( logN )時間 (重複した情報が問題にならず、リストまたは別の線形コンテナーを使用している場合は O(1)) と、クエリにO(1)時間を取得します。

于 2012-07-04T07:57:14.827 に答える