JS-201 · Lesson 12 of 12 · 30 min

Capstone: solving and analysing algorithm problems

▶ Video coming soon A video version of this lesson is on the way.

The last session of the block is planned for Thursday, October 14, 2027, and it is a working session rather than a lesson. Gareth has collected four real problems from the Food Hub's autumn: one from Lucy, one from Rosa, one from Paul and one from Dev's hamper drive page. Mira's job is to solve each one, explain how fast her solution is and why, and show that it is correct. On Friday, October 15, she will walk Gareth and Theo through her solutions, and the code will go into riverside-data before the hamper drive in December.

"Interviewers and code reviewers ask the same thing," Gareth says. "Not whether you remember an algorithm, but whether you can take a problem you have not seen, find a correct answer, and say how it will behave when the data grows." This lesson follows Mira through the four problems using one method.

A method for algorithm problems

Gareth's method has six steps. They are not a ritual; each one prevents a specific, common failure. Skipping the first step solves the wrong problem. Skipping the second misses the awkward cases. Skipping the third leaves nothing to check the clever version against. And skipping the last three ships code that is slow, wrong or impossible for the next person to understand.

Six boxes in a row joined by arrows: 1 Understand, restate the problem and its inputs, outputs and limits; 2 Examples, work small cases by hand including edge cases; 3 Brute force, write the simplest correct solution; 4 Analyse, find its Big-O and the bottleneck; 5 Improve, choose a better data structure or technique; 6 Test and explain, compare with the brute force and state the trade-offs. A dashed arrow returns from step 6 to step 4.
A six-step method for solving and analysing algorithm problems. Testing often sends you back to analyse again.
The method, step by step.
StepWhat to doFailure it prevents
1. UnderstandRestate the problem; list the inputs, outputs, sizes and limits; ask what happens in odd casesSolving the wrong problem
2. ExamplesWork two or three small cases by hand, including empty, single and tied inputsMissing edge cases
3. Brute forceWrite the simplest correct solution, however slowHaving nothing to check a fast version against
4. AnalyseFind the Big-O of time and space and the line that dominatesOptimizing the wrong part
5. ImproveRemove the bottleneck with a better structure or techniqueCode that fails when the data grows
6. Test and explainCompare the fast version with the brute force on many inputs; state the costs and trade-offsFast code that is wrong, or that nobody can maintain

For step 5, the earlier lessons give a checklist of questions. Is there a hidden loop that a Map or Set could replace (Lessons 1, 2 and 5)? Would sorting first make the rest easy (Lessons 7 and 8)? Is this really a tree or graph problem (Lessons 9 and 10)? Is the same subproblem being solved repeatedly (Lessons 6 and 11)? Is only the top few of something needed, which suggests a heap (Lesson 4)?

Problem 1: merging busy times

Lucy's problem: each volunteer's calendar on the dashboard lists their shifts, training sessions and meetings for a day as start and end times, and the lists overlap. She wants each volunteer's busy times merged into the fewest separate blocks, so that she can see at a glance when someone is free. Step 1 raises a question: do two blocks that touch, one ending at 10:00 and the next starting at 10:00, count as one block? Lucy says yes. Step 2 gives examples: 9:00 to 10:00 and 9:30 to 11:00 become 9:00 to 11:00; an empty list stays empty; a block inside another disappears into it.

The brute force repeatedly looks for any two blocks that overlap and merges them, until no pair overlaps. Each pass compares all pairs, O(n²), and there can be up to n passes, so it is O(n³) in the worst case. The improvement comes from sorting: once the blocks are sorted by start time, any block that overlaps the current merged block must come straight after it. A single sweep through the sorted list finishes the job, so the whole algorithm is O(n log n) for the sort plus O(n) for the sweep.

JavaScript Example · Merging overlapping busy times
// Intervals are [start, end] in minutes after midnight, with start < end.
function mergeIntervals(list) {
  const sorted = list.toSorted((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of sorted) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);   // overlaps or touches: extend
    else out.push([s, e]);
  }
  return out;
}

const hhmm = (m) => String(Math.floor(m / 60)).padStart(2, '0') + ':' + String(m % 60).padStart(2, '0');
const show = (list) => list.map(([s, e]) => hhmm(s) + '-' + hhmm(e)).join(', ') || '(free all day)';

