Step 1 of 6

Review: pagination

Reading other people's code critically is half of a professional developer's job. Before code is merged, a teammate reviews it: they read the change line by line, looking for bugs the author missed. The tests in these steps are the reviewer's edge cases. Your job is to find what breaks and fix it.

How to review

For every line, ask: what inputs break this? Try the edge cases in your head:

• empty input, one element, exactly full
• the first and the last item
• zero, negative numbers, huge numbers
• values right at a boundary (the spec's "1-based", "inclusive", "at most")

Then compare the code with the spec, word by word. Many bugs are code that works, but does something slightly different from what was asked.

A worked review

This function should return the last n messages of a chat (fewer if there aren't that many). Here's the fixed version, with comments on what the review caught:

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> last_n(const std::vector<std::string>& msgs, int n) {
    std::vector<std::string> out;
    if (n <= 0) return out;                          // caught: negative n
    // caught: msgs.size() - n underflowed (size_t is unsigned) when n > size
    std::size_t start = msgs.size() > (std::size_t)n ? msgs.size() - n : 0;
    for (std::size_t i = start; i < msgs.size(); i++) out.push_back(msgs[i]);
    return out;
}

int main() {
    std::vector<std::string> chat = {"hi", "gg", "wp", "rematch?"};
    for (int n : {2, 10, 0, -1}) {
        std::cout << n << ":";
        for (const auto& m : last_n(chat, n)) std::cout << " " << m;
        std::cout << "\n";
    }
    std::cout << "empty: " << last_n({}, 3).size() << "\n";
}

2: wp rematch?
10: hi gg wp rematch?
0:
-1:
empty: 0

The original version passed the author's one test (n = 2) and crashed on the other four.

For this pull request

Check the arithmetic for "page 1 is the first page" with a concrete example: with 10 items, 3 per page, page 1 is items 0 to 2 and page 4 holds just item 9. Then ask what happens for page 5, and for page 0.

A teammate opened this pull request for the leaderboard API. The spec says:

• page is 1-based (page 1 is the first page)
• pages past the end return an empty list, never crash
• page < 1 or per_page < 1 returns an empty list

The tests here are the reviewer's edge cases.

Your task

Find and fix the bugs. There are three.

Challenge 2

This pull request adds a hand-written binary search. It hangs on some inputs, misses the last element and can overflow on huge arrays. Fix the three bugs so find(v, x) returns the index of x in the sorted vector, or -1.

Challenge 3

This pull request adds truncate(s, max) for showing long player names. The specification: strings of at most max characters are returned unchanged; longer ones are cut so that, with ... added, the result is exactly max characters; when max is less than 3 there's no room for dots, so just cut to max. Fix the two bugs.

Next: Review: dangling references