SparseArray free response answer 12

9 May 2015   | 2015 AP Computer Science Exam Answers

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 May 9,2015 9:48 pm

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

    • Brandon Horn May 10,2015 8:19 am

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

    • Dilan Apr 10,2017 12:09 am

      the method is void

      • Brandon Horn May 4,2017 7:32 pm

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

  2. 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.

    • 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. 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?

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

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

  5. Person Mar 21,2018 6:05 pm

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

    • Brandon Horn Mar 25,2018 9:56 pm

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

Comments are closed.