const ana = [[600, 660], [540, 600], [690, 750], [570, 615], [720, 735], [900, 960]];
console.log('Ana busy:', show(mergeIntervals(ana)));
console.log('Empty:   ', show(mergeIntervals([])));
console.log('Inside:  ', show(mergeIntervals([[540, 720], [600, 630]])));
Output
Ana busy: 09:00-11:00, 11:30-12:30, 15:00-16:00
Empty:    (free all day)
Inside:   09:00-12:00

What this code does

mergeIntervals sorts copies of the blocks by start time and then sweeps through them, extending the last merged block whenever the next one starts before or exactly when it ends. Ana's six entries collapse into three blocks because the morning ones chain together through overlaps and a touching boundary at 10:00. The edge cases from step 2 behave as Lucy expects.

Step 6 tests the fast version against the brute force. Hand-picked examples catch some bugs, but randomized testing catches more: generate hundreds of random inputs, run both versions on each, and stop at the first disagreement. The random numbers come from a seeded generator so that any failure can be reproduced exactly.

JavaScript Example · Checking the fast version against the brute force
// Intervals are [start, end] in minutes after midnight, with start < end.
function mergeIntervals(list) {
  const sorted = list.toSorted((a, b) => a[0] - b[0]);
  const out = [];
  for (const [s, e] of sorted) {
    const last = out[out.length - 1];
    if (last && s <= last[1]) last[1] = Math.max(last[1], e);   // overlaps or touches: extend
    else out.push([s, e]);
  }
  return out;
}

function lcg(seed) { return () => (seed = (seed * 48271) % 2147483647) / 2147483647; }

function mergeBrute(list) {
  let blocks = list.map(([s, e]) => [s, e]);
  let changed = true;
  while (changed) {
    changed = false;
    outer: for (let i = 0; i < blocks.length; i++) {
      for (let j = i + 1; j < blocks.length; j++) {
        const [a, b] = [blocks[i], blocks[j]];
        if (a[0] <= b[1] && b[0] <= a[1]) {
          blocks[i] = [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
          blocks.splice(j, 1);
          changed = true;
          break outer;
        }
      }
    }
  }
  return blocks.sort((x, y) => x[0] - y[0]);
}

const rand = lcg(2027);
let tests = 0, failures = 0;
for (let t = 0; t < 500; t++) {
  const n = Math.floor(rand() * 8);
  const list = Array.from({ length: n }, () => {
    const s = 480 + Math.floor(rand() * 40) * 15, len = 15 + Math.floor(rand() * 8) * 15;
    return [s, s + len];
  });
  tests++;
  if (JSON.stringify(mergeIntervals(list)) !== JSON.stringify(mergeBrute(list))) failures++;
}
console.log(tests, 'random tests,', failures, 'disagreements');
Output
500 random tests, 0 disagreements

What this code does

mergeBrute is the slow, obviously correct version: it merges any overlapping or touching pair and starts again until nothing changes. The test loop builds 500 random calendars of up to seven blocks from a seeded generator and checks that both versions give identical results. No disagreements means the fast version matches the definition on every one of those cases, including the empty and single-block calendars that turn up by chance.

Problem 2: the busiest shifts

Paul wants the five busiest shifts of the season, by number of sign-ups, for his report to the board. The season has about 4,000 shifts. The obvious solution sorts all the shifts by sign-ups and takes the first five, which is O(n log n) and perfectly fine at this size. Mira writes it first, as step 3 says.

But step 4 notices that sorting puts all 4,000 shifts in order when only five are needed. A min-heap of size k does better: walk through the shifts, keep the k busiest seen so far in the heap with the smallest of them at the top, and whenever a shift beats the top, replace it. Each heap operation is O(log k), so the whole job is O(n log k). With k = 5, log k is tiny, and the heap never holds more than five shifts, which matters when the data arrives as a stream too large to keep in memory.

JavaScript Example · Top five by sorting and by a heap
class MinHeap {
  constructor(less) { this.a = []; this.less = less; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) { const a = this.a; a.push(x); let i = a.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } }
  pop() { const a = this.a, top = a[0], last = a.pop();
    if (a.length) { a[0] = last; let i = 0;
      for (;;) { const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } }
    return top; }
}

function lcg(seed) { return () => (seed = (seed * 48271) % 2147483647) / 2147483647; }

