The report that reordered itself

import java.util.*;
import java.util.stream.*;

/**
 * Solution: the settlement report that reordered itself.
 *
 * Four independent defects. Only the second one is the kind that ever throws,
 * and it is the one the team already knew about — the other three had been
 * producing wrong reports quietly.
 */
public class Solution {

    record Order(long id, int amountMinor, String customer) {}

    /* ── the report, fixed ──────────────────────────────────────────────── */

    static List<Order> byId(List<Order> orders, Comparator<Order> counted) {
        List<Order> copy = new ArrayList<>(orders);
        copy.sort(counted);
        return copy;
    }

    /*
     * Defect 1. The original was `(int) (a.id() - b.id())`, which is wrong
     * twice over: the subtraction of two longs can overflow, and the cast to
     * int throws away the top 32 bits of whatever survives — so ids differing
     * by exactly 2^32 compared equal. Neither failure throws.
     *
     * comparingLong never subtracts. It is also the shorter code.
     */
    static final Comparator<Order> BY_ID = Comparator.comparingLong(Order::id);

    /*
     * Defect 2. "Within one rupee counts as the same band" is not transitive:
     * 236 and 164 are within 100, 164 and 76 are within 100, and 236 and 76
     * are not. TimSort noticed and threw the general-contract exception.
     *
     * The requirement is real; expressing it as a tolerance is what breaks.
     * Assign each amount to a fixed band, compare bands, and use the amount
     * itself as a tiebreak. Banding is a function of one element, so the
     * result is transitive by construction.
     */
    static final int BAND_MINOR = 100;
    static final Comparator<Order> BY_BAND =
        Comparator.comparingInt((Order o) -> o.amountMinor() / BAND_MINOR)
                  .thenComparingInt(Order::amountMinor);

    /*
     * Defect 3. A TreeSet decides membership with its comparator, not with
     * equals. Comparing only on customer meant every order after the first for
     * a given customer was treated as a duplicate and dropped — 150 of 200
     * rows, silently, with no exception and no log line.
     *
     * De-duplication is an equals question, so use an equals-based Set.
     * LinkedHashSet also preserves encounter order, which a HashSet would not.
     */
    static List<Order> deduplicate(List<Order> orders) {
        return new ArrayList<>(new LinkedHashSet<>(orders));
    }

    /*
     * Defect 4. `stream().sorted(cmp).limit(10)` orders all 100,000 rows to
     * keep ten — sorted() is a full barrier, so limit() saves nothing.
     *
     * A bounded min-heap of size k keeps the k largest seen so far. Each new
     * element costs one comparison against the smallest of those, and only the
     * rare improvement costs a heap operation: O(n log k) time, O(k) memory.
     */
    static List<Order> topTen(List<Order> orders, Comparator<Order> counted) {
        final int k = 10;
        // Smallest-first, so peek() is the weakest member of the current top k.
        PriorityQueue<Order> best = new PriorityQueue<>(k, counted.reversed());
        for (Order o : orders) {
            if (best.size() < k) {
                best.offer(o);
            } else if (counted.compare(o, best.peek()) < 0) {   // strictly better
                best.poll();
                best.offer(o);
            }
        }
        List<Order> out = new ArrayList<>(best);
        out.sort(counted);
        return out;
    }

    /* ── checks (unchanged from the starter) ────────────────────────────── */

    static <T> Comparator<T> counting(Comparator<T> inner, long[] calls) {
        return (a, b) -> { calls[0]++; return inner.compare(a, b); };
    }

    static List<Order> sample(int n, long seed) {
        Random r = new Random(seed);
        List<Order> out = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            out.add(new Order(r.nextLong(), r.nextInt(1_000_000), "cust-" + r.nextInt(50)));
        return out;
    }

    public static void main(String[] args) {
        List<String> failures = new ArrayList<>();

        List<Order> wide = List.of(
            new Order(Long.MAX_VALUE, 10, "a"),
            new Order(-5L, 20, "b"),
            new Order(4_294_967_296L, 30, "c"),
            new Order(0L, 40, "d"));
        List<Order> sorted = byId(wide, counting(BY_ID, new long[1]));
        for (int i = 1; i < sorted.size(); i++) {
            if (sorted.get(i - 1).id() > sorted.get(i).id()) {
                failures.add("1. statement is not in id order: "
                    + sorted.stream().map(o -> String.valueOf(o.id())).collect(Collectors.joining(", ")));
                break;
            }
        }

        List<Order> triples = new ArrayList<>();
        Random rb = new Random(7);
        for (int i = 0; i < 40; i++) triples.add(new Order(i, rb.nextInt(500), "cust"));
        outer:
        for (Order a : triples) for (Order b : triples) {
            if (Integer.signum(BY_BAND.compare(a, b)) != -Integer.signum(BY_BAND.compare(b, a))) {
                failures.add("2. BY_BAND is not antisymmetric");
                break outer;
            }
            for (Order c : triples) {
                if (BY_BAND.compare(a, b) <= 0 && BY_BAND.compare(b, c) <= 0 && BY_BAND.compare(a, c) > 0) {
                    failures.add("2. BY_BAND is not transitive: it puts " + a.amountMinor()
                        + " at or before " + b.amountMinor() + ", and " + b.amountMinor()
                        + " at or before " + c.amountMinor() + ", but " + a.amountMinor()
                        + " after " + c.amountMinor());
                    break outer;
                }
            }
        }

        List<Order> withDupes = new ArrayList<>(sample(200, 11));
        withDupes.add(withDupes.get(0));
        int expected = (int) withDupes.stream().distinct().count();
        int actual = deduplicate(withDupes).size();
        if (actual != expected)
            failures.add("3. deduplicate kept " + actual + " of " + expected + " distinct orders — "
                       + (expected - actual) + " rows silently dropped");

        List<Order> many = sample(100_000, 13);
        long[] calls = new long[1];
        Comparator<Order> largestFirst = Comparator.comparingInt(Order::amountMinor)
                                                   .reversed()
                                                   .thenComparingLong(Order::id);
        List<Order> top = topTen(many, counting(largestFirst, calls));
        List<Order> reference = many.stream().sorted(largestFirst).limit(10).toList();
        if (!top.equals(reference))
            failures.add("4. top ten is wrong");
        else if (calls[0] > 500_000)
            failures.add("4. top ten cost " + calls[0] + " comparisons for 10 rows out of "
                       + many.size() + " — budget is 500000");

        if (failures.isEmpty()) {
            System.out.println("PASS");
        } else {
            failures.forEach(f -> System.out.println("  " + f));
            System.out.println("FAIL");
        }
    }
}