SparseArray free response problem from the 2015 AP Computer Science A Exam.

SparseArray is #3 from the from the 2015 AP Computer Science A Free Response problems.

https://secure-media.collegeboard.org/digitalServices/pdf/ap/ap15_frq_computer_science_a.pdf

## Part (a) – getValueAt method

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

return 0;
}
```

Since the elements in entries are unordered the only solution is to traverse the entire list.

## Part (b) – removeColumn method

```public void removeColumn(int col)
{
for(int i = entries.size() - 1; i >= 0; i--)
{
SparseArrayEntry entry = entries.get(i);

if(entry.getCol() == col)
entries.remove(i);
else if(entry.getCol() > col)
entries.set(i, new SparseArrayEntry(
entry.getRow(), entry.getCol() - 1, entry.getValue()));
}

numCols--;
}
```

Removing a column can be accomplished with a single traversal of entries. SparseArrayEntry objects are immutable so new objects must be created for the entries with column values greater than col.

## 12 thoughts on “SparseArray free response answer”

1. Amar Shah

Shouldn’t the method return without doing anything if numCols is zero?

• Brandon Horn

I assume you’re referring to `removeColumn`. The precondition for that method was `0 <= col < getNumCols()` which prohibits `numCols` from being 0.

• Dilan

the method is void

• Brandon Horn

A void method can still contain a `return;` statement. The statement would just end the method.

2. Lebron

Actually if 0 is <= col, col can be 0. See, 0 is less than or EQUAL TO col.

• Brandon Horn

The second part of the precondition states that `numCols` must be strictly greater than `col`. `col` can be 0 but `numCols` can’t.

3. Anon1

For part b, instead of looping backwards like you, I looped forward but then I did i– when I deleted an item whose column equaled col. In addition, instead of setting a new item in entires, I inserted a new one at position I, then deleted the old version that was moved to position i+1. Would this still work?

• Brandon Horn

Looping forward and decrementing `i` on removal is fine. You could also have used a `while` loop and incremented `i` only when you didn’t remove an element.

Adding a new element then removing the shifted one is silly but I can’t think of a situation in which it wouldn’t work. I don’t have the scoring guide so I don’t know if that would be penalized but I doubt it.

4. Jack Levin

Does it matter whether you finish the code with `--numCols` or `numCols--`

• Brandon Horn

No. If the code is on its own line both operations are equivalent.

5. Person

Can you use a “for each” loop for part b?
Thank you!

• Brandon Horn

No. You can’t structurally modify (add to or remove from) the list that you’re looping through with a for each loop.