8

我读到了这个问题之一，被要求参加软件工程师的工作面试。

如果有 1000 个网站和 1000 个用户，编写一个程序和数据结构，以便我可以实时查询以下内容： 1. 给定任何用户，我得到他/她访问过的所有网站的列表 2. 给定任何网站，我得到所有访问过它的用户的列表。

我认为他们想要一种伪代码或设计算法..

各位大神可以给点建议吗？

4

5 回答 5

3

有一件事是肯定的 - 为了能够回答这两个查询，您需要存储所有对，这意味着用户已经访问了给定的网站。所以我的建议如下：

你有一个结构：

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

nextForUser 将指向给定用户的下一个对，如果没有给定用户的下一个对，则为 NULL，类似地，nextForWebsite 将指向网站的下一个对。用户和网站将如下所示：

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

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

我假设 Website-s 和 users 都存储在数组中，比如这些数组是websitesand 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;
}

打印一个网站的所有用户和一个用户的所有网站是通过简单地遍历一个列表来完成的，所以你应该能够做到这一点。

简而言之，我创建的是一个集成了两个列表的结构。我不认为有一个更复杂的解决方案，因为这个解决方案具有相对于答案的线性复杂性和添加一对的恒定复杂性。

希望这可以帮助。

于 2012-07-04T07:35:43.870 回答
3

对于每个网站和用户，分别为访问者和访问的网站保留一个链接列表。每当用户访问网站时，在用户链接列表和网站链接列表中添加一个条目。

这具有最小的内存开销和快速的更新和查询。

于 2012-07-04T07:44:51.493 回答
3

由于站点数量和用户数量都是有界的并且事先已知，因此您可以使用 1000 x 1000 维度的 2D 数组，其中用户是一维，网站是另一维。该数组将是一个布尔数组。

bool tracker[1000][1000] ;

当用户 x 访问网站 y 时，它被标记为 1 ( true )。

tracker[x][y] = 1;

要返回访问过网站 J 的所有用户，返回 J 列中的所有值，其值为 1，

返回用户 i 访问的所有网站，返回第 i 行中所有值为 1 的值。

查找的复杂度为 O(n) ，但这种方法节省空间，并且更新为 0(1)，不像链表需要 O(n) 复杂度才能将用户添加到网站链表或添加网站到用户的链表。（但是在进行查找时会产生 O(1) 复杂性）。

于 2012-07-04T07:56:44.047 回答
1

这是已发布答案的摘要。

设 m 为站点数，n 为用户数。对于每个数据结构，我们分别给出了更新的复杂性。得到。

  • 两个链表数组。O（1），分别。O(len(答案))。
  • 一个 m×n 矩阵。O（1），分别。O(m) 或 O(n)。如果大多数用户访问大多数站点，则内存使用最少，但如果大多数用户仅访问少数站点，则空间和时间不是最佳的。
  • 两组数组。O（log m）或O（log n），分别。O(len(答案))。

izomorphius 的答案非常接近链表。

O(len(answer)) 是读取整个答案所需的时间，但是对于集合和列表，可以在 0(1) 中获得一个迭代器，它有一个next方法也可以保证 O(1)。

于 2012-07-05T07:54:49.947 回答
1

在一般情况下，N个用户和M个站点有两个用于查询的地图，例如

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

当用户u访问站点时，您将其更新为

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

此处使用set以避免重复。如果复制没问题（或者你稍后会处理它），你可以只列出另一个日志并减少更新时间。
在这种情况下，更新将花费O( logN + logM )时间（或仅O( logN )，见上文），查询将花费O( logN )时间。

在您的特定情况下，当站点和用户的最大数量不是太多并且事先已知（假设它是K）时，您可以只拥有两个数组，例如

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

在这里，您将获得O(logN)时间进行更新（或者如果重复信息不是问题并且您使用列表或其他线性容器，则 O(1) 时间），以及O (1)时间进行查询。

于 2012-07-04T07:57:14.827 回答