Problem 3 Linear Search with Indices and Occurrences

Find every index of a key, in parallel — without a shared-write bottleneck

Given an array, report all indices where a key occurs, using several threads. The mechanism that makes this scale is partition → collect locally → merge: split the array into contiguous ranges, give one range to each thread, let each thread accumulate its hits into its own list (no sharing, so no lock), then combine the per-thread lists at the end. Sharing one list behind a lock — which the earlier version did — serializes every hit and defeats the point of going parallel.

Correct worked trace

Array [4, 5, 4, 6, 4, 7, 8, 4, 9, 5] (indices 0-9), key = 4. The value 4 sits at indices 0, 2, 4, 7 — four occurrences. (The earlier page reported index 8 for the fourth 4, but index 8 holds 9; the fourth 4 is at index 7.)

index	0	1	2	3	4	5	6	7	8	9
value	4	5	4	6	4	7	8	4	9	5
hit?	✓		✓		✓			✓

Result: [0, 2, 4, 7].

Correct Java (lock-free local collection, then merge)

import java.util.*;
import java.util.concurrent.*;

List<Integer> search(int[] a, int key, int numThreads) throws Exception {
    ExecutorService pool = Executors.newFixedThreadPool(numThreads);
    int n = a.length, chunk = (n + numThreads - 1) / numThreads;
    List<Future<List<Integer>>> parts = new ArrayList<>();

    for (int t = 0; t < numThreads; t++) {
        final int lo = t * chunk, hi = Math.min(lo + chunk, n);
        parts.add(pool.submit(() -> {
            List<Integer> local = new ArrayList<>();   // thread-private: no lock needed
            for (int i = lo; i < hi; i++) if (a[i] == key) local.add(i);
            return local;
        }));
    }
    List<Integer> result = new ArrayList<>();
    // Collect futures in ascending partition id order → already sorted indices.
    // sort is unnecessary O(k log k) when partitions are contiguous and merged in order.
    for (Future<List<Integer>> f : parts) result.addAll(f.get());
    pool.shutdown();
    // Collections.sort(result); // only if completion order ≠ partition order
    return result;
}

When sort is needed: if you push locals into a concurrent bag or receive from a channel in completion order (not partition id), indices are a permutation of the true hit set — then sort. If you get() futures 0..T-1 or store List[] byPart and concatenate in id order, append is already ascending — prefer O(k) merge of k hits.

Correct Go

func search(a []int, key, workers int) []int {
    n := len(a); chunk := (n + workers - 1) / workers
    parts := make([][]int, workers)
    var wg sync.WaitGroup
    for t := 0; t < workers; t++ {
        wg.Add(1)
        lo, hi := t*chunk, min((t+1)*chunk, n)
        go func(t, lo, hi int) {
            defer wg.Done()
            var local []int
            for i := lo; i < hi; i++ { if a[i] == key { local = append(local, i) } }
            parts[t] = local // slot per partition — no race on different indices
        }(t, lo, hi)
    }
    wg.Wait()
    var res []int
    for t := 0; t < workers; t++ { res = append(res, parts[t]...) } // ordered merge
    return res // already sorted; sort.Ints only if you used unordered fan-in
}

Pitfalls

• Don't share one list behind a lock. Every match would contend on the lock; with many hits you've built a sequential program wearing a parallel costume. Collect locally, merge once.
• Linear scan is memory-bandwidth bound; past a few threads you won't speed up because the bottleneck is RAM, not CPU. Parallelism helps most when work per element is non-trivial.

Collection-choice trade-off

The local ArrayList is the right default here because writes are frequent and private to each thread. In other shapes of this problem a different collection wins:

Collection	Best when	Why / cost
Local ArrayList per thread	Hits are frequent and thread-local partition is cheap.	Zero contention; pays only the final merge.
Collections.synchronizedList	Must share one list and hits are rare.	Simple but serializes every write; loses parallelism on the hot path.
CopyOnWriteArrayList	Reads dominate and writes are very rare.	Each write copies the whole array; catastrophic if hits are common.
ConcurrentLinkedQueue	Ordering does not matter and you want lock-free sharing.	Fine for a shared bag of hits, but you still pay coordination cost per insertion.

The rule of thumb: start with a private accumulator; only introduce a shared concurrent collection when the merge itself becomes a bottleneck or when partitions are impossible.

Takeaways

• Partition → collect per-thread (no lock) → merge: the default shape for parallel reductions/searches.
• The fourth 4 is at index 7, not 8 — verify your own traces against the data.
• A shared locked accumulator serializes the hot path; private accumulators don't.

---

Re-authored for correctness for this guide (the prior version mis-reported an index and shared one locked list). See also: Critical Section & Race Condition, ForkJoin Approach.

Why the speed-up plateaus: this scan is memory-bandwidth bound

The pitfall list warns that "past a few threads you won't speed up." That is worth turning into a number, because it is the follow-up an interviewer will push on. Each iteration reads one 4-byte int and does a single compare — roughly one arithmetic op per 4 bytes touched. That ratio (ops per byte) is the kernel's arithmetic intensity, and here it is tiny: ~0.25 ops/byte. A modern core can retire billions of compares per second, but a socket's DRAM only delivers on the order of 25 GB/s. So the ceiling is set by memory, not by cores.

Concretely, scanning n = 100 million ints means streaming 400 MB. At 25 GB/s that is a hard floor of ≈16 ms — no matter how many threads you throw at it. One or two threads already saturate a channel's worth of bandwidth, so going from 2→8 threads on the same socket buys almost nothing; you have hit the roofline's flat memory ceiling. The classic tell in a benchmark is a curve that scales cleanly to ~2× and then goes flat while CPUs sit at 100% but stalled on memory. Real speed-up returns only when (a) the array spans multiple NUMA nodes/sockets so you add bandwidth, not just cores, or (b) the per-element work grows (a regex match, a distance computation) so arithmetic intensity rises and you leave the memory-bound regime for the compute-bound one. This is why "add more threads" is the wrong instinct for a bare scan and the right instinct for a heavy per-item kernel.

Drill ladder — defend the design under a hostile follow-up

• L1 — "Does splitting across K threads make this O(n/K)?" No. Total work stays Θ(n) comparisons; only the span (wall-clock) can approach Θ(n/K), and only while the scan is compute-bound and K ≤ cores. State work and span separately or you have answered the wrong question.
• L2 — "You returned [0,2,4,7] already sorted without a sort call. Lucky, or guaranteed?" Guaranteed, because partitions are contiguous and merged in ascending partition-id order — each thread's local hits are ascending within its range, and range i precedes range i+1. The moment you fan results in by completion order (a shared queue, CompletionService), that invariant is gone and you must sort.
• L3 — "Benchmarks show 1.9× at 2 threads, then flat to 8. Bug or expected?" Expected — the scan is memory-bandwidth bound (~0.25 ops/byte), so a couple of threads saturate DRAM and the rest stall. Fix by adding bandwidth (NUMA/sockets) or raising per-element work, not by adding threads.
• L4 — "Would padding each thread's counter to a cache line help?" Only if threads shared adjacent slots of one array (false sharing). Here each thread owns a heap ArrayList, so their write targets are already far apart — padding buys nothing. False sharing is the trap when you "optimize" into a shared int[] counts indexed by thread id.

I'm working on the problem **Problem 3 Linear Search with Indices and Occurrences** (Concurrency). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Problem 3 Linear Search with Indices and Occurrences** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Problem 3 Linear Search with Indices and Occurrences**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Problem 3 Linear Search with Indices and Occurrences**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.