CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Split by hand (20 minutes)

Split 100.00 equally among 7 people, in cents. Give the shares and check the sum.

Done when: four people have 1429, three have 1428, and the sum is 10000.

Hint

10000 divided by 7 is 1428 with remainder 4, so four people get one extra cent.

Easy 2: Run the ledger (20 minutes)

Type the code and reproduce the first three rows of the run table.

Done when: you print 6666, -3333, -3333, 0, then 4666, 667, -5333, 0, then the two payments.

Hint

Print the map after each expense.

Easy 3: Balance check (20 minutes)

Alice paid 90 for Alice, Bob and Cara equally. Bob paid 30 for Bob and Cara equally. Give the net balance of each.

Done when: the balances are Alice +60, Bob -15 and Cara -45 in whole units, summing to zero.

Hint

Alice +90 - 30 = +60. Bob -30 + 30 - 15 = -15. Cara -30 - 15 = -45.

Medium

Medium 1: Share-based split (45 minutes)

Add a ByShares rule where each person has a number of shares, such as 2, 1 and 1. Handle leftover cents.

Done when: a test splits 100.00 as 2, 1, 1 into 50.00, 25.00 and 25.00, and another test with an odd cent adds up.

Hint

Total times own shares divided by all shares, then hand out the leftover.

Medium 2: Expense history (45 minutes)

Keep a list of expense records. Add delete(id) that rebuilds the balances from the list.

Done when: after deleting an expense the balances equal those of a ledger that never had it.

Hint

Store each expense with its split result.

Medium 3: Pairwise view (45 minutes)

Add a method that shows, for two people, how much one owes the other from direct expenses only.

Done when: a test with three expenses gives the right figure for each pair.

Hint

Add up only expenses where one of the two paid and the other shared.

Hard

Hard 1: Random balance test (90 minutes)

Generate 10,000 random expenses with all three rules and a seeded generator. After each, check that the sum of balances is zero.

Done when: the test passes, and a deliberately broken split rule is caught by the ledger's check.

Hint

new Random(42) gives repeatable data.

Hard 2: Fewer payments (90 minutes)

For small groups, find the minimum number of payments by trying subsets of people whose balances sum to zero. Compare with the greedy answer.

Done when: a table shows the two counts for ten random groups, and a case where greedy uses more payments is found or shown to be rare.

Hint

A group of people whose balances sum to zero needs one fewer payment than its size.

Hard 3: Thread safety (90 minutes)

Run 8 threads adding expenses and settlements at once. Make the ledger safe.

Done when: the final sum is zero, and an unsynchronized version fails the same test at least once.

Hint

One lock around each public method is enough.