Problem 2 Linear Search for All Occurrences

Split the array into one contiguous chunk per thread, have each thread scan its chunk for the key, and merge the per-thread hits at the end — the parallelism is safe because each thread reads a disjoint index range and only the merge step touches shared state.

The single design decision that separates a correct-but-slow solution from a fast one is where threads write their results. The naive approach hands every thread a pointer to one shared ArrayList guarded by a single lock; the better approach gives each thread a private list and merges once. Both are correct. Only one scales.

The mechanism: disjoint reads, contended writes

Reading the array needs no synchronization — the input is immutable during the search and every thread owns a non-overlapping [start, end) slice, so two threads can never read-write the same cell. The only shared mutable object is the results collection. Every time a thread finds the key it must record the index somewhere, and that "somewhere" is the hot spot.

An ArrayList is not thread-safe: concurrent add calls can corrupt its internal size counter and backing array, dropping elements or throwing ArrayIndexOutOfBoundsException. So you serialize the writes with one lock. That makes it correct — but now every hit, across every thread, funnels through one mutex.

Worked example: find all 12s in [4, 15, 12, 3, 12, 9, 12]

Array length 7, key = 12, 3 threads. Chunk size = 7 / 3 = 2 (integer division), and the last thread absorbs the remainder, so the slices are not all equal:

T0 finds nothing. T1 finds index 2. T2 finds indices 4 and 6. The set of correct answers is {2, 4, 6} — but the order they land in the shared list depends on which thread grabbed the lock first. A run might produce [4, 6, 2] or [2, 4, 6] or [4, 2, 6]. If you need ascending indices, you must sort after the merge — parallel search does not preserve scan order.

Java: the naive version (correct, contended)

This is the version most people write first. It works, and for sparse keys it is fine — but read on for why it does not scale.

import java.util.*;

public class AllOccurrences {
  static final int NUM_THREADS = 4;
  static final Object lock = new Object();
  static final List<Integer> found = new ArrayList<>();

  static void search(int id, int[] arr, int key) {
    int chunk = arr.length / NUM_THREADS;
    int start = id * chunk;
    int end = (id == NUM_THREADS - 1) ? arr.length : start + chunk;
    for (int i = start; i < end; i++) {
      if (arr[i] == key) {
        synchronized (lock) {   // every hit serializes here
          found.add(i);
        }
      }
    }
  }

  public static void main(String[] a) throws InterruptedException {
    int[] arr = {4, 15, 12, 3, 12, 9, 12};
    int key = 12;
    List<Thread> ts = new ArrayList<>();
    for (int i = 0; i < NUM_THREADS; i++) {
      int id = i;
      Thread t = new Thread(() -> search(id, arr, key));
      ts.add(t); t.start();
    }
    for (Thread t : ts) t.join();
    Collections.sort(found);            // restore ascending index order
    System.out.println(found);          // [2, 4, 6]
  }
}

Why the unsynchronized version is wrong: drop the synchronized block and two threads can call found.add simultaneously. ArrayList.add does elementData[size++] = e — a non-atomic read-increment-write of size. Interleaved, both threads read the same size, one overwrites the other's element, and the count ends up wrong. You silently lose indices, or trip an ArrayIndexOutOfBoundsException mid-resize. The bug is intermittent, which is the worst kind.

Java: the better version (per-thread local list, single merge)

Give each thread a private ArrayList it owns exclusively — no lock needed during the scan — then concatenate the lists once on the main thread after join. This is exactly the structure Problem 3 generalizes. Zero lock acquisitions on the hot path.

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

public class AllOccurrencesFast {
  static final int NUM_THREADS = 4;

  public static void main(String[] a) throws Exception {
    int[] arr = {4, 15, 12, 3, 12, 9, 12};
    int key = 12;
    List<List<Integer>> partials = new ArrayList<>();
    List<Thread> ts = new ArrayList<>();

    for (int i = 0; i < NUM_THREADS; i++) {
      List<Integer> local = new ArrayList<>();   // private to this thread
      partials.add(local);
      int id = i;
      int chunk = arr.length / NUM_THREADS;
      int start = id * chunk;
      int end = (id == NUM_THREADS - 1) ? arr.length : start + chunk;
      Thread t = new Thread(() -> {
        for (int j = start; j < end; j++)
          if (arr[j] == key) local.add(j);     // no lock: sole writer
      });
      ts.add(t); t.start();
    }
    for (Thread t : ts) t.join();

    List<Integer> found = new ArrayList<>();
    for (List<Integer> p : partials) found.addAll(p);  // merge, single-threaded
    Collections.sort(found);                            // if order matters
    System.out.println(found);                          // [2, 4, 6]
  }
}

