设计一个大数据的算法

我读了这个问题之一被要求接受软件工程师的求职面试。设计一个大数据的算法

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

我认为他们想排序的伪代码或设计算法..

你们可以给这个任何提示？

来源

2012-07-04 rain

二维阵列？........ –

这里只有一百万点需要考虑。在目前的大多数情况下，我认为这不是一个足够大的数据集来保证'聪明'的治疗。 –

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

你有一个结构：

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

我认为这两个网站-S和用户存储在阵列中，说这些阵列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; 
}

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

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

希望这会有所帮助。

来源

2012-07-04 07:35:43

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

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

来源

2012-07-04 07:44:51 tskuzzy

+1。明确提到需要2个数组，一个用于网站，另一个用于用户，每个元素都是（指向一个）链接列表。这两个网站和用户必须由整数编号从0 –

由于网站数量和用户数量都是有限的，并且事先已知，所以您可以使用尺寸为1000 x 1000的二维数组，其中用户为一维，网站为另一维度。该数组将是一个布尔数组。

bool tracker[1000][1000] ;

当用户x访问网站y时，它被标记为1（真）。

tracker[x][y] = 1;

要回到谁访问过的网站J均以用户，回报在J列所有值，具有值1，

可以返回用户我访问的所有网站，在行返回所有值我，有价值1。

查找的复杂度是O（n），但是这种方法是节省空间的，并且更新为0（1），，不像链表需要O（n）复杂性来将用户添加到网站链表，或者将网站添加到用户的链接列表中（但是在查找时会导致O（1）的复杂性）。

来源

2012-07-04 07:56:44 DhruvPathak

我很抱歉，但我不同意这个答案。该方法不具有空间效率，因为它总是使用1000 * 1000的内存，无论对的数量如何。此外，链接列表中还有一些常量。阅读我的答案。 –

@izomorphius我部分同意你的看法，但考虑到网站访问量可能出现大量事件，1000x1000布尔值每个比特都会比节点好。 – DhruvPathak

无论这是否有效地利用空间，或者它是否比链接列表方法更具空间效率，取决于我们所没有的数据 - 密度（或稀疏性，如果您愿意的话）矩阵。所以我们做假设...... –

在一般的情况下与ñ用户和中号网站有两个地图查询，如

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

当用户ü访问网站小号你

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

更新此

设置这里用来避免du折叠。如果重复是可以的（或者稍后您会处理它），那么您可以只使用列表，并将更新时间减少另一个日志。
在这种情况下更新将需要O（+ logN个10gm的）时间（或只是O（logN）的，见上文）和查询将采取O（logN）的时间。

在当网站和用户的最大数量不太多，预先知道你的具体情况（让我们说这是ķ）你可以有两个数组一样

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

在这里你会得到O（logN）的时间更新（或O（1）如果复制的信息是不是一个问题，你用列表或一些其它线性容器），和O（1）时间查询。

来源

2012-07-04 07:57:14

你写过“O（logN * logM）”，但不是“O（logN + logM）”吗？ – jrouquie

另外，在这个数据结构中，更新确实是O（logN + logM），但是“获取她访问的所有站点的列表”osΘ（M），因为这是答案的长度。 – jrouquie

@jrouquie：谢谢，修正了第一个问题。但我不同意第二个 - 你在O（logN）中得到了答案（更确切地说 - 一个指向答案的指针），并且Θ（M）将是复制它所需的时间，我不认为它是一个查询的一部分。 –

以下是发布的答案摘要。

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

两个链表的数组。 O（1）， O（LEN（回答））。
m×n矩阵。 O（1）， O（m）或O（n）。大多数用户访问大多数网站时，内存使用量最少，但如果大多数用户只访问少数网站，则空间和时间不是最佳。
两组数组。 O（log m）或O（log n）， O（LEN（回答））。

izomorphius的答案非常接近链接列表。（len（answer））是读取整个答案所需的时间，但对于集合和列表，可以得到一个迭代器在0（1）中，该方法的next方法也保证了O（1 ）。

来源

2012-07-05 07:54:49 jrouquie

好，但我认为izomorphius的答案使用与2个单独链接列表相同数量的内存（假设没有固定的per-'malloc（）'开销）。 'VisitPair'可以拆分成2个'struct'，每个''struct'有一个ID和一个下一个指针，并且它在程序运行中的每个实例对应于这些'struct'的每一个的一个实例。 –

你是对的，已更新。 – jrouquie

设计一个大数据的算法

回答

相关问题