CODEWITHSUNDEEP
data-structures
user3795493
user3795493

Reputation: 11

Data Structure search record

The question asked by interview Panel..Web application user can select the favorite sports, one user has a number of Favourite sports.e.g User John has Favourites sport as Football, Soccer, Tennis. User Alen has favorites sport as BaseBall,BasketBall.

Consider Million of users, Which algorithm in Data structure uses to search users associated with Football or scoccer.

First I gave an answer as HashMap but interview panel told me it cause Memory issue, another way I can use Binary Search tree, but he is not satisfied with the answer. Can anyone please explain to me what is a good way to get all users with favorite sport using DS algorithm.

Upvotes: 0

Views: 64

Answers (1)

Kaidul
Kaidul

Reputation: 15855

The easiest solution is to use HashMap by mapping user as key and list of sports as value as you mentioned. And its very common to come with this solution first at interview to see if it satisfies the interviewers.

A better solution can be building a graph of users and sports where there will be uni-directional edge from sport item node i.e. football to user nodes i.e. foo, bar. For any query for sport item i.e. football, we can traverse the graph considering football as source node. All the nodes which will be traversed are the list of users whose one of the favorite sports is football. This way, it will space efficient.

Considering the time complexity of traversing the graph for each query, where time complexity of graph traversal is O(E) where E = all users in worst case. So, we can cache some frequent query result using HashMap. Again, to cope with space, we can simulate LRU cache with HashMap.

Hope it helps!

Upvotes: 1

Related Questions