Design a Leaderboard or Low-Level Design of a Leaderboard

Posted on by admin

Overview

In this tutorial, we will design a leaderboard and see the full working code for it. Below are some of the requirements for the leaderboard which we are going to design

  • AddScore(id, score) – Add score to the score of the player with playerId as id. If no such player exists then create one.
  • RestScore(id)– Reset the score to zero of the player with playerId as id
  • Top K Sum – Should be able to retrieve the top k sum from the leaderboard.
  • Top K Players – Should be able to retrieve the top k players from the leaderboard.

The first solution that comes to mind looking at this problem is to use a Min Heap + HashMap. But Min Heap is not an optimal solution if the Top K sum or Top K players are called too frequently which they will be as it is a leaderboard that is meant to show leaders. But why is it not an optimal solution and then what is the optimal solution? We will look at it in this tutorial. Let’s first see how this problem can be solved using Min Heap + Hashmap solution

Two data structures will be required

  • MinHeap– MinHeap will only be created at the time when Top K Sum or Top K players method will be called
  • Hashmap – Other than MinHeap we will also maintain a hashmap that will contain the entry for each of the players and their score. So for this hashmap the
    • The key will be playerID
    • The value will be the player’s Score

Let’s look at the Time Complexity of each of the operations in the case of the Min Heap + Hashmap solution

Add Score:

Add to the Hash Map. TC is O(1)

Reset Score

Set the value in the Hash Map to zero. TC is O(1)

Top K Sum:

Create a Min Heap of k elements. Traverse through the HashMap and add elements to the Min Heap if the score is more than the top element of the Min Heap. TC of this operation will be O(Nlogk) where N is the number of players

Top K Players:

Same as Top K Sum. TC is O(NlogK) where N is the number of players

Here we can see that Time Complexity of Top K sum and Top K Players is O(Nlogk) which is on the higher side. We can optimize it using a Balanced BST + Hashmap Solution. For a Balanced BST + Hashmap Solution below will be the Time Complexity of each of the operations

  • Add Score: O(logN)
  • Reset Score: O(logN)
  • Top K Sum: O(K)
  • Top K Players: O(K)

The Time Complexity of AddScore and ResetScore has increased at the cost of the lower Time Complexity of Top K Sum and Top K player operations. Let’s look at how it will be implemented and then compare it with Min Heap Solution later on in the tutorial.

Balanced BST + Hashmap Solution

Balanced BST solution. We are going to maintain two data structures

  • Balanced BST – We are going to use the AVL tree here. Each node in the AVL tree will store below things
    • Score
    • Player IDs with that score. We will store it on a map. Why map and not an array? So that we can easily remove a player from the node when its score changes
    • Num Player with that score. It will be equal to the number of entries in the Players Map
  • Hashmap – Other than Balanced BST we will also maintain a hashmap that will contain the entry for each of the players and their score. So for this hashmap the
    • The key will be playerID
    • The value will be the player’s Score

Comparison with Min Heap

The below table compares (Balanced BST + HashMap) to (Min Heap + Hashmap)

Assumption: N is the number of players

OperationBalanced BST + HashMapMin Heap + HashMap
Add ScoreO(logN)O(1)
Reset ScoreO(logN)O(1)
Top K SumO(k)O(Nlogk)
Top K playersO(k)O(Nlogk)

The purpose of the leaderboard is to show the top score players at all times and the board needs to be refreshed every time any score of any player changes. So we would want to optimize the Top K Sum and Top K players method more. Hence Balanced BST + Hashmap is more suited to designing the leaderboard

Implementation

Let’s look at how the implementation and design of the Balanced BST + Hashmap solution

Here is an example of how things are stored in the AVL tree

Here is how each of the operations is going to work

AddScore

For this scenario, we have two cases

  • The player already exists in the leaderboard

For this, we simply add the player to the hashmap as well as the AVL tree.

  • The player doesn’t already exist in the leaderboard

