507. Design data structure for players and ranks

Given a list of player names and their scores, design a data structure that can support following modules in optimal time-

• updateEntry(String name) - Increase the player score with "name" by 1. If no player with name is present then add a player with score 1.
• getEntryFromRank(int rank) - Get the players with the given rank. 
• addPlayer(String name, int score) - Add player and score. 

Example:

addPlayer("Carl", 70)
addPlayer("Sam", 80)
addPlayer("Bob", 70)
getEntryFromRank(2) = Players with rank 2: [Carl, Bob]
updateEntry("Carl")
getEntryFromRank(2) = Players with rank 2: [Carl]

Approach:

• Use two maps, Hashmap and TreeMap. 
• Construct a Hashmap with the player as key and their score as value, call it as playerMap.
• Construct a Treemap with score as key and list of players with that score as value, call it as rankMap. Override treemap compare function to maintain the key in decreasing order.
• addPlayer(String name, int score) - Add player and its score into playerMap and check if score is present in rankMap then add player name to the player list else create a new entry into rankMap.
• updateEntry(String name) - check if player is present in playerMap, 
  • If yes then get the player's existing score and increase the score in map by 1, call it a new score. Get the player list from rankMap with existing score and remove the player name. Now add player name to new score  - if the new score is present in rankMap then add player name to the player list else create a new entry into rankMap.
  • If No, then add player with score 1 in playerMap and rankMap, add the player against score 1.
• getEntryFromRank(int rank) - If rank is greater than rankMap size, print invalid rank and return. If rank is valid then get the keys of rankMap (which are scores) and return the index[rank-1].

Output:

Players with rank 2: [Carl, Bob]
Players with rank 5: [Joe]
Players with rank 6: [Xoe]
Players with rank 1: [Sam]
Invalid rank: 10
Players with rank 2: [Carl]