SparseArray free response answer 10

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.

10 thoughts on “SparseArray free response answer

  1. Reply Amar Shah May 9,2015 9:48 pm

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

  2. Reply Lebron May 10,2015 9:56 am

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

    • Reply Brandon Horn May 10,2015 11:22 am

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

  3. Reply Anon1 May 10,2015 10:27 am

    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?

    • Reply Brandon Horn May 10,2015 11:27 am

      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. Reply Jack Levin Jan 11,2016 5:50 pm

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

Leave a Reply