Each thread is the sole writer to local, and the main thread only reads partials after join — and join establishes a happens-before edge, so the reads see every write with no extra synchronization. Note that iterating partials in thread-index order makes results per-chunk ordered (T0's hits, then T1's, ...) even before sorting, which is often good enough.

Go: the same two designs

Go's idiom replaces the shared lock with a channel, or — closer to the "local list + merge" design — pre-sized per-goroutine slots written without any synchronization. A sync.WaitGroup stands in for the join loop.

package main

import (
	"fmt"
	"sort"
	"sync"
)

func main() {
	arr := []int{4, 15, 12, 3, 12, 9, 12}
	key, numG := 12, 4

	partials := make([][]int, numG) // one slot per goroutine
	var wg sync.WaitGroup

	for g := 0; g < numG; g++ {
		chunk := len(arr) / numG
		start := g * chunk
		end := start + chunk
		if g == numG-1 {
			end = len(arr)
		}
		wg.Add(1)
		go func(g, start, end int) {
			defer wg.Done()
			var local []int // owned by this goroutine
			for i := start; i < end; i++ {
				if arr[i] == key {
					local = append(local, i)
				}
			}
			partials[g] = local // distinct index per goroutine: no race
		}(g, start, end)
	}
	wg.Wait()

	var found []int
	for _, p := range partials {
		found = append(found, p...) // merge after Wait
	}
	sort.Ints(found)
	fmt.Println(found) // [2 4 6]
}

Writing each goroutine's result into its own partials[g] slot is race-free because the indices are distinct and wg.Wait() happens-before the merge read — confirm with go run -race. The channel alternative (hits := make(chan int), each goroutine sends, a collector ranges over it) is more idiomatic when you don't know the result count up front, at the cost of one channel send per hit.

Where the two runtimes differ

• Threads vs goroutines. Each Java Thread is an OS thread (~1 MB stack, kernel-scheduled). Spawning one per chunk is fine at NUM_THREADS = 4 but ruinous at thousands. A goroutine starts at ~2 KB and is multiplexed onto a small pool of OS threads by the Go runtime, so "one goroutine per chunk" scales to far finer granularity.
• Lock vs channel. Java's synchronized / wait / notify is mutual exclusion over shared memory. Go's chan int moves the value between goroutines so ownership transfers instead of being shared — "don't communicate by sharing memory; share memory by communicating." Both express the merge; the channel version needs no explicit lock.
• Race detection. Go ships -race, a built-in dynamic detector that flags the unsynchronized-ArrayList class of bug at runtime. Java has no equivalent in the standard toolchain — you reason about happens-before yourself or reach for tools like jcstress.

Pitfalls

• Unsynchronized shared ArrayList. The headline bug. Concurrent add corrupts size and the backing array — lost indices or ArrayIndexOutOfBoundsException, intermittently. Either lock it, use a thread-safe collection, or (best) avoid sharing entirely.
• Lock contention when the key is dense. The single-lock design serializes every match. If the key occurs in half the array, threads spend most of their time queued on the mutex and you can run slower than a single-threaded scan. The per-thread-list design has zero hot-path locking — this is the whole reason to prefer it.
• Assuming the result is sorted. Parallel search returns indices in lock-acquisition order, which is non-deterministic. If a caller expects ascending indices, Collections.sort / sort.Ints after the merge — or merge per-chunk slices in thread order, which is already sorted within and across chunks.
• Integer-division chunking drops the tail. 7 / 3 = 2 covers only indices 0–5; index 6 is lost unless the last thread takes end = arr.length. Always give the final chunk the remainder (both versions above do).
• Reusing CopyOnWriteArrayList as the "easy fix." It is thread-safe but copies the entire backing array on every add — O(n) per write, O(n²) total. Catastrophic for a write-heavy collector. It is for read-mostly data, not this.

Takeaways

• The reads are embarrassingly parallel (disjoint slices, immutable input); the only synchronization problem is collecting results.
• One shared list + one lock is correct but serializes every match — fine for sparse keys, a contention disaster for dense ones.
• Per-thread local list + a single post-join merge eliminates hot-path locking entirely. This is the pattern Problem 3 builds on; prefer it by default.
• Parallel results are unordered by index — sort after merging if order matters, and always give the last chunk the array's remainder.

Re-authored and deepened for this guide. Mechanism, contention analysis, and the local-list-plus-merge design draw on Brian Goetz et al., Java Concurrency in Practice (happens-before, thread confinement); the Go idioms and the race detector follow Effective Go and the official sync / -race documentation. Worked example traced on [4, 15, 12, 3, 12, 9, 12] searching for 12. Earlier raster screenshots replaced with the authored two-design diagram and a corrected, compiling Java + Go pair.