設計一個大數據的算法

我讀了這個問題之一被要求接受軟件工程師的求職面試。設計一個大數據的算法

如果有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

設計一個大數據的算法

回答

相關問題