设计大数据的算法

Question

我读了这个问题之一,被要求接受软件工程师的面试.

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

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

你们能为此提出任何建议吗？

Answer 1

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

你有一个结构：

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

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

打印网站的所有用户和用户的所有网站只需迭代列表即可完成，因此您应该能够做到这一点。

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

希望这可以帮助。