CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Trace one car (20 minutes)

A car at floor 3 going up has stops 6 and 9. Then floor 4 is pressed inside it. List the floors it visits and where it opens its doors.

Done when: the list shows 4 (open), 5, 6 (open), 7, 8, 9 (open).

Hint

The new stop 4 is on the way up, so it joins the sweep.

Easy 2: Run the car (20 minutes)

Type Elevator and reproduce the 14-tick run.

Done when: you print the floors with stars at 2, 5 and 8.

Hint

Print the floor after each step call.

Easy 3: Compute costs (20 minutes)

Car A is at 2 going up with stops up to 8. Car B is idle at 9. Give both costs for a call at floor 5 going up, then a call at floor 1 going up.

Done when: you write 3 and 4 for the first call, and 6 + 7 = 13 and 8 for the second.

Hint

A car that will pass the call pays only the distance.

Medium

Medium 1: Door timing (45 minutes)

Keep the door open for two ticks at each stop. Update the tests.

Done when: a car at a stop stays still for two ticks and then moves.

Hint

A small counter that counts down while the door is open works.

Medium 2: Capacity (45 minutes)

Add a load and a capacity to the car. A full car skips hall calls but still serves its own stops.

Done when: a test fills a car and shows the dispatcher giving the call to another car.

Hint

The dispatcher skips cars where the load equals the capacity.

Medium 3: Lobby return (45 minutes)

Make idle cars go to floor 0 after five idle ticks.

Done when: a test shows a car back at floor 0 and still taking new calls on the way.

Hint

Count idle ticks in Building.tick.

Hard

Hard 1: Direction-aware stops (90 minutes)

Record the direction wanted at each stop. A car going up should not stop at a floor where someone wants to go down, unless it is the last stop on the sweep.

Done when: a test with one up call and one down call at the same floor shows the right car behaviour.

Hint

Store a map from floor to the set of wanted directions.

Hard 2: Random simulation (90 minutes)

Run 4 cars, 20 floors and 500 random calls with a seeded generator. Report the average wait in ticks for the nearest dispatcher and for a round-robin dispatcher.

Done when: a table shows both averages and a sentence explains the result.

Hint

Record the tick of each call and the tick of its service.

Hard 3: Thread safety (90 minutes)

Let 8 threads press buttons while one thread ticks. Make the car safe and prove that no stop is lost.

Done when: a stress test ends with every pressed stop either served or still pending, and none missing.

Hint

Synchronize addStop and step on the same lock.