Seating Chart Solution

It’s almost 100% that at least one free response question on the AP computer science exam will have you working with an array of some arbitrary object. In 2014 the SeatingChart problem had you do just that.

Student Class

You are given an arbitrary class called Student that has no implemented methods. It looks like this.

public class Student {
	
	/** Returns the name of this Student */
	public String getName() {
		// implementation not shown
	}
	
	/** Returns the number of times this Student has missed class */
	public int getAbsenceCount() {
		// implementation not shown
	}
	
	// There may be instance variables, constructors, and
	// methods that are not shown
	
}

A couple of things that we need to unpack here.

First, they’re giving you a class that you likely have not worked with before. You’re not expected to have done any labs with this Student class. You’re being tested on whether you understand how classes work.

Second, there are two methods; getName and getAbsenceCount; in this class. Both are shown as implementation not shown, which means that we don’t have to care how they work. But since the test writer spent the time to put the methods in Student, you can be sure that you’ll call them somewhere.

Seating Chart

Both parts A and B have you working with a class called SeatingChart which contains a 2 dimensional array of Student references. The shell looks like this.

public class SeatingChart {
	
	private Student[][] seats; 
	
	// Part A
	public SeatingChart( List<Student> studentList, int rows, int cols ) {
		
	}
	
	// Part B
	public int removeAbsentStudents( int allowedAbsences ) {
		
	}
}

We’ll be filling in parts A and B below.

Part A

For the first part you’re given the shell of a constructor with instructions on how to implement. Note that you’re given a List of type Student called studentList that you’re going to use to fill in the matrix seats.

The most common issue I see when we do this FRQ in class is students keeping track of where they are in both studentList and in the matrix seats. For this we’re going to use an int variable, idx in the example code below.

// Part A
public SeatingChart( List<Student> studentList, int rows, int cols ) {
	seats = new Student[rows][cols];
	int idx = 0; 
	
	for (int c = 0; c < cols; c++) {
		for (int r = 0; r < rows; r++) {
			if (idx < studentList.size()) {
				seats[r][c] = studentList.get(idx); 
				idx++; 
			}
		}
	}
}

Notice that the first line instantiates seatingChart to the correct size. We have to do this. Otherwise seatingChart would be null.

The second line creates the idx variable that I mentioned above. It’s going to be used to keep track of where we are in studentList.

The nested loops may look backwards since you’re probably used to looping through the rows and then the columns. But the problem states that we should fill each column before moving on to the next, which means we have to flip the loops around.

Before putting a Student in the list I check to make sure that (idx < studentList.size(). This isn’t strictly necessary since the preconditions state that rows * cols >= studentList.size(), but I think it’s a good habit to check things like that.

I then use idx to pull a Student out of studentList and put that reference into seats.

Part B

For the second part you are to go through seats and remove any student that has more than allowedAbsences from the seating chart. To remove we set that position to null.

You also have to keep count of how many students are removed and return that value.

// Part B
public int removeAbsentStudents( int allowedAbsences ) {
	int cnt = 0;
	
	for (int r=0; r<seats.length; r++) {
		for (int c=0; c<seats[r].length; c++) {
			if (seats[r][c] != null && seats[r][c].getAbsenceCount() > allowedAbsences) {
				seats[r][c] = null;
				cnt++; 
			}
		}
	}
	
	return cnt;
}

First line creates a variable named cnt that we’ll use to keep track of removals. That value is returned at the end.

Then we loop through the matrix. This time I looped through rows first because that’s what I’m used to. It would work just as well if you looped through columns in the outer loop and rows in the inner loop.

For each element in seats we first check to make sure it’s not null. If it is, we couldn’t call the getAbsenceCount method as that would result in a NullPointerException. If it is null the if statement will short circuit and never call getAbsenceCount().

If the element at seats[r][c] is both non-null and the absence count is too high we’ll set that position to null to remove it from the matrix and increment cnt to keep track of how many we’ve removed.

Thoughts

As a teacher, I like this problem a lot. It covers a good chunk of the AP Java topic list and is a good indicator of how well a student learned the content through the course of the year.

Students needed to understand quite a few separate topics on this problem. For those that understood how to iterate through both Lists and matricies and work with arbitrary classes this should have been a relatively straight forward problem. For students that were missing any of those pieces, it was likely a very difficult problem.

And I also noticed reading back through this post that the getName method in Student was never actually used. Guess the best thing I can say there is that it’s odd.

Leave a Reply

Your email address will not be published. Required fields are marked *