Mini-challenge — findCommonElements: naive vs optimized

Teammate junior của bạn vừa nộp code để tìm phần tử chung giữa hai mảng. Manager test với 1 triệu phần tử mỗi mảng — máy chạy 8 giây rồi timeout. Manager hỏi bạn: "Optimize đi."

Bạn nhìn vào code và thấy hai vòng for lồng nhau. Bottleneck rõ ràng — nhưng fix thế nào? Và làm sao biết fix xong nhanh hơn bao nhiêu?

Bài này luyện framework 5 bước từ bài học trước: viết brute force → identify bottleneck → optimize → đo bằng benchmark nanoTime.

🎯 Đề bài

Viết hàm findCommonElements(int[] a, int[] b) trả về mảng các phần tử xuất hiện trong cả hai mảng đầu vào.

Yêu cầu chi tiết

• Input: hai mảng int[] a và int[] b. Mỗi mảng có tối đa 1 triệu phần tử. Giá trị trong khoảng Integer.MIN_VALUE đến Integer.MAX_VALUE.
• Output: int[] chứa các phần tử có mặt trong cả hai mảng. Mỗi phần tử xuất hiện đúng một lần trong output (dedup), không yêu cầu thứ tự.
• Target complexity: O(n+m) time, O(min(n,m)) space.

Test cases hiển thị

Test ẩn: 1 triệu random int + 1 triệu random int — xem phần benchmark.

📦 Starter code

import java.util.*;

public class CommonElementsChallenge {

    // TODO: implement using nested loop. Expect O(n*m).
    public static int[] findCommonNaive(int[] a, int[] b) {
        throw new UnsupportedOperationException("TODO");
    }

    // TODO: implement using HashSet. Expect O(n+m).
    public static int[] findCommonFast(int[] a, int[] b) {
        throw new UnsupportedOperationException("TODO");
    }

    public static void main(String[] args) {
        // visible test cases
        System.out.println(Arrays.toString(findCommonNaive(new int[]{1,2,3}, new int[]{2,3,4}))); // [2, 3]
        System.out.println(Arrays.toString(findCommonNaive(new int[]{},    new int[]{1})));        // []
        System.out.println(Arrays.toString(findCommonNaive(new int[]{1,1,2}, new int[]{1,2,2}))); // [1, 2]
        System.out.println(Arrays.toString(findCommonNaive(new int[]{5},   new int[]{5})));        // [5]
    }
}

Dành 20–25 phút tự làm trước khi xem gợi ý.

💡 Gợi ý

// Skeleton hint -- fill in the logic
public static int[] findCommonNaive(int[] a, int[] b) {
    Set<Integer> result = new LinkedHashSet<>();
    for (int x : a) {
        for (int y : b) {
            if (x == y) {
                result.add(x); // add handles dedup automatically
                break;         // early exit: no need to keep scanning b
            }
        }
    }
    // convert Set<Integer> -> int[]
    return result.stream().mapToInt(Integer::intValue).toArray();
}

✅ Lời giải