const rand = lcg(15);
const areas = ['Kitchen', 'Garden', 'Counter', 'Grocery', 'Warehouse'];
const shifts = Array.from({ length: 4000 }, (_, i) => ({
  id: 'S' + (i + 1), area: areas[i % 5], signups: Math.floor(rand() * 12) + Math.floor(rand() * 12),
}));

function topBySort(list, k) {
  return list.toSorted((a, b) => b.signups - a.signups || a.id.localeCompare(b.id)).slice(0, k);
}
function topByHeap(list, k) {
  // "smaller" = fewer sign-ups, or the later id on a tie, so the top of the heap is the weakest kept shift
  const weaker = (a, b) => a.signups < b.signups || (a.signups === b.signups && a.id.localeCompare(b.id) > 0);
  const heap = new MinHeap(weaker);
  for (const s of list) {
    if (heap.size < k) heap.push(s);
    else if (weaker(heap.peek(), s)) { heap.pop(); heap.push(s); }
  }
  const out = [];
  while (heap.size) out.push(heap.pop());
  return out.reverse();
}

const fmt = (list) => list.map((s) => s.id + ' ' + s.area + ' ' + s.signups).join(' | ');
console.log('sort:', fmt(topBySort(shifts, 5)));
console.log('heap:', fmt(topByHeap(shifts, 5)));
Output
sort: S1009 Grocery 22 | S110 Warehouse 22 | S1215 Warehouse 22 | S1486 Kitchen 22 | S1783 Counter 22
heap: S1009 Grocery 22 | S110 Warehouse 22 | S1215 Warehouse 22 | S1486 Kitchen 22 | S1783 Counter 22

What this code does

The 4,000 shifts are generated with a seeded random generator, so the report is the same on every run. topBySort sorts every shift and keeps the first five, while topByHeap keeps only five shifts in a min-heap and replaces the weakest whenever a busier shift comes along. Ties are broken by shift id in both versions, which is why they agree exactly.

The tie-breaking rule is the detail that makes the two versions agree. Without it, several shifts with the same number of sign-ups could be chosen in different orders, both answers would be reasonable, and the comparison test would report false failures. Deciding what should happen on a tie is part of step 1, and it is a question for Paul, not a choice for the code.

Problem 3: the longest run of days

Rosa wants to thank the lunch counter volunteers who came in on the most consecutive days. For each volunteer she has the list of dates they worked, as day numbers counted from January 1, unsorted and with repeats when someone worked two shifts in a day. The brute force checks, for every day, how long a run starts there by looking up the following days one by one in the list, which is O(n²) because each lookup is a linear search.

Two improvements are possible. Sorting the unique days and scanning for runs is O(n log n). A Set does better: put every day in a Set, and start counting only from days whose previous day is not in the Set, since only those can begin a run. Each day is then looked at a bounded number of times, so the whole check is O(n) on average.

JavaScript Example · The longest run of consecutive days in O(n)
function longestRun(days) {
  const set = new Set(days);
  let best = 0, bestStart = null;
  for (const d of set) {
    if (set.has(d - 1)) continue;          // not the start of a run
    let len = 1;
    while (set.has(d + len)) len++;
    if (len > best) { best = len; bestStart = d; }
  }
  return { best, bestStart };
}

const volunteers = {
  Ana: [250, 251, 252, 260, 253, 251, 270, 271],
  Ben: [255, 257, 259, 261],
  Chi: [240, 241, 242, 243, 244, 300, 301],
};
for (const [name, days] of Object.entries(volunteers)) console.log(name, longestRun(days));
Output
Ana { best: 4, bestStart: 250 }
Ben { best: 1, bestStart: 255 }
Chi { best: 5, bestStart: 240 }

What this code does

longestRun puts the days in a Set, which also removes repeated days, and skips any day whose previous day is present because it cannot start a run. From each starting day it counts forward while the next day is in the Set. Every day is counted in at most one run, so the work is proportional to the number of days, and Chi's five days in a row win.

Problem 4: the drivers' rounds

Dev's hamper drive page already gives the quickest route between any two pick-up points, using Dijkstra's algorithm from Lesson 10. The new request is harder: one van leaves the Hub, visits all six pick-up points and returns, and the round should take as little time as possible. This is the travelling salesman problem, and Lesson 10 warned that no fast exact algorithm is known.

