數據結構搜索記錄

Question

面試問題Panel ..Web應用程序用戶可以選擇喜歡的運動，一個用戶擁有一些Favorite sports.e.g用戶John擁有足球，足球，網球等收藏夾運動。用戶Alen擁有BaseBall，BasketBall的最愛運動。

考慮百萬用戶，數據結構中的哪個算法用於搜索與足球或scoccer關聯的用戶。

首先我給出了一個HashMap的答案，但面試小組告訴我這會導致內存問題，另一種方式我可以使用二叉搜索樹，但他不滿意答案。 任何人都可以請向我解釋什麼是使用DS算法讓所有用戶喜愛的運動的好方法。

Answer 1

最簡單的解決方案是通過將用戶作爲鍵和運動列表映射爲您所提到的值來使用HashMap。在面試時首先使用這種解決方案很常見，看看它是否符合面試官的要求。

更好的解決方案可以是建立用戶和運動的圖形，其中將存在來自運動項節點即足球到用戶節點即foo，bar的單向邊緣。對於任何關於運動項目即足球的查詢，我們可以考慮football作爲源節點來遍歷該圖。所有將被遍歷的節點都是其中最喜歡的運動之一是足球的用戶列表。這樣，它將節省空間。

考慮遍歷每個查詢的圖的時間複雜度，其中圖遍歷的時間複雜度爲O(E)其中E = all users在最壞的情況下。因此，我們可以使用HashMap緩存一些頻繁的查詢結果。再一次，爲了應對空間，我們可以用HashMap模擬LRU緩存。

希望它有幫助！