Skip to content

Module 14 — Challenge Problems

Open problems. More than one defensible answer exists, and the reasoning is assessed as much as the code.

All three are about choosing under a workload, which is the judgement this module teaches. The techniques are not in question — you can write the algorithms and the containers. What is being tested is whether you can say which, why, and what it costs.

Challenge 1 — Build an index that answers a question nothing else can [L6 Build]

The problem. The library system must answer, on demand and repeatedly: "which loans are overdue today?" — and the answer must not scan every loan. The index must stay correct as loans are taken, returned, and (because the campus changes the rules) extended.

Design it, build it, and account for it.

What a good answer contains.

  • A structure chosen for the query, not for convenience. Consider at the least: a map keyed by due date, an unordered_map from day to a set of loans, and a heap ordered by due date. Name what each makes cheap and what it makes expensive.
  • The cost of every update. Taking a loan inserts; returning one removes; extending one moves an entry from one bucket to another. Give the complexity of each, in your structure.
  • A demonstration that it stays correct. A scripted sequence — add, return, extend, query — whose output is compared against the naive scan's, so that "the index agrees with the definition" is shown rather than asserted.
  • One sentence on what the design assumed. For example: "this assumes a loan's due date is not changed after it is recorded; if that changes, the index needs a remove-then-reinsert."
  • A note on what would break it: back-dated loans, two loans on the same day, a due date edited while the report is being produced.

What would make it weak. Keeping a sorted vector of loans and re-sorting it on every query. It is correct, and it turns a query that should be logarithmic into a linear scan — which is precisely the problem the challenge names. A weaker answer still: an index that is correct but never updated, so the report is right the first time it runs.

Deciding it for yourself. Ask what the repeated operation is. If the query runs once per user action and updates are rare, a structure that is expensive to update and cheap to query wins; if updates are constant, it does not. That is the whole decision, and it needs the workload, not a preference.

Challenge 2 — Refactor for readability and complexity at once [L7 Refactor]

The problem. This query is correct, fifteen lines long, and quadratic. Rewrite it so that it is shorter, linear, and measurably the same in behaviour.

std::vector<std::string> report(const std::vector<Loan>& loans,
                               const std::vector<Member>& members,
                               const std::vector<Item>& items,
                               int overdueLimit) {
    std::vector<std::string> lines;
    for (std::size_t i = 0; i < loans.size(); ++i) {
        if (loans[i].returned) { continue; }
        std::string name;
        for (std::size_t j = 0; j < members.size(); ++j) {
            if (members[j].id == loans[i].memberId) { name = members[j].name; break; }
        }
        std::string title;
        for (std::size_t k = 0; k < items.size(); ++k) {
            if (items[k].id == loans[i].itemId) { title = items[k].title; break; }
        }
        if (loans[i].overdueDays() > overdueLimit) {
            lines.push_back(name + " owes " + title + " (" +
                            std::to_string(loans[i].overdueDays()) + " days)");
        }
    }
    return lines;
}

What a good answer contains.

  • The same output, verified by comparison rather than by inspection — run both versions on the same data and diff them, including the order of the lines.
  • Complexity stated before and after, with numbers. Three nested scans is O(loans × (members + items)); two lookups built once is O(members + items + loans). The measurements at two sizes are the evidence.
  • The rewrite shorter and clearer. The standard version is roughly: build two indexes, then transform the loans into lines, filtering first with remove_if or a check. If your "cleaner" version is longer than the original, the refactor has not happened.
  • The requirements named: Loan needs equality or a projection, Member/Item need their ids, and the report needs stable ordering — say which of those the algorithms demanded.

What would make it weak. A rewrite that is linear but unreadable — three std::function variables and a lambda inside a lambda — or one that changes behaviour subtly: reordering the lines, dropping loans with a missing member, or losing the returned filter. "It is faster" is not the whole requirement; this challenge is about doing both at once.

Deciding it for yourself. Write the output of both versions into files and compare them. If you cannot demonstrate that the output is unchanged, the refactor has not been verified, and behaviour changes hidden inside optimisations are the most expensive kind of bug this course has taught.

Challenge 3 — Judge three designs for the same lookup [L8 Evaluate]

The problem. Three implementations of the same catalogue lookup are in front of you:

A: sorted vector + lower_bound B: std::map C: std::unordered_map
Lookup O(log n), compact, cache-friendly O(log n), node per element average O(1), worst O(n)
Insert O(n) (shift) O(log n) average O(1)
Ordered iteration free — the data is sorted free impossible
Worst case guaranteed guaranteed depends on the hash

Choose one for a stated workload, and defend it.

The workload is yours to state, and stating it is half the answer. Two examples: "the catalogue is loaded once at startup, then queried thousands of times per session, and a report iterates it in title order" and "items are added and removed continuously while the system runs, and lookups are one per user action". The same three designs do not rank the same way for both.

What a good answer contains.

  • A decision, not a table. The table is the work; the answer is a choice, with the workload it was made for written down first.
  • A real cost named for each option you rejected, not a vague one: A needs a re-sort after every insertion; B allocates a node per item and loses locality; C can be linear in the worst case and cannot answer an ordered query at all.
  • The cost of the option you chose, named too. A single perfect choice does not exist here, and an answer that presents one as free has not understood the table.
  • A measurement from the lab's own numbers — at least one comparison count or a memory statement, so the judgement rests on something you produced rather than on the table above.
  • A criterion that would change your mind, stated explicitly. For example: "if the report were removed from the requirements, B loses to C outright; if insertions became constant, C's worst case would need defending."

What would make it weak. "unordered_map is fastest, so C." That is a statement about one operation in one case, and it ignores three of the four rows — including the one that decides many real workloads, which is whether anything ever needs the data in order. Equally weak: choosing A because it is the fastest lookup, while the workload inserts on every user action and re-sorts the whole vector each time.

Deciding it for yourself. Write the workload as a sentence, then ask which of the four rows in the table that sentence makes dominant. The dominant row chooses the container. If two rows are equally dominant, you have not stated the workload precisely enough yet — and that imprecision is itself worth noticing, because it is exactly what makes people reach for a container out of habit.

Evaluating your own answer

Write these five lines before reading any suggested approach:

The workload, in one sentence:
The dominant operation, and why the sentence makes it dominant:
My choice:
Its cost, and the cost of the option I rejected:
What would change my mind:

Then check it against three tests:

  1. Is there a workload? Without one there is no decision to evaluate — only a preference, and preferences do not survive the first measurement.
  2. Is a cost named for the chosen option? Every one of the three designs here pays for what it buys. An answer with no cost is a slogan.
  3. Was it measured? This module's exit level is 7: refactoring with unchanged behaviour and a demonstrated improvement. Numbers turn a claim into an argument, and the numbers have to be in the answer.

Levels: [L6 Build] · [L7 Refactor] · [L8 Evaluate] — this module's exit level is 7, and Challenge 3 goes beyond it deliberately: the counterweight to a module about choosing is the admission that some choices have no winner.

Next: Self-assessment — ten questions, including a prediction about invalidation and one about a key type that lies.