Step 1 checks the size: six points. Step 3's brute force tries every order of visiting them, 6! = 720 orders, which a computer checks in a moment. It needs the quickest time between every pair of points first, which is a job for the Floyd-Warshall algorithm, a dynamic programming method that improves every pair's time by allowing each point in turn as a stop on the way. It is O(V³), which for seven places is 343 steps.

JavaScript Example · All-pairs times and the best round by brute force
const places = ['Hub', 'Library', 'School', 'Church', 'Clinic', 'Rink', 'Market'];
const roads = [['Hub', 'Library', 6], ['Hub', 'School', 9], ['Library', 'School', 4], ['Library', 'Church', 8],
  ['School', 'Clinic', 5], ['Church', 'Clinic', 3], ['Church', 'Rink', 7], ['Clinic', 'Market', 10],
  ['Rink', 'Market', 4], ['School', 'Market', 16]];

// Floyd-Warshall: quickest time between every pair of places.
const idx = new Map(places.map((p, i) => [p, i]));
const n = places.length;
const t = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
for (const [a, b, w] of roads) { t[idx.get(a)][idx.get(b)] = w; t[idx.get(b)][idx.get(a)] = w; }
for (let k = 0; k < n; k++) for (let i = 0; i < n; i++) for (let j = 0; j < n; j++)
  if (t[i][k] + t[k][j] < t[i][j]) t[i][j] = t[i][k] + t[k][j];

function roundTime(order) {                      // order of stops, starting and ending at the Hub (index 0)
  let total = 0, at = 0;
  for (const p of order) { total += t[at][p]; at = p; }
  return total + t[at][0];
}
function* permutations(a) {
  if (a.length <= 1) { yield a; return; }
  for (let i = 0; i < a.length; i++) for (const rest of permutations([...a.slice(0, i), ...a.slice(i + 1)])) yield [a[i], ...rest];
}

let best = null, tried = 0;
for (const order of permutations([1, 2, 3, 4, 5, 6])) {
  tried++;
  const time = roundTime(order);
  if (best === null || time < best.time) best = { time, order };
}
console.log('orders tried:', tried);
console.log('best round:', best.time, 'min: Hub ->', best.order.map((i) => places[i]).join(' -> '), '-> Hub');
Output
orders tried: 720
best round: 49 min: Hub -> Library -> Church -> Rink -> Market -> Clinic -> School -> Hub

What this code does

The triple loop is Floyd-Warshall: for each place k, it checks whether going through k gives any pair of places a quicker time, so at the end t holds the quickest time between every pair. The brute force then tries all 720 orders of the six pick-up points and keeps the quickest round. With six stops this is instant, but each extra stop multiplies the number of orders.

For six points, brute force is the right answer: it is exact, simple and fast enough. But the hamper drive might grow to ten or more stops, and 10! is 3,628,800 orders, 15! is over a trillion. Step 5 looks for a heuristic, a fast method that usually gives a good answer without promising the best one. The simplest is nearest neighbour: from wherever the van is, drive to the closest unvisited point. It takes O(V²) time, and its answer can be compared with the brute force while the problem is still small enough to check.

JavaScript Example · The nearest-neighbour heuristic
const places = ['Hub', 'Library', 'School', 'Church', 'Clinic', 'Rink', 'Market'];
// Quickest times between every pair, as computed by Floyd-Warshall in the previous example.
const t = [
  [0, 6, 9, 14, 14, 21, 24], [6, 0, 4, 8, 9, 15, 19], [9, 4, 0, 8, 5, 15, 15], [14, 8, 8, 0, 3, 7, 11],
  [14, 9, 5, 3, 0, 10, 10], [21, 15, 15, 7, 10, 0, 4], [24, 19, 15, 11, 10, 4, 0],
];
function nearestFirst() {
  const left = new Set([1, 2, 3, 4, 5, 6]);
  const order = [];
  let at = 0, total = 0;
  while (left.size > 0) {
    let next = null;
    for (const p of left) if (next === null || t[at][p] < t[at][next]) next = p;
    total += t[at][next]; order.push(next); left.delete(next); at = next;
  }
  return { time: total + t[at][0], order: order.map((i) => places[i]) };
}
const r = nearestFirst();
console.log('closest stop first:', r.time, 'min:', ['Hub', ...r.order, 'Hub'].join(' -> '));
Output
closest stop first: 53 min: Hub -> Library -> School -> Clinic -> Church -> Rink -> Market -> Hub

