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<>();
    for (Future<List<Integer>> f : parts) result.addAll(f.get());  // merge in range order
    pool.shutdown();
    Collections.sort(result);   // ranges are ordered, but sort makes intent explicit
    return result;
}

Correct Go

func search(a []int, key, workers int) []int {
    n := len(a); chunk := (n + workers - 1) / workers
    ch := make(chan []int, workers)
    for t := 0; t < workers; t++ {
        lo, hi := t*chunk, min((t+1)*chunk, n)
        go func(lo, hi int) {
            var local []int
            for i := lo; i < hi; i++ { if a[i] == key { local = append(local, i) } }
            ch <- local                 // hand the slice back over a channel
        }(lo, hi)
    }
    var res []int
    for t := 0; t < workers; t++ { res = append(res, (<-ch)...) }
    sort.Ints(res); return res
}

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.

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.

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.