Hotel: 2005 FRQ 1

Booking a hotel room sounds like a front-desk problem, but underneath it's a search through a plain array plus some first-come-first-served bookkeeping — that's what this AP Computer Science A free-response question actually asks you to write.

What This FRQ Tests

• AP CSA units: Unit 6 (Array) and Unit 7 (ArrayList)
• Core skill: searching an array of objects for the first empty (null) slot
• Secondary skill: keeping a first-come-first-served waiting list by adding to the end and removing from the front of an ArrayList
• Official category: content-wise this is squarely an "Array/ArrayList" question, even though it's printed as FRQ 1 on the 2005 exam. The now-standard ordering — FRQ 1 is always Methods/Control Structures, FRQ 2 is Classes, FRQ 3 is Array/ArrayList, FRQ 4 is 2D Array — wasn't formalized until the 2019-2020 Course and Exam Description redesign, so a 2005 question's printed number doesn't reliably predict its category the way a modern one does.

The Setup

• The given Reservation class (not to be modified) provides:
  • Reservation(String guestName, int roomNumber) — a constructor
  • int getRoomNumber() — a getter for the room number
• The Hotel class has two fields:
  • private Reservation[] rooms — index i corresponds to room i; a null entry means that room is empty
  • private ArrayList waitList — guest names waiting for a room, in the order they asked (declared without a generic type parameter, exactly as the original 2005 question wrote it)
• You're asked to write two methods:
  • requestRoom(String guestName) — find an empty room, or add the guest to the wait list
  • cancelAndReassign(Reservation res) — free up a room, reassigning it to whoever is next in line

Part (a): Writing requestRoom(String guestName)

The Rule, Broken Down

1. Look for any room that's currently empty (rooms[i] == null).
2. If one exists, create a new Reservation for guestName in that room and return it.
3. If every room is already taken, add guestName to the end of waitList instead, and return null.

Step-by-Step Approach

1. Loop over every index of rooms.
2. The moment you find a null entry, that room number is available — create a Reservation for guestName there, store it, and return it immediately.
3. If the loop finishes without ever returning, there were no empty rooms — add guestName to waitList and return null.

The Code

public Reservation requestRoom(String guestName)
{
    for (int i = 0; i < rooms.length; i++)
    {
        if (rooms[i] == null)
        {
            rooms[i] = new Reservation(guestName, i);
            return rooms[i];
        }
    }

    waitList.add(guestName);
    return null;
}

Why Each Piece Matters

• rooms[i] == null — checks for an empty room using ==, which is correct here since we're testing whether the reference itself is absent, not comparing two objects' contents.
• new Reservation(guestName, i) — the room number passed in is the loop index i itself, which is exactly what makes rooms[index].getRoomNumber() return index, as the class comment promises.
• Returning immediately inside the loop — this stops the search the instant a room is found, so later rooms are never touched and the guest never accidentally gets added to the wait list too.
• waitList.add(guestName) only runs if the loop never found an empty room — add(E obj) appends to the end of the list, which is what "add the guest to the end of waitList" requires.

Tracing the Example

The released question doesn't include a numeric example for this method, so here's a small self-built one to confirm the logic: a 3-room hotel, rooms = [null, null, null], waitList empty.

Each guest lands in the lowest-numbered empty room, and once the hotel is full, the next guest goes straight to the wait list instead.

Common Mistakes to Avoid

• Not returning immediately after filling a room. Without the early return, the loop keeps running and could overwrite a later room too.
• Adding to waitList unconditionally, instead of only after the loop confirms no empty room exists.
• Mismatching the room number and the array index — since rooms[i] is always room i by construction, the constructor call must use i, not some other computed value.

Part (b): Writing cancelAndReassign(Reservation res)

The Rule, Broken Down

1. The room being released is res.getRoomNumber().
2. If anyone is on waitList, take the first name off the list and give that person a brand-new Reservation in the just-vacated room.
3. If nobody is waiting, simply mark that room as empty (null) and return null.

Step-by-Step Approach

1. Get the room number to free up: res.getRoomNumber().
2. Check whether waitList has anyone in it.
3. If it does, remove the first name (index 0), create a Reservation for that person in the freed room, store it, and return it.
4. If it doesn't, set that room's slot in rooms back to null and return null.

The Code

public Reservation cancelAndReassign(Reservation res)
{
    int roomNum = res.getRoomNumber();

    if (waitList.size() > 0)
    {
        String nextGuest = (String) waitList.remove(0);
        rooms[roomNum] = new Reservation(nextGuest, roomNum);
        return rooms[roomNum];
    }
    else
    {
        rooms[roomNum] = null;
        return null;
    }
}

Why Each Piece Matters

• res.getRoomNumber() — uses the accessible method already given on Reservation rather than searching rooms for a matching reference; the precondition guarantees res is valid, so no extra checking is needed.
• waitList.remove(0) — removes and returns the first name, which is exactly the first-come-first-served behavior the wait list needs. Because waitList was declared as a plain ArrayList with no generic type parameter (as given in the original class), remove(int index) returns a plain Object, so it has to be cast to String before it can be used as one.
• Reassigning to roomNum, the same room that was released — the newly waiting guest takes over the exact room res used to occupy, never a different one.
• rooms[roomNum] = null in the else branch — this is what actually marks the room empty when nobody was waiting; skipping it would leave the old, now-cancelled Reservation sitting in the array as if it were still valid.

Tracing the Example

Again, the question gives no worked numeric trace for this method, so continuing the scenario built above — rooms = [Alice-0, Bob-1, Carol-2], waitList = ["Dan"]:

The first call hands room 0 straight to Dan and empties the wait list; the second call has nobody left to reassign, so room 1 just goes back to being empty.

Common Mistakes to Avoid

• Forgetting to actually remove the name from waitList. Using get(0) instead of remove(0) would leave "Dan" in the list forever, so the next cancellation would reassign him again.
• Not casting the result of waitList.remove(0). Since waitList isn't declared with a generic type here, remove returns Object — assigning it directly to a String variable without (String) won't compile.
• Leaving rooms[roomNum] untouched when waitList is empty. Without explicitly setting it to null, the array would still hold a reference to the cancelled Reservation, and the room would incorrectly appear occupied.

Key Takeaways

• When an array's index is the meaningful identifier (a room number, here), finding an available slot is just a search for null — no separate lookup table is needed.
• A first-come-first-served queue maps directly onto ArrayList: add new entries at the end (add), always serve from the front (remove(0)).
• A field declared as a raw ArrayList (no generic type) returns plain Object from methods like get and remove — remember the explicit cast before treating the result as anything more specific.