CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 6 of 6 · 2 min read

Exercises

Easy

Easy 1: Find the race (20 minutes)

Read this code and name its race: if (!map.containsKey(k)) map.put(k, v); on a ConcurrentHashMap used by many threads.

Done when: you name check-then-act and give the one-call fix.

Hint

putIfAbsent does both steps at once.

Easy 2: Run the counters (20 minutes)

Type the three counters and run four threads of 100000 increments. Print each total.

Done when: the locked and atomic totals are 400000, and the plain total is lower.

Hint

Start all threads on a latch so they overlap.

Easy 3: Match the tool (20 minutes)

Choose lock, atomic, volatile or immutable for: a stop flag, a hit counter, a seat set with an invariant, a config object shared by all threads.

Done when: four answers each have a one-line reason.

Hint

A flag needs visibility, a counter needs atomicity.

Medium

Medium 1: Seat map (45 minutes)

Type SeatMap. Run eight threads calling reserve(7) and count the winners. Then break it by splitting check and add into two separate calls with a yield between them, and show a double win.

Done when: the safe version always gives one winner, and the broken one gives two at least once in 200 runs.

Hint

A CountDownLatch releases all threads together.

Medium 2: Safe counter map (45 minutes)

Count words from four threads into a ConcurrentHashMap<String,Integer>. First use get then put, then use merge. Compare totals.

Done when: the merge version is always correct and the first loses counts.

Hint

m.merge(word, 1, Integer::sum).

Medium 3: Stop flag (45 minutes)

Write the stop-thread example with a plain boolean, then with volatile. Explain what you observe on your machine.

Done when: the volatile version always stops, and a note says the plain one may not.

Hint

Use a loop that counts, so it does not end for other reasons.

Hard

Hard 1: Transfer without deadlock (90 minutes)

Write transfer with naive lock order and show a deadlock with a timeout. Fix it by ordering on account id. Add a total-balance check.

Done when: the naive version hangs in a test with a timeout, the fixed one finishes, and the total stays 2000.

Hint

Use Thread.join(timeout) to detect a hang.

Hard 2: Thread-safe parking lot (90 minutes)

Write a ParkingLot with park(plate) and leave(plate) that never gives two cars the same slot. Choose a locking design and document the policy.

Done when: 50 threads parking into 10 slots give exactly 10 successes, and a comment names the lock.

Hint

One lock around the whole slot table is simplest.

Hard 3: Pair of fields (90 minutes)

Make a Range class with lower and upper and the invariant that lower is at most upper. Show that two atomic fields are unsafe, then fix it with one lock.

Done when: a test shows a broken invariant before and none after.

Hint

The invariant spans two fields, so one lock must cover both.