Design: Leaderboard



Similar Posts:


linkedin
github
slack

Q: Design a leaderboard, which implements three functions:

  1. add_score(player_id int, score int) float
  2. top(num int) []int
  3. reset(player_id int)

See interface defined at the bottom of this post.

A: The most challenging part is how to deal with reset function. Link: Google Play Games Services: reset scores.

Q: How to implement hide(player_id int) function?

Q: [Scaling] What if you have 10 million users?

A: Some consideration about the use cases might deserve dicussions:

  • Is it acceptable only top #10K users could see their exact ranking?
  • What the interval of the game/competition is?

Interfaces:

/*
Exercise Goals:
 
- The goal of this exercise is to show us how you apply software engineering principles to create a maintainable software solution.
 
How to approach this:
 
    - Don't worry about persistence. It would make sense here, but for this exercise only use in-memory data structures.
    - Don't worry about tricks or "gotchyas", as there aren't any.
    - Just focus on writing clean maintainable code.
 
Specification:
 
  Create a class LeaderBoard whose interface includes the following methods:
 
  Method Name: add_score
 
    - Add a new score to the player's average. If a player doesn't exist in the 
    LeaderBoard, they will be automatically added.
 
    Args:
 
            player_id (Integer): The player's ID.
            score (Integer): The score to record for the player
 
    Returns:
 
            Double: The new average score for the given player
 
  Method Name: top
 
      - Get the top player_ids on the leaderboard ordered by their average scores
      from highest to lowest
 
      Args:
 
              num_players (Integer): The maximum number of player_ids to return
 
      Returns:
 
              List<Integer>: a list of player_ids
 
  Method Name: reset
 
      - Removes any scoring information for a player, effectively 
      resetting them to 0
 
      Args:
 
              player_id (Integer): The player's ID.
 
Example Usage:
 
 
  // Create a new LeaderBoard Instance
  LeaderBoard leader_board = new LeaderBoard();
 
  // Add scores for players to the LeaderBoard
  leader_board.add_score(1, 50); // 50.0
  leader_board.add_score(2, 80); // 80.0
  leader_board.add_score(2, 70); // 75.0
  leader_board.add_score(2, 60); // 70.0
  leader_board.add_score(3, 90); // 90.0
  leader_board.add_score(3, 85); // 87.5
 
  // Get top positions for the leaderboard
  leader_board.top(3); // [3, 2, 1]
  leader_board.top(2); // [3, 2]
  leader_board.top(1); // [3]
 
  // Reset a player 3's scores
  leader_board.reset(3); // void
 
  // Player 3 is now at the bottom of the leaderboard
  leader_board.top(3); // [2, 1, 3]
 
Expected values
 
  - Player IDs will always be positive integers small enough to be 
  stored as a signed 32-bit integer Scores are integers ranging from 0-100
 
 
We have provided stubbed out code and tests for you below. Please note that these tests are not exhaustive and do not cover all corner cases. We recommend extending the given tests to ensure your code is correct.
*/
 
// Your code goes here. Feel free to make helper classes if needed
class LeaderBoard {
   
  class player{
    int player_id;
    int num_score = 0;
    int total_score = 0;
    double average_score = 0;
    public player(int player_id) {
      this.player_id = player_id;
    }
  }
  }
   
  public List<Integer> top(Integer max) {
  }
   
  public List<Integer> button(Integer max) {
  }
 
  public void reset(Integer player_id) {
   
  }
 
}
 
 
// Test code here
class Solution {
  public static void main(String[] args) {
    LeaderBoard leaderBoard = new LeaderBoard();
    leaderBoard.add_score(1, 50);
    System.out.println(leaderBoard.add_score(2, 80) == 80);
    System.out.println(leaderBoard.add_score(2, 70) == 75);
    System.out.println(leaderBoard.add_score(2, 60) == 70);
    System.out.println(leaderBoard.add_score(3, 90) == 90);
    System.out.println(leaderBoard.add_score(3, 85) == 87.5);
 
    
    System.out.println(leaderBoard.top(3).equals(Arrays.asList(3, 2, 1)));  
    System.out.println(leaderBoard.top(2).equals(Arrays.asList(3, 2)));
 
    leaderBoard.reset(3);
 
    System.out.println(leaderBoard.top(3).equals(Arrays.asList(2, 1, 3)));
  }
}

Share It, If You Like It.

Leave a Reply

Your email address will not be published. Required fields are marked *