数据结构搜索记录

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缓存。

希望它有帮助！