What this code does

nearestFirst starts at the Hub and always drives to the closest pick-up point not yet visited, then returns to the Hub at the end. The table of times is the one the Floyd-Warshall example computed, written out so the example can stand on its own. Its round takes 53 minutes, four more than the best round of 49 that the brute force found, because grabbing the closest stop early leaves a long drive back from the Market at the end. Checking it against the exact answer is how Mira knows how far off it is.

Mira's plan for the December drive is therefore two-sided. For up to eight stops, the page uses brute force and shows the best round. For more stops, it uses nearest neighbour followed by a simple improvement step that tries reversing parts of the route, and labels the result as a suggested round, not a guaranteed best one. Being honest about what an algorithm promises is part of step 6.

Measuring as well as analysing

Big-O predicts how the work grows; measurement confirms it on real devices. Gareth asks Mira to time the busiest-shifts report on the counter tablet, the slowest device the Food Hub uses, with realistic data. The browser's performance.now() gives times in milliseconds with fractions, and repeating the work many times smooths out noise. Timings differ on every run and every device, which is why they appear here as a listing to try in the browser's console rather than as a runnable example with fixed output.

JavaScript Example
function timeIt(label, fn, repeats = 50) {
  fn();                                         // warm up: let the engine optimize first
  const start = performance.now();
  for (let i = 0; i < repeats; i++) fn();
  const ms = (performance.now() - start) / repeats;
  console.log(label, ms.toFixed(3), 'ms per run');
}

timeIt('top 5 by sort', () => topBySort(shifts, 5));
timeIt('top 5 by heap', () => topByHeap(shifts, 5));

What this code does

timeIt runs the function once to warm up, because engines optimize code that runs often, and then times many runs and reports the average. The numbers depend on the device, the browser and what else is running, so only large differences are meaningful. Comparing the same functions on the slowest device the Food Hub uses tells Mira whether the faster algorithm matters in practice.

On Gareth's laptop both versions take a fraction of a millisecond for 4,000 shifts, so the sort version stays in riverside-data for its clarity, and the heap version goes in alongside it for the stream of sign-up events that Theo is planning for 2028. That is a typical conclusion: the better algorithm matters when the data is large or the operation runs often, and the clearer code wins otherwise.

Explaining a solution

On Friday, October 15, Mira presents each solution in the same short form, which Gareth recommends for code reviews and interviews alike. Say what the problem is and the assumptions made, such as touching blocks counting as one. Describe the brute force and its cost in one sentence. Describe the improved solution, its time and space in Big-O, and the reason it is faster, such as "sorting puts every overlap next to the block it overlaps". Say how it was tested. And name the trade-off, such as the heuristic not being guaranteed best.

Mira's summary for the review.
ProblemBrute forceImprovedKey ideaTested by
Merge busy timesO(n³)O(n log n)Sort by start, then one sweep500 seeded random calendars
Five busiest shiftsO(n log n) sortO(n log k) heapKeep only the k best so farSame answer as the sort, with ties broken by id
Longest run of daysO(n²)O(n) averageSet lookups; count only from run startsHand examples with repeats and gaps
Drivers' roundO(V!) ordersO(V²) heuristicFloyd-Warshall times, nearest neighbourCompared with brute force for six stops

"A year ago you were running the volunteer schedule in a spreadsheet," Gareth says when the table is finished. "Now you can tell me how the schedule code will behave with ten times the data, and prove it." The block ends, if the plan holds, with the hamper drive routes ready for December and Mira's next block, on Node.js and the server, planned for the new year.

Try it yourself

Merge the bookings

Complete merge(list) so that it returns the busy blocks merged into the fewest separate blocks, sorted by start time. Blocks are [start, end] in minutes; blocks that overlap or touch become one.

Sort a copy by start time, then sweep once.

function merge(list) {
  return list;
}

console.log(JSON.stringify(merge([[600, 660], [540, 600], [700, 720], [570, 615]])));
console.log(JSON.stringify(merge([])), JSON.stringify(merge([[480, 540]])));
console.log(JSON.stringify(merge([[540, 720], [600, 630], [720, 750]])));

Try it yourself

Longest streak

