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 lặp 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.

🎯 Đề bài

Viết hàm findCommonElements(A, 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 số nguyên A và B. Mỗi mảng có tối đa 1 triệu phần tử.
• Output: mảng 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 pseudocode

-- TODO: implement findCommonNaive -- mong đợi O(n*m)
function findCommonNaive(A, B):
    throw "TODO"

-- TODO: implement findCommonFast -- mong đợi O(n+m)
function findCommonFast(A, B):
    throw "TODO"

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

💡 Gợi ý

-- Skeleton hint -- điền logic vào
-- Time: O(n*m)  Space: O(k) với k là số phần tử chung
function findCommonNaive(A, B):
    result <- Set rỗng (tự dedup)
    for each x trong A:
        for each y trong B:
            if x = y:
                result.add(x)
                break          -- early exit: không cần scan tiếp B
    return result dưới dạng mảng

✅ Lời giải

-- Time: O(n*m)  Space: O(k) với k là số phần tử chung
function findCommonNaive(A, B):
    result <- Set rỗng
    for each x trong A:
        for each y trong B:
            if x = y:
                result.add(x)
                break             -- dedup early exit
    return result dưới dạng mảng

-- Nạp mảng nhỏ hơn vào hash set để tiết kiệm memory
-- Time: O(n+m)  Space: O(min(n,m))
function findCommonFast(A, B):
    if A.length <= B.length:
        smaller <- A
        larger  <- B
    else:
        smaller <- B
        larger  <- A

    seen <- HashSet(smaller)      -- nạp mảng nhỏ một lần: O(min(n,m))

    result <- Set rỗng
    for each x trong larger:
        if x trong seen:
            result.add(x)         -- dedup tự động

    return result dưới dạng mảng

-- Time: O(n log n + m log m) do sort  Space: O(n+m) cho bản sao
-- Tốt hơn khi input đã sorted sẵn; chậm hơn hash set trên random data
function findCommonTwoPointer(A, B):
    sortedA <- sort(copy(A))
    sortedB <- sort(copy(B))

    result <- []
    i <- 0
    j <- 0
    while i < sortedA.length AND j < sortedB.length:
        if sortedA[i] = sortedB[j]:
            val <- sortedA[i]
            result.append(val)
            -- bỏ qua duplicate liên tiếp để dedup
            while i < sortedA.length AND sortedA[i] = val: i <- i + 1
            while j < sortedB.length AND sortedB[j] = val: j <- j + 1
        else if sortedA[i] < sortedB[j]:
            i <- i + 1
        else:
            j <- j + 1
    return result

📊 Benchmark

-- Benchmark harness (pseudocode — implement trong ngôn ngữ bạn chọn)
function benchmark():
    A <- randomArray(1_000_000, seed=42)
    B <- randomArray(1_000_000, seed=42)

    -- warm up trước khi đo (quan trọng với JVM và JIT)
    repeat 3 times: findCommonFast(A, B)

    t0 <- now()
    result <- findCommonFast(A, B)
    elapsed <- now() - t0
    print "Fast  (n=1M):", elapsed, "ms,", result.length, "phần tử chung"

    -- naive quá chậm ở 1M -- chỉ chạy ở 10k
    A10k <- randomArray(10_000, seed=42)
    B10k <- randomArray(10_000, seed=42)

    repeat 3 times: findCommonNaive(A10k, B10k)

    t0 <- now()
    resultN <- findCommonNaive(A10k, B10k)
    elapsed <- now() - t0
    print "Naive (n=10k):", elapsed, "ms,", resultN.length, "phần tử chung"

Expected output (hardware hiện đại, runtime đã warm up):

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

xychart-beta
    title "Thời gian chạy theo n (ms)"
    x-axis ["1k", "10k", "100k"]
    y-axis "Thời gian (ms)" 0 --> 50000
    bar [5, 500, 50000]
    line [0.1, 1, 10]

Tại n=1 triệu, naive ≈ 5.000.000 ms (vượt khung) trong khi fast chỉ ~30 ms.

⚠️ Pitfall khi benchmark

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

JVM và nhiều runtime khác không compile code thành native ngay — 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 pseudocode trên).

Pitfall 2 — Dùng clock wall-time độ phân giải thấp.

Một số platform có timer interrupt resolution 10–20ms. Đ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. Dùng monotonic clock độ phân giải cao (nanosecond): System.nanoTime() trên JVM, time.perf_counter_ns() trên Python, performance.now() trên JavaScript.

-- Đo đúng: monotonic high-resolution clock
t0 <- monotonic_ns()
-- ... chạy hàm ...
elapsed_ms <- (monotonic_ns() - t0) / 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 hash set 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 processing:

-- Parallel filter trên mảng larger
seenSet <- HashSet(smaller)
result <- parallel_filter(larger, x => x trong seenSet).distinct()

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ử — hash set 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 ở Thuật toán Ứng dụng — Module 3 (Big Data & Streaming). Câu hỏi: trong bài này, false positive ảnh hưởng output thế nào?

🔗 Bài 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 — hash map đếm thay hash set.
• 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 → hash set → 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: high-resolution clock, runtime warm-up, fixed seed.
• Biết 3 cạm bẫy phổ biến khi micro-benchmark.
• Thấy hình dạng curve thực tế: naive tăng bậc hai, hash set tăng tuyến tính — số liệu xác nhận lý thuyết Big-O.

Bài tiếp theo: Module 1 — Tổng kết & cheat sheet

Một thư viện thật áp dụng ý tưởng amortized này ở đâu? Chính ArrayList của Java: mỗi lần đầy, nó nhân dung lượng lên 1.5 lần. Nếu bạn học Java, Java Internals — ArrayList.grow() cho thấy code OpenJDK và lý do chọn con số 1.5x.