go-04-map-concurrent
1.000
Challenge · difficulty 4/5
# Concurrent ordered map
Implement **`solution.go`** in `package challenge` exporting:
```go
func MapConcurrent(inputs []int, workers int, fn func(int) int) []int
```
Apply `fn` to every element of `inputs` using a pool of **at most `workers`**
goroutines running concurrently, and return the results.
Rules:
- The returned slice has the **same length** as `inputs`, and `result[i]` is
`fn(inputs[i])` — i.e. results are in the **same order as the inputs**,
regardless of the order goroutines finish in.
- Work must be distributed across concurrent goroutines (use goroutines plus
channels and/or `sync.WaitGroup`). No more than `workers` goroutines may be
processing elements at the same time.
- `workers` may be larger than `len(inputs)`; never start more workers than
there is work for, and never start fewer than one when there is work.
- If `inputs` is empty (or `nil`), return an empty (non-nil is fine, but it must
have length 0) slice without starting any work.
- You may assume `workers >= 1` and that `fn` is safe to call concurrently
(it does not share mutable state).
Examples:
- `MapConcurrent([]int{1, 2, 3}, 2, func(x int) int { return x * x })` → `[]int{1, 4, 9}`
- `MapConcurrent([]int{}, 4, fn)` → `[]int{}`
- `MapConcurrent([]int{5}, 8, func(x int) int { return x + 1 })` → `[]int{6}`
tests/solution_test.go
package challenge
import (
"reflect"
"sync"
"sync/atomic"
"testing"
)
func TestMapConcurrentMatchesSequential(t *testing.T) {
fn := func(x int) int { return x*x + 1 }
cases := []struct {
name string
inputs []int
workers int
}{
{"empty", []int{}, 4},
{"nil", nil, 4},
{"single", []int{7}, 1},
{"single many workers", []int{7}, 16},
{"workers one", []int{1, 2, 3, 4, 5}, 1},
{"workers equal len", []int{1, 2, 3, 4}, 4},
{"workers gt len", []int{1, 2, 3}, 10},
{"larger", []int{9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2}, 3},
{"negatives", []int{-5, -4, -3, -2, -1}, 2},
}
for _, c := range cases {
t.Run(c.name, func(t *testing.T) {
want := make([]int, len(c.inputs))
for i, v := range c.inputs {
want[i] = fn(v)
}
got := MapConcurrent(c.inputs, c.workers, fn)
if len(got) != len(c.inputs) {
t.Fatalf("len = %d, want %d", len(got), len(c.inputs))
}
if !reflect.DeepEqual(got, want) {
t.Errorf("MapConcurrent(%v, %d) = %v, want %v", c.inputs, c.workers, got, want)
}
})
}
}
func TestMapConcurrentOrderPreserved(t *testing.T) {
// Identity maps input value to output position; any reordering would be caught.
inputs := make([]int, 200)
for i := range inputs {
inputs[i] = i * 3
}
got := MapConcurrent(inputs, 7, func(x int) int { return x })
for i, v := range inputs {
if got[i] != v {
t.Fatalf("index %d = %d, want %d (order not preserved)", i, got[i], v)
}
}
}
func TestMapConcurrentEmptyReturnsLenZero(t *testing.T) {
got := MapConcurrent(nil, 4, func(x int) int { return x })
if len(got) != 0 {
t.Fatalf("len = %d, want 0", len(got))
}
}
func TestMapConcurrentRespectsWorkerLimit(t *testing.T) {
inputs := make([]int, 100)
for i := range inputs {
inputs[i] = i
}
const limit = 4
var mu sync.Mutex
cond := sync.NewCond(&mu)
var active int64
var maxActive int64
var arrived int
// fn blocks until either `limit` callers are concurrently in flight or no more
// callers can arrive. This forces real concurrency while bounding it at `limit`:
// if the implementation ran fewer than `limit` workers it would deadlock-stall,
// and any run above `limit` would be recorded in maxActive.
fn := func(x int) int {
cur := atomic.AddInt64(&active, 1)
for {
m := atomic.LoadInt64(&maxActive)
if cur <= m || atomic.CompareAndSwapInt64(&maxActive, m, cur) {
break
}
}
mu.Lock()
arrived++
if arrived >= limit {
cond.Broadcast()
}
for arrived < limit {
cond.Wait()
}
mu.Unlock()
atomic.AddInt64(&active, -1)
return x * 2
}
got := MapConcurrent(inputs, limit, fn)
if m := atomic.LoadInt64(&maxActive); m > limit {
t.Fatalf("observed %d concurrent workers, limit was %d", m, limit)
}
if atomic.LoadInt64(&maxActive) < 2 {
t.Fatalf("no real concurrency observed (maxActive=%d)", maxActive)
}
for i := range inputs {
if got[i] != inputs[i]*2 {
t.Fatalf("index %d = %d, want %d", i, got[i], inputs[i]*2)
}
}
}
func TestMapConcurrentCallsFnOncePerElement(t *testing.T) {
inputs := []int{10, 20, 30, 40, 50, 60}
var calls int64
got := MapConcurrent(inputs, 3, func(x int) int {
atomic.AddInt64(&calls, 1)
return x + 1
})
if calls != int64(len(inputs)) {
t.Fatalf("fn called %d times, want %d", calls, len(inputs))
}
for i, v := range inputs {
if got[i] != v+1 {
t.Errorf("index %d = %d, want %d", i, got[i], v+1)
}
}
}
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.
Proposed solution
```go
package challenge
func MapConcurrent(inputs []int, workers int, fn func(int) int) []int {
// Handle empty or nil input
if len(inputs) == 0 {
return []int{}
}
// Ensure workers doesn't exceed the number of inputs
if workers > len(inputs) {
workers = len(inputs)
}
// Initialize result slice with the same length as inputs
result := make([]int, len(inputs))
// Create channels for work distribution and coordination
inputChan := make(chan struct {
index int
value int
})
outputChan := make(chan struct {
index int
value int
})
// Start worker goroutines
for i := 0; i < workers; i++ {
go func() {
for work := range inputChan {
outputChan <- struct {
index int
value int
}{
index: work.index,
value: fn(work.value),
}
}
}()
}
// Send all inputs to the input channel
go func() {
for i, val := range inputs {
inputChan <- struct {
index int
value int
}{index: i, value: val}
}
close(inputChan)
}()
// Collect results in order
for i := 0; i < len(inputs); i++ {
out := <-outputChan
result[out.index] = out.value
}
return result
}
```Test output (stdout)
56366+02:00","Action":"run","Package":"challenge","Test":"TestMapConcurrentMatchesSequential/negatives"}
{"Time":"2026-07-01T22:48:37.880757546+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentMatchesSequential/negatives","Output":"=== RUN TestMapConcurrentMatchesSequential/negatives\n"}
{"Time":"2026-07-01T22:48:37.880758806+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentMatchesSequential/negatives","Output":"--- PASS: TestMapConcurrentMatchesSequential/negatives (0.00s)\n"}
{"Time":"2026-07-01T22:48:37.880759826+02:00","Action":"pass","Package":"challenge","Test":"TestMapConcurrentMatchesSequential/negatives","Elapsed":0}
{"Time":"2026-07-01T22:48:37.880760956+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentMatchesSequential","Output":"--- PASS: TestMapConcurrentMatchesSequential (0.00s)\n"}
{"Time":"2026-07-01T22:48:37.880763116+02:00","Action":"pass","Package":"challenge","Test":"TestMapConcurrentMatchesSequential","Elapsed":0}
{"Time":"2026-07-01T22:48:37.880764146+02:00","Action":"run","Package":"challenge","Test":"TestMapConcurrentOrderPreserved"}
{"Time":"2026-07-01T22:48:37.880765036+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentOrderPreserved","Output":"=== RUN TestMapConcurrentOrderPreserved\n"}
{"Time":"2026-07-01T22:48:37.880855066+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentOrderPreserved","Output":"--- PASS: TestMapConcurrentOrderPreserved (0.00s)\n"}
{"Time":"2026-07-01T22:48:37.880865836+02:00","Action":"pass","Package":"challenge","Test":"TestMapConcurrentOrderPreserved","Elapsed":0}
{"Time":"2026-07-01T22:48:37.880869566+02:00","Action":"run","Package":"challenge","Test":"TestMapConcurrentEmptyReturnsLenZero"}
{"Time":"2026-07-01T22:48:37.880870766+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentEmptyReturnsLenZero","Output":"=== RUN TestMapConcurrentEmptyReturnsLenZero\n"}
{"Time":"2026-07-01T22:48:37.880875216+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentEmptyReturnsLenZero","Output":"--- PASS: TestMapConcurrentEmptyReturnsLenZero (0.00s)\n"}
{"Time":"2026-07-01T22:48:37.880876586+02:00","Action":"pass","Package":"challenge","Test":"TestMapConcurrentEmptyReturnsLenZero","Elapsed":0}
{"Time":"2026-07-01T22:48:37.880877886+02:00","Action":"run","Package":"challenge","Test":"TestMapConcurrentRespectsWorkerLimit"}
{"Time":"2026-07-01T22:48:37.880880256+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentRespectsWorkerLimit","Output":"=== RUN TestMapConcurrentRespectsWorkerLimit\n"}
{"Time":"2026-07-01T22:48:37.880970847+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentRespectsWorkerLimit","Output":"--- PASS: TestMapConcurrentRespectsWorkerLimit (0.00s)\n"}
{"Time":"2026-07-01T22:48:37.880972317+02:00","Action":"pass","Package":"challenge","Test":"TestMapConcurrentRespectsWorkerLimit","Elapsed":0}
{"Time":"2026-07-01T22:48:37.880980697+02:00","Action":"run","Package":"challenge","Test":"TestMapConcurrentCallsFnOncePerElement"}
{"Time":"2026-07-01T22:48:37.880981977+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentCallsFnOncePerElement","Output":"=== RUN TestMapConcurrentCallsFnOncePerElement\n"}
{"Time":"2026-07-01T22:48:37.880989517+02:00","Action":"output","Package":"challenge","Test":"TestMapConcurrentCallsFnOncePerElement","Output":"--- PASS: TestMapConcurrentCallsFnOncePerElement (0.00s)\n"}
{"Time":"2026-07-01T22:48:37.880990947+02:00","Action":"pass","Package":"challenge","Test":"TestMapConcurrentCallsFnOncePerElement","Elapsed":0}
{"Time":"2026-07-01T22:48:37.880993587+02:00","Action":"output","Package":"challenge","Output":"PASS\n"}
{"Time":"2026-07-01T22:48:37.881072717+02:00","Action":"output","Package":"challenge","Output":"ok \tchallenge\t0.001s\n"}
{"Time":"2026-07-01T22:48:37.881083897+02:00","Action":"pass","Package":"challenge","Elapsed":0.001}