In this case, it means that the player’s score is getting changed. So in this case we will do two things. Let’s understand the two things which are required to be done using an example. For eg let’s say that the earlier score of the player was 5 and now 3 is getting added to his score. So 5 is the old score and 5+3=8 is the new score. So we will simply

  • Remove that player from the node in the AVL tree with a score of 5.
  • Add that player to the node in the AVL tree with a score of 8. If a node with a score of 8 doesn’t already exist then create it.

The TC for AddScore will be O(logN) where N is the number of players

Reset Score

In this scenario as well we have two cases

  • The player already exists in the leaderboard with a score of x

For this, we simply remove that player from the node in the AVL tree with a score of x. Check in the map if the player exists in the leaderboard. If it exists then perform the above-mentioned action

  • The player doesn’t already exist in the leaderboard

In this case, we don’t need to do anything

The TC for ResetScore will be O(logN) where N is the number of players

Retrieve the top k sum from the leaderboard

For this, we simply need to traverse the AVL tree starting with the node having the highest score, then add that score*num_players at the output sum. If NumPlayers at that AVL node is greater than k, then add score*k to the output sum. Keep repeating this process with the node with the second-highest score and then the third-highest score until the overall k score has been added.

The TC for this operation will be O(K) because it is the same as traversing K nodes in a balanced BST

Retrieve the top k players from the leaderboard.

For this, we simply need to traverse the AVL tree starting with the node having the highest score, then add all the players with that score to the output. If num players at that AVL node are greater than k, then add only k players.

Keep repeating this process with the node with the second-highest score and then third highest score until the overall k players have been added

The TC for this operation will be O(K) because it is the same as traversing K nodes in a balanced BST

Low-Level Design

In this design, we are going to use two classes

  • The first is the leaderboard class. The leaderboard class will expose all methods
    • AddScore(playerId string, scoreToAdd int)
    • Reset(playerId string)
    • TopPlayers(k int)
    • TopSum(k int)

leaderboard class will internally use AVL to return all the results

  • The second is the AVL class. This class with contain below two classes and will encapsulate all logic for implementing an AVL tree
    • AVL Tree Class
    • AVLNode class

Full Working Code

The code for AVL tree in golang has been inspired by https://github.com/karask/go-avltree

Here is the working code for the same in Go Programming Language

lederboard.go

package main

type leaderboard struct {
	avl       *AVLTree
	leaderMap map[string]int
}

func initLeaderboard() *leaderboard {
	return &leaderboard{
		avl:       &AVLTree{},
		leaderMap: make(map[string]int),
	}
}

func (this *leaderboard) AddScore(playerId string, scoreToAdd int) {
	oldScore, ok := this.leaderMap[playerId]
	newScore := oldScore + scoreToAdd
	if ok && oldScore != 0 {
		this.avl.Remove_Player_From_Score(oldScore, playerId)
		this.avl.Add(newScore, playerId)
	} else {
		this.avl.Add(scoreToAdd, playerId)
	}
	this.leaderMap[playerId] = newScore
}

func (this *leaderboard) Reset(playerId string) {
	oldScore, ok := this.leaderMap[playerId]
	if ok && oldScore != 0 {
		this.avl.Remove_Player_From_Score(oldScore, playerId)
	}
	this.leaderMap[playerId] = 0
}

func (this *leaderboard) TopPlayers(k int) []AVLItem {
	return this.avl.TopPlayers(k)

}

func (this *leaderboard) TopSum(k int) int {
	sum := this.avl.TopSum(k)
	return sum
}

avl.go

package main

type AVLTree struct {
	root *AVLNode
}

func (t *AVLTree) Add(key int, value string) {
	t.root = t.root.add(key, value)
}

func (t *AVLTree) Remove(key int) {
	t.root = t.root.remove(key)
}

func (t *AVLTree) Search(key int) (node *AVLNode) {
	return t.root.search(key)
}

func (t *AVLTree) TopPlayers(k int) []AVLItem {
	curr := 0
	output, _ := t.root.topPlayers(&curr, k)
	return output
}

