7.9 million ranks after every ball, without sorting

transcript

One contest. 7 point 9 million entries. A new ball every 45 seconds or so. Every rank exact, within a minute of each ball. No sorting.

The textbook answer is a sorted set. Update a score, it re-sorts. But one ball can change most scores in a contest. Millions of updates. All on one hot key. Sorted sets are built for scores that change one at a time. Not this.

Here's the trick. Fantasy points are discrete. The captain scores double. The vice-captain scores one and a half times. That makes halves. So every score is a multiple of half a point. Nothing in between.

So a whole contest's scores fit in about 3,000 buckets. Each ball, count how many entries sit in each bucket. Karthik has 412 and a half points. How many entries scored more? His rank is one plus that. One lookup. And it's exact.

But here's the catch. What about ties? Twelve entries tie for ranks 1,000 to 1,011. All twelve are rank 1,000. And they split those prizes equally. Counting gets that right for free.

When scores are discrete, you don't need to sort millions. Count them. Rank by counting.

Full breakdown in the lecture.