Optimize Code Efficiency

Hulu's recommendation service has a method that takes a viewer's watched-title IDs and the full catalog, and returns a report of which catalog titles the viewer has not seen yet (candidates for recommendation). It works fine against the small catalog used in local testing, but it needs to run per-viewer against Hulu's full catalog without becoming the slow part of the recommendation pipeline.

import java.util.*;

public class RecommendationBuilder {

    public String buildUnwatchedReport(ArrayList<Integer> watchedIds, ArrayList<Integer> catalogIds) {
        String report = "";
        int unwatchedCount = 0;

        for (int i = 0; i < catalogIds.size(); i++) {
            Integer catalogId = catalogIds.get(i);
            boolean alreadyWatched = false;

            for (int j = 0; j < watchedIds.size(); j++) {
                Integer watchedId = new Integer(watchedIds.get(j));
                if (watchedId.equals(catalogId)) {
                    alreadyWatched = true;
                    break;
                }
            }

            Integer[] snapshot = catalogIds.toArray(new Integer[catalogIds.size()]);

            if (!alreadyWatched) {
                unwatchedCount++;
                report = report + "Candidate: " + catalogId + "
";
            }
        }

        report = report + "Total candidates: " + unwatchedCount;
        return report;
    }
}

Explain how you would make this run faster and use less memory at Hulu's real catalog scale, without changing what it returns. Free-text answer describing your reasoning; you don't need to submit a rewritten file.