Sparse Array Entry Solution

The SparseArrayEntry free response question on the 2015 AP Computer Science exam has you working with an ArrayList of an arbitrary class called SparseArrayEntry.

Talking to students that took the AP exam this year I think the most confusing part of this question is that the list of entries acted like a matrix, so several wanted to write a solution using nested loops like they were iterating through a matrix. But it was just a 1-d list of objects.

The SparseArrayEntry class has instance variables for row, column and value; getters / accessor methods (only) for these 3 values; and a constructor where you can create a new reference by passing all 3 values. We’ll come back to there only being accessor methods in part B.

Part A

For the first part students had to go through the list looking for an entry with a specific row and column value. This is where some of my students got confused and used a nested loop instead of going through the list.

At each entry we’re going to compare the row and column of the SparseArrayEntry reference with the row and column we’re looking for. If we find a match, we return the value.

If we get all the way through entries without finding a match, we return 0. This is part of the problem description. entries does represent a 2-d array, but any missing elements have a value of 0.

public int getValueAt(int row, int col) {
    for (SparseArrayEntry sae: entries) {
        if (sae.getRow() == row && sae.getCol()==col) {
            return sae.getValue(); 
        }
    }
    return 0; 
}

Part B

The second part has you writing code to remove a column from the pseudo grid.

There’s two parts to this. The first you need to actually remove any references to entries that are on the column to remove. That was the easy part for most students as we had done this dozens of times in labs.

The second part was a little more confusing. Since you’re removing a column, any entry that’s in a higher column needs to have its column decremented. Problem is, there aren’t any modifier methods in a SparseArrayEntry. So instead we have to create a new entry using the values from the current occupant and the overwrite that position.

And the last part was the one that I’d guess 75% of my students probably didn’t do. Since the removeColumn method removed a column the numCols instance variable also had to decrement by one.

public void removeColumn(int col) {
    for (int i=entries.size() - 1; i>=0; i--) {
        SparseArrayEntry sae = entries.get(i);
        if (sae.getCol() == col) {
            entries.remove(i);
        }
        else if (sae.getCol() > col) {
            entries.set(i, new SparseArrayEntry(sae.getRow(), sae.getCol() - 1, sae.getValue()));
        }
    }
    numCols--;
}
This site contains affiliate links. If you click an affiliate link and make a purchase we may get a small commission. It doesn't affect the price you pay, but it is something we must disclose.