c - 为大数据设计算法

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

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

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

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

希望这对您有所帮助。