Skip to content

Table of Contents

Month 3 · Week 4 — Exercises

Building blocks for the Week 4 concurrency project (a crawler): a dedup set, a bounded concurrent crawler, and a token-bucket rate limiter. Each folder is its own package with a solution and table-driven tests. Standard library only. Always run under the race detector — concurrency bugs hide from a plain go test.

Exercise Concept Day Run tests
visited/ goroutine-safe "seen URL" set; check-and-insert under one lock 079 go test -race ./visited
crawl/ bounded concurrent crawler over a link graph; single-owner dedup, no mutex 078-079 go test -race ./crawl
tokenbucket/ deterministic token-bucket limiter (Allow/Refill), time injected 081 go test -race ./tokenbucket

How to use

  1. Try it yourself first — rename the solution aside and re-implement from the prompt below.
  2. Run go test -race ./... from this directory.
  3. Compare with the provided solution; log differences in your day note's "Mistakes" section.

Prompts

  • visited: implement a Set safe for concurrent use whose MarkSeen(url string) bool returns true only the FIRST time a URL is seen and records it, all under a single lock so the check-and-insert is atomic. The zero value must be usable (lazy-init the map); it must not be copied (pass *Set). A 200-goroutine race on one URL must produce exactly one winner.
  • crawl: implement Crawl(seeds []string, fetch Fetch, workers int) []string that returns every URL reachable from the seeds, de-duplicated and sorted, fetching at most workers pages concurrently. Own seen and the outstanding-work counter in a single goroutine so no mutex is needed; bound fetches with a fixed worker pool. Results must be identical for workers = 1, 2, 8, and every reachable page must be fetched exactly once.
  • tokenbucket: implement a Bucket with New(capacity) (starts full), Allow() bool (consume one token, non-blocking), and Refill(n int) (add tokens, clamped to [0, capacity]). Make it goroutine-safe and deterministic by injecting time through Refill rather than using a real clock. Under a 500-goroutine race on a 100-token bucket, exactly 100 Allow calls succeed.

Results

Exercise Tests Status
visited TestMarkSeenTableDriven, TestMarkSeenExactlyOneWinner ✅
crawl TestCrawlTableDriven, TestCrawlFetchesEachPageOnce ✅
tokenbucket TestBurstThenEmpty, TestRefillTableDriven, TestConcurrentAllowNeverOverGrants ✅