func (t *AVLTree) TopSum(k int) int {
	curr := 0
	sum, _ := t.root.topSum(&curr, k)
	return sum
}

func (t *AVLTree) Remove_Player_From_Score(oldScore int, playerId string) {
	//Get AVL Node for old Score
	node := t.root.search(oldScore)
	if node.NumPlayers == 1 {
		t.root.remove(oldScore)
	} else {
		t.root.remove_player_from_score(oldScore, playerId)
	}
}

// AVLNode structure
type AVLNode struct {
	Score        int
	PlayerIDsMap map[string]bool
	NumPlayers   int

	// height counts nodes (not edges)
	height int
	left   *AVLNode
	right  *AVLNode
}

type AVLItem struct {
	Score     int
	PlayerIDs []string
}

func (n *AVLNode) topPlayers(curr *int, k int) ([]AVLItem, bool) {
	output := make([]AVLItem, 0)
	if n.right != nil {
		o, br := n.right.topPlayers(curr, k)
		output = append(output, o...)
		if br {
			return output, true
		}
	}

	i := 0
	playerIds := make([]string, 0)
	for playerId, _ := range n.PlayerIDsMap {
		if *curr < k && i < n.NumPlayers {
			playerIds = append(playerIds, playerId)
			*curr = *curr + 1
			i++
		} else {
			break
		}
	}

	output = append(output, AVLItem{n.Score, playerIds})

	if *curr == k {
		return output, true
	}

	if n.left != nil {
		o, br := n.left.topPlayers(curr, k)
		output = append(output, o...)
		if br {
			return output, true
		}
	}

	return output, false
}

func (n *AVLNode) topSum(curr *int, k int) (int, bool) {
	sum := 0
	if n.right != nil {
		s, br := n.right.topSum(curr, k)
		sum = sum + s
		if br {
			return sum, true
		}
	}

	less := 0

	if k-*curr < n.NumPlayers {
		less = k - *curr
	} else {
		less = n.NumPlayers
	}

	sum = sum + n.Score*less
	*curr = *curr + less

	if *curr == k {
		return sum, true
	}

	if n.left != nil {
		s, br := n.left.topSum(curr, k)
		sum = sum + s
		if br {
			return sum, true
		}
	}

	return sum, false
}

// Adds a new node
func (n *AVLNode) add(score int, playerID string) *AVLNode {
	if n == nil {
		m := make(map[string]bool)
		m[playerID] = true
		return &AVLNode{score, m, 1, 1, nil, nil}
	}

	if score < n.Score {
		n.left = n.left.add(score, playerID)
	} else if score > n.Score {
		n.right = n.right.add(score, playerID)
	} else {
		// if same key exists update value
		n.NumPlayers = n.NumPlayers + 1
		n.PlayerIDsMap[playerID] = true
	}
	return n.rebalanceTree()
}

// Removes a node
func (n *AVLNode) remove(score int) *AVLNode {
	if n == nil {
		return nil
	}
	if score < n.Score {
		n.left = n.left.remove(score)
	} else if score > n.Score {
		n.right = n.right.remove(score)
	} else {
		if n.left != nil && n.right != nil {
			// node to delete found with both children;
			// replace values with smallest node of the right sub-tree
			rightMinNode := n.right.findSmallest()
			n.Score = rightMinNode.Score
			n.PlayerIDsMap = rightMinNode.PlayerIDsMap
			n.NumPlayers = rightMinNode.NumPlayers
			// delete smallest node that we replaced
			n.right = n.right.remove(rightMinNode.Score)
		} else if n.left != nil {
			// node only has left child
			n = n.left
		} else if n.right != nil {
			// node only has right child
			n = n.right
		} else {
			// node has no children
			n = nil
			return n
		}

	}
	return n.rebalanceTree()
}

// Remove player from score
func (n *AVLNode) remove_player_from_score(score int, playerId string) {
	if n == nil {
		return
	}
	if score < n.Score {
		n.left.remove_player_from_score(score, playerId)
	} else if score > n.Score {
		n.right.remove_player_from_score(score, playerId)
	} else {
		n.NumPlayers = n.NumPlayers - 1
		delete(n.PlayerIDsMap, playerId)
	}
	return
}

