一种大数据的算法设计

Question

我读到了一个被问到要面试软件工程师的问题。

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

我想他们想要一种伪代码或者设计算法。

你们能给点建议吗？

Answer 1

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

你有一个结构：

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;
};

我假设网站和用户都存储在数组中，比如这些数组是websites和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;
}

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

简而言之，我创建的是一个包含两个列表的结构。我认为不可能有一个更复杂的解决方案，因为这个解决方案在答案方面具有线性复杂性，而对于增加一对答案则具有恒定的复杂性。

希望这能有所帮助。

Answer 2

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

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

Answer 3

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

bool tracker[1000][1000] ;

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

tracker[x][y] = 1;

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

若要返回用户i访问的所有网站，请返回第一行中具有值1的所有值。

查找的复杂性是O(n)，但是这种方法是空间高效的，并且更新是0(1)，不像链接列表那样需要O(n)复杂性来将用户添加到网站链接列表，或者将网站添加到用户的链接列表中。(但这在进行查找时给出了O(1)复杂性)。