Two dimensional arrays are tested on the AP Computer Science A Exam, often with a free response question. You will probably be required to loop through the entire data structure in a specified order. You might be required to loop through part of the data structure, which is more complex. This problem is intended as practice with both simple and moderately complex traversals.

Please don’t use this problem to practice your timing for the AP CS A Free Response section. Use only actual released AP CS FR for timing practice. The approach for this problem is identical to a real AP CS FR.

Problem description

An airline flight reservation system stores information about reservations for each seat on a flight. The Reservation class stores the name of the passenger and whether the passenger is a frequent flyer. The declaration of the Reservation class is shown below.

public class Reservation
{
    /**
     * Constructs a reservation for a passenger
     * @param passengerName the passenger's name
     */
    public Reservation(String passengerName)
    { /* implementation not shown */ }

    /**
     * Returns the name of the passenger associated with the reservation
     * @return the passenger's name
     */
    public String passengerName()
    { /* implementation not shown */ }

    /**
     * Returns whether the passenger associated with the reservation is a frequent flyer
     * @return true if the passenger is a frequent flyer, false otherwise
     */
    public boolean isFrequentFlyer()
    { /* implementation not shown */ }

    // There may be instance variables, constructors, and methods that are not shown.
}

The Flight class stores all reservations for a flight. The declaration of the Flight class is shown below. You will write several methods of the Flight class.

public class Flight
{
    // A two-dimensional array of reservations with empty seats represented by null,
    // instantiated in the constructor
    private Reservation[][] seats;

    // The number of rows of seats, set by the constructor; guaranteed to be >= 1
    private int rows;

    // The number of seats per row, set by the constructor; guaranteed to be >= 3
    private int seatsPerRow;

    /**
     * Determines the name of each frequent flyer with a reservation
     * @return a list of the names of the frequent flyers with reservations
     */
    public ArrayList<String> frequentFlyers()
    {
        /* to be implemented in part (a) */
    }

    /**
     * Reserves adjacent seats and returns true if possible; otherwise,
     * does not make reservations and returns false.
     * @param passOneName the name of a passenger seeking a reservation
     * @param passTwoName the name of a passenger seeking a reservation
     * @return true if adjacent seats were reserved, false if no adjacent seats are available
     */
    public boolean reserveAdjacentSeats(String passOneName, String passTwoName)
    {
        /* to be implemented in part (b) */
    }

    /**
     * Reserves a window seat and returns true if possible; otherwise,
     * does not make a reservation and returns false
     * @param passengerName the name of a passenger seeking a reservation
     * @return true if a window seat was reserved, false if no window seat is available */
    public boolean reserveWindowSeat(String passengerName)
    {
        /* to be implemented in part (c) */
    }

    /** 
     * Determines the name of each passenger without an adjacent reservation.
     * @return a list of the names of all passengers without adjacent reservations
     */
    public ArrayList<String> isolatedPassengers()
    {
        /* to be implemented in part (d) */
    }

    // There may be instance variables, constructors, and methods that are not shown.
}

Part (a) frequentFlyers method

The frequentFlyers method returns a list containing the names of all passengers with reservations who are frequent flyers. The names in the returned list may appear in any order. If there are no passengers with reservations who are frequent flyers, the method returns an empty list.

Complete method frequentFlyers.

/**
 * Determines the name of each frequent flyer with a reservation
 * @return a list of the names of the frequent flyers with reservations
 */
public ArrayList<String> frequentFlyers()

Part (b) reserveAdjacentSeats method

Two seats are adjacent if they are in the same row and have consecutive column numbers. Recall that empty seats are represented by null.

The reserveAdjacentSeats method attempts to reserve adjacent seats for the 2 passengers whose names are taken as parameters.

If at least 1 pair of empty adjacent seats exists, the method reserves a pair of empty adjacent seats and returns true. If 2 or more pairs of empty adjacent seats exist, the method may reserve any 1 such pair. If no pair of empty adjacent seats exists, the method does not make any reservations and returns false. reserveAdjacentSeats does not modify existing reservations.

Complete method reserveAdjacentSeats.

/**
 * Reserves adjacent seats and returns true if possible; otherwise,
 * does not make reservations and returns false.
 * @param passOneName the name of a passenger seeking a reservation
 * @param passTwoName the name of a passenger seeking a reservation
 * @return true if adjacent seats were reserved, false if no adjacent seats are available
 */
public boolean reserveAdjacentSeats(String passOneName, String passTwoName)

Part (c) reserveWindowSeat method

A seat is a window seat if it is the first or last seat in any row. Recall that empty seats are represented by null.

The reserveWindowSeat method attempts to reserve a window seat for the passenger whose name is taken as a parameter.

If at least 1 empty window seat exists, the method reserves a windows seat and returns true. If 2 or more empty window seats exist, the method may reserve any 1 such seat. If no empty window seat exists, the method does not make any reservation and returns false. reserveWindowSeat does not modify existing reservations.

Complete method reserveWindowSeat.

/**
 * Reserves a window seat and returns true if possible; otherwise,
 * does not make a reservation and returns false
 * @param passengerName the name of a passenger seeking a reservation
 * @return true if a window seat was reserved, false if no window seat is available */
public boolean reserveWindowSeat(String passengerName)

Part (d) isolatedPassengers method

Two seats are adjacent if they are in the same row and have consecutive column numbers. Recall that empty seats are represented by null.

The isolatedPassengers method returns a list of the names of all passengers with no adjacent reservations. A passenger has no adjacent reservations if each seat adjacent to the passenger’s seat is empty. The names in the returned list may appear in any order. If there are no passengers with no adjacent reservations, the method returns an empty list.

Complete method isolatedPassengers.

/** 
 * Determines the name of each passenger without an adjacent reservation.
 * @return a list of the names of all passengers without adjacent reservations
 */
public ArrayList<String> isolatedPassengers()

Solution & comments

See the Flight solution or review it with AP CS Tutor Brandon Horn.

Comment on Flight free response

Additional 2D array resources