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].

Complete Code:

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]