// Searches for a node
func (n *AVLNode) search(score int) *AVLNode {
	if n == nil {
		return nil
	}
	if score < n.Score {
		return n.left.search(score)
	} else if score > n.Score {
		return n.right.search(score)
	} else {
		return n
	}
}

func (n *AVLNode) getHeight() int {
	if n == nil {
		return 0
	}
	return n.height
}

func (n *AVLNode) recalculateHeight() {
	n.height = 1 + max(n.left.getHeight(), n.right.getHeight())
}

// Checks if node is balanced and rebalance
func (n *AVLNode) rebalanceTree() *AVLNode {
	if n == nil {
		return n
	}
	n.recalculateHeight()

	// check balance factor and rotateLeft if right-heavy and rotateRight if left-heavy
	balanceFactor := n.left.getHeight() - n.right.getHeight()
	if balanceFactor == -2 {
		// check if child is left-heavy and rotateRight first
		if n.right.left.getHeight() > n.right.right.getHeight() {
			n.right = n.right.rotateRight()
		}
		return n.rotateLeft()
	} else if balanceFactor == 2 {
		// check if child is right-heavy and rotateLeft first
		if n.left.right.getHeight() > n.left.left.getHeight() {
			n.left = n.left.rotateLeft()
		}
		return n.rotateRight()
	}
	return n
}

// Rotate nodes left to balance node
func (n *AVLNode) rotateLeft() *AVLNode {
	newRoot := n.right
	n.right = newRoot.left
	newRoot.left = n

	n.recalculateHeight()
	newRoot.recalculateHeight()
	return newRoot
}

// Rotate nodes right to balance node
func (n *AVLNode) rotateRight() *AVLNode {
	newRoot := n.left
	n.left = newRoot.right
	newRoot.right = n

	n.recalculateHeight()
	newRoot.recalculateHeight()
	return newRoot
}

// Finds the smallest child (based on the key) for the current node
func (n *AVLNode) findSmallest() *AVLNode {
	if n.left != nil {
		return n.left.findSmallest()
	} else {
		return n
	}
}

// Returns max number - TODO: std lib seemed to only have a method for floats!
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

main.go

package main

import "fmt"

func main() {
	leaderboard := initLeaderboard()

	leaderboard.AddScore("a", 1)
	leaderboard.AddScore("b", 2)
	leaderboard.AddScore("c", 3)
	leaderboard.AddScore("d", 4)
	leaderboard.AddScore("e", 4)

	leaderboard.AddScore("f", 10)

	k := 4
	output := leaderboard.TopPlayers(k)
	for i := 0; i < len(output); i++ {
		fmt.Printf("PlayerIDs: %v, Score: %d\n", output[i].PlayerIDs, output[i].Score)
	}
	topSum := leaderboard.TopSum(k)
	fmt.Printf("Sum: %d", topSum)

	leaderboard.AddScore("f", 15)

	fmt.Println("\n")
	k = 7
	output = leaderboard.TopPlayers(k)
	for i := 0; i < len(output); i++ {
		fmt.Printf("PlayerIDs: %v, Score: %d\n", output[i].PlayerIDs, output[i].Score)
	}
	topSum = leaderboard.TopSum(k)
	fmt.Printf("Sum: %d", topSum)

}

Output

PlayerIDs: [f], Score: 10
PlayerIDs: [d e], Score: 4
PlayerIDs: [c], Score: 3
Sum: 21

PlayerIDs: [f], Score: 25
PlayerIDs: [e d], Score: 4
PlayerIDs: [c], Score: 3
PlayerIDs: [b], Score: 2
PlayerIDs: [a], Score: 1
Sum: 39

Conclusion

This is all about designing and implementing a leaderboard. Hope you have liked this article. Please share feedback in the comments

Note: Check out our system design tutorial series System Design Questions

©2024 Welcome to Tech by Example | Design: Newspaperly WordPress Theme