SparseArrayEntry Solution

The SparseArrayEntry free response question on the 2015 AP Computer Science exam has you working with an ArrayListof 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 SparseArrayEntryclass 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 SparseArrayEntryreference 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 entrieswithout finding a match, we return 0. This is part of the problem description. entriesdoes 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 removeColumnmethod removed a column the numColsinstance 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--;
}

Leave a Reply

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