public static int[] findCommonNaive(int[] a, int[] b) {
    Set<Integer> result = new LinkedHashSet<>();
    for (int x : a) {
        for (int y : b) {
            if (x == y) {
                result.add(x);
                break; // dedup early exit
            }
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

public static int[] findCommonFast(int[] a, int[] b) {
    // pick smaller array for hashset to save memory
    int[] smaller = a.length <= b.length ? a : b;
    int[] larger  = a.length >  b.length ? a : b;

    // load factor 0.75 default -- pre-size to avoid rehash
    Set<Integer> seen = new HashSet<>(smaller.length * 4 / 3 + 1);
    for (int x : smaller) seen.add(x);

    Set<Integer> result = new LinkedHashSet<>();
    for (int x : larger) {
        if (seen.contains(x)) result.add(x);
    }

    int[] out = new int[result.size()];
    int i = 0;
    for (int v : result) out[i++] = v;
    return out;
}

public static int[] findCommonTwoPointer(int[] a, int[] b) {
    int[] sortedA = Arrays.copyOf(a, a.length);
    int[] sortedB = Arrays.copyOf(b, b.length);
    Arrays.sort(sortedA);
    Arrays.sort(sortedB);

    List<Integer> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < sortedA.length && j < sortedB.length) {
        if (sortedA[i] == sortedB[j]) {
            // dedup: skip consecutive duplicates
            int val = sortedA[i];
            result.add(val);
            while (i < sortedA.length && sortedA[i] == val) i++;
            while (j < sortedB.length && sortedB[j] == val) j++;
        } else if (sortedA[i] < sortedB[j]) {
            i++;
        } else {
            j++;
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

📊 Benchmark harness

import java.util.*;

public class BenchHarness {

    public static void main(String[] args) {
        int[] a = randomArr(1_000_000);
        int[] b = randomArr(1_000_000);

        // warm up JIT -- run a few times before measuring
        for (int i = 0; i < 3; i++) {
            findCommonFast(a, b);
        }

        long start = System.nanoTime();
        int[] result = findCommonFast(a, b);
        long elapsed = System.nanoTime() - start;
        System.out.printf("Fast  (n=1M): %4d ms, %d common elements%n",
            elapsed / 1_000_000, result.length);

        // naive is too slow at 1M -- run only at 10k
        int[] a10k = randomArr(10_000);
        int[] b10k = randomArr(10_000);

        // warm up for naive
        for (int i = 0; i < 3; i++) {
            findCommonNaive(a10k, b10k);
        }

        long startN = System.nanoTime();
        int[] resultN = findCommonNaive(a10k, b10k);
        long elapsedN = System.nanoTime() - startN;
        System.out.printf("Naive (n=10k): %4d ms, %d common elements%n",
            elapsedN / 1_000_000, resultN.length);
    }

    static int[] randomArr(int n) {
        Random r = new Random(42); // fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = r.nextInt(n / 2);
        return arr;
    }
}

Expected output (JVM warmed up, modern hardware):

Số thực tế phụ thuộc vào máy và JVM. Điều quan trọng là hình dạng curve: naive tăng bậc hai, fast tăng tuyến tính.

⚠️ Pitfall khi benchmark

Pitfall 1 — Quên warm up JVM trước khi đo.

JVM không compile bytecode thành native code ngay lập tức — có JIT tier C1 (quick compile) và C2 (optimized compile). Lần chạy đầu tiên luôn chậm hơn 2–10x do interpretation overhead. Nếu đo ngay lần đầu → kết quả nhiễu, không phản ánh steady-state performance.

Fix: chạy 3–5 lần warm-up trước khi lấy thời gian (như đoạn code trên).

Pitfall 2 — Dùng System.currentTimeMillis() thay System.nanoTime().

currentTimeMillis() có resolution 10–20ms trên Windows (phụ thuộc timer interrupt). Đo một hàm chạy 1ms → kết quả luôn ra 0ms hoặc 10ms, không có giá trị nào ở giữa. nanoTime() dùng monotonic clock với nanosecond resolution — đây là chuẩn cho micro-benchmark.

// Wrong: too coarse on Windows
long start = System.currentTimeMillis();
// ... run ...
long ms = System.currentTimeMillis() - start; // granularity 10-20ms

// Correct
long start = System.nanoTime();
// ... run ...
long ms = (System.nanoTime() - start) / 1_000_000;

Pitfall 3 — Random seed cố định (42) — tốt cho reproducibility, nhưng có cạm bẫy.

Fixed seed đảm bảo mọi người chạy cùng kết quả — tốt cho debug và sharing. Tuy nhiên một pattern data cụ thể có thể làm HashSet degenerate (nhiều collision) hoặc làm naive nhanh hơn bình thường (early exit nhiều). Nếu benchmark cho production, chạy với nhiều seed khác nhau để xác nhận kết quả nhất quán.

🎓 Variant để tự thử

Variant 1 — Parallel stream:

// Does parallel help for 1M elements?
Set<Integer> seenSet = /* build from smaller array */;
int[] result = Arrays.stream(larger).parallel()
    .filter(seenSet::contains)
    .distinct()
    .toArray();

Thử đo xem có nhanh hơn findCommonFast không. Spoiler: parallel giúp chỉ khi n đủ lớn và operation đủ nặng. Fork/join overhead thường lớn hơn gain với n dưới 10 triệu và operation đơn giản như contains.

Variant 2 — Input streaming (không vào hết RAM):

Nếu mảng không fit RAM — ví dụ 10 tỷ phần tử — HashSet cũng không dùng được. Gợi ý: Bloom filter xấp xỉ tập hợp với xác suất false positive nhỏ, dùng rất ít memory. Sẽ học ở Module 3 (Big Data & Streaming). Câu hỏi: trong bài này, false positive ảnh hưởng output thế nào?

🔗 LeetCode liên quan

Bài này map trực tiếp sang ba bài LeetCode:

• 349. Intersection of Two Arrays — dedup, trả về set. Đúng bài này.
• 350. Intersection of Two Arrays II — giữ số lần xuất hiện (duplicate count). Cần approach khác — HashMap đếm thay HashSet.
• 1213. Intersection of Three Sorted Arrays — extension sang 3 mảng, input đã sorted → 3-pointer.

✨ Điều bạn vừa làm được

• Áp framework 5 bước vào bài toán thực tế: brute force → identify bottleneck → HashSet → benchmark verify.
• Nhận ra inner loop O(m) là bottleneck, trade O(min(n,m)) memory để cắt về O(n+m).
• Đo benchmark đúng cách: nanoTime, JVM warm-up, fixed seed.
• Biết 3 cạm bẫy phổ biến khi micro-benchmark JVM code.
• Thấy hình dạng curve thực tế: naive tăng bậc hai, HashSet tăng tuyến tính — số liệu xác nhận lý thuyết Big-O.

Bài tiếp theo: Case Study: java.util.ArrayList.grow()