Problem: Build a Leaderboard

Suppose a game keeps track of the top 3 scores anyone has ever gotten. Every time someone finishes a game, their score is checked against the 3 scores already on the board. If the new score is higher than the lowest of the 3, it takes that spot and the old lowest score is dropped. If the new score is not high enough, the board does not change. The board is always displayed from highest score to lowest.

That is the structure we will build: a Leaderboard that remembers only the k largest elements it has ever seen, kept in order. It is a SortedArray with one extra promise.

The invariant

SortedArray makes a single promise: it is always sorted. A Leaderboard makes two promises:

• its elements are in sorted order, and
• there are never more than k of them.

The second promise is the capacity bound. Once the board is full, adding a value means you also have to remove a value. Every operation you write has to keep both invariants in place.

The interface

class Leaderboard<T extends Comparable<T>> {
  Leaderboard(int k);   // keep at most the k largest
  void add(T value);    // offer a value to the board
  T get(int index);     // returns the value ranked `index`; rank 0 is the highest score
  int size();           // how many are currently on the board (<= k)
}

Notice that add returns nothing and never throws. Offering a value that does not belong on the board is fine; the board just stays as it was.

Leaderboard keeps its elements sorted descending: index 0 holds the highest score, and scores get lower as the index grows. That is the opposite of SortedArray, which stores ascending. The reason is get. A Leaderboard is read by rank: “give me the highest,” “give me the second-highest.” So storing the highest score at index 0 means get(index) can just return the element at that index, with no translation. It also means the lowest score, the one that falls off when a bigger value shows up, sits at the last used index, which is cheaper to remove than the first.

How it should behave

Here is a board with k = 3, fed one value at a time. Index 0 is always the highest value on the board:

Leaderboard<Integer> board = new Leaderboard<>(3);
add 50  ->  [50]
add 70  ->  [70, 50]
add 30  ->  [70, 50, 30]      // full now (k = 3)
add 90  ->  [90, 70, 50]      // 90 gets in; 30 falls off
add 10  ->  [90, 70, 50]      // 10 can't beat 50; nothing changes
add 80  ->  [90, 80, 70]      // 80 gets in; 50 falls off

get(0) is 90, get(1) is 80, get(2) is 70. All three are read straight off the array, in order.

The accompanying code for this practice problem has a worked solution in practice.Leaderboard, and a runnable demo in practice.PracticeMain that feeds the board the scores above and prints it after each add.