Complete longestStreak(days) so that it returns the length of the longest run of consecutive day numbers in the unsorted array days, which may contain repeats. Return 0 for an empty array.

Make it O(n) on average with a Set, counting only from days that start a run.

function longestStreak(days) {
  return days.length;
}

console.log(longestStreak([10, 4, 11, 5, 12, 6, 13, 20]));
console.log(longestStreak([3, 3, 3]), longestStreak([]), longestStreak([7, 9, 11]));

Try it yourself

The three busiest areas

Complete topAreas(signups, k) so that it returns the names of the k areas with the most sign-ups, busiest first. Break ties by area name in alphabetical order.

Count with a Map in one pass, then sort the much shorter list of areas.

function topAreas(signups, k) {
  return signups.slice(0, k).map((s) => s.area);
}

const signups = ['Kitchen', 'Garden', 'Counter', 'Kitchen', 'Grocery', 'Garden', 'Kitchen', 'Counter', 'Grocery', 'Warehouse']
  .map((area) => ({ area }));
console.log(topAreas(signups, 3).join(', '));
console.log(topAreas(signups, 1).join(', '));

Common mistakes

  • MistakeStarting with the clever solution.

    InsteadWrite the brute force first; it is the reference that proves the fast version correct.

  • MistakeTesting only with the examples from the problem statement.

    InsteadAdd edge cases and seeded random tests compared against the brute force.

  • MistakeLeaving ties to chance.

    InsteadDecide the tie rule as part of understanding the problem, or two correct versions will disagree.

  • MistakeClaiming a heuristic gives the best answer.

    InsteadSay what it promises: usually good, not guaranteed best, and check it where the exact answer is known.

  • MistakeJudging speed by one timing.

    InsteadWarm up, repeat, measure on the slowest real device, and trust large differences only.

Summary and key terms

  • A six-step method guides algorithm problems: understand the problem and its limits, work examples by hand, write a brute force, analyse its cost and bottleneck, improve it with a better structure or technique, then test and explain.
  • Merging busy times becomes O(n log n) by sorting by start time and sweeping once.
  • Seeded randomized tests that compare a fast version with a brute force catch bugs that hand examples miss.
  • The top k of n items can be kept in a min-heap of size k in O(n log k), and tie rules must be decided so that versions agree.
  • A Set finds the longest run of consecutive days in O(n) on average by counting only from run starts.
  • The best round visiting every pick-up point needs all-pairs times, from Floyd-Warshall in O(V³), and a brute force over V! orders, which is fine for six stops but not for many; a nearest-neighbour heuristic is fast but not guaranteed best.
  • Timings confirm analysis but vary, so warm up, repeat and test on real devices.
  • A good explanation states assumptions, both solutions with their costs, the key idea, the tests and the trade-offs.
brute force
The simplest correct solution, which tries every possibility or does the obvious work without optimizing.
bottleneck
The part of an algorithm that dominates its running time.
randomized testing
Checking code on many generated inputs, often by comparing it with a simpler trusted version.
seeded random generator
A generator of pseudo-random numbers that produces the same sequence from the same starting seed.
sweep
A single pass over sorted data that processes items in order, such as merging intervals.
top-k problem
Finding the k largest or smallest items, which a heap of size k solves in O(n log k).
travelling salesman problem
Finding the shortest round that visits every location once and returns to the start.
Floyd-Warshall algorithm
A dynamic programming algorithm that finds the shortest paths between all pairs of vertices in O(V³).
heuristic
A fast method that usually gives a good answer without guaranteeing the best one.
nearest-neighbour heuristic
Building a route by always moving to the closest unvisited location.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. Why write a brute force before an improved solution?

    Show answer

    It is simple enough to trust, so it can check the improved version on many inputs.

  2. What is the cost of finding the 10 busiest of 50,000 shifts with a heap of size 10?

    Show answer

    O(n log k), about 50,000 × log₂ 10 heap steps, with only 10 shifts kept.

  3. Why does the longest-run check skip days whose previous day is in the Set?

    Show answer

    Those days are in the middle of a run, so counting from them would repeat work.

  4. How many orders does a brute-force round of 8 stops try?

    Show answer

    8! = 40,320.

  5. Why are timings shown as a listing rather than a runnable example with fixed output?

    Show answer

    Timings vary with the device, the browser and the moment, so no single output is correct.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz