2015 FRQ Practice Exam Question Three • 14 min read

Question 3

copied below

(a) Write the SparseArray method getValueAt. The method returns the value of the sparse array element at a given row and column in the sparse array. If the list entries contains an entry with the specified row and column, the value associated with the entry is returned. If there is no entry in entries corresponding to the specified row and column, 0 is returned. In the example above, the call sparse.getValueAt(3, 1) would return -9, and sparse.getValueAt(3, 3) would return 0.

(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray: All entries in the list entries with column indexes matching col are removed from the list. All entries in the list entries with column indexes greater than col are replaced by entries with column indexes that are decremented by one (moved one column to the left). The number of columns in the sparse array is adjusted to reflect the column removed.

Type of FRQ

This feels like a combination Classes and ArrayList problem. It includes understanding parts of a class, including constructor methods. The SparseArrayEntries are also objects, which opens up many more concepts, such as adding and removing. However, the main focus of the problem is learning how to handle arrays, especially when adding or removing elements to them.

import java.util.ArrayList;
import java.util.List;


public class SparseArrayEntry {
    private int row;
    private int col;
    private int value;


    // all methods below given by the problem
    public SparseArrayEntry(int r, int c, int v) {
        row = r;
        col = c;
        value = v;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getValue() {
        return value;
    }
}

public class SparseArray {
    private int numRows;
    private int numCols;
    private List<SparseArrayEntry> entries;

    // start of my work:

    public SparseArray(int numRows, int numCols) {
        this.numRows = numRows; // finds number of rows and columns for iteration purposes.
        this.numCols = numCols;
        entries = new ArrayList<>(); // new list for the array when removing a column (part b)
    }

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    public int getValueAt(int row, int col) {
        // part a
        int output = 0; // output is 0 by default, since most values in a Sparse array are 0

        for (SparseArrayEntry i : entries) {
            if (i.getRow() == row && i.getCol() == col) {
                output = i.getValue(); // if a value object is found, the output is no longer 0
                break;  
            }
        }
        return output;
    }

    public void removeColumn(int col) {
        List<SparseArrayEntry> newArray = new ArrayList<>(); // creating a new array without a column

        for (SparseArrayEntry i : entries) {
            if (i.getCol() != col) { // any entries that are not in the removed column are added to the new one
                newArray.add(i);
            }
        }

        entries = newArray;
        numCols--; // to account for removed column (BE SURE TO REMEMBER THIS IN FUTURE FRQs)
    }


    public static void main(String[] args) {
        SparseArray sparseArray = new SparseArray(3, 4);

        SparseArrayEntry entry1 = new SparseArrayEntry(1, 4, 4);
        SparseArrayEntry entry2 = new SparseArrayEntry(2, 0, 1);
        SparseArrayEntry entry3 = new SparseArrayEntry(3, 1, -9);
        SparseArrayEntry entry4 = new SparseArrayEntry(1, 1, 5);

        sparseArray.entries.add(entry1);
        sparseArray.entries.add(entry2);
        sparseArray.entries.add(entry3);
        sparseArray.entries.add(entry4);
        
        int getValue1 = sparseArray.getValueAt(3, 1);
        int getValue2 = sparseArray.getValueAt(3, 3);

        System.out.println("Part A:");
        System.out.println("Value at (3,1): " + getValue1);
        System.out.println("Value at (3,3): " + getValue2);

        System.out.println("Part B:");
        int getValueBefore = sparseArray.getValueAt(1, 4);
        sparseArray.removeColumn(1);
        int getValueAfter = sparseArray.getValueAt(1, 3);
        System.out.println("Before: " + getValueBefore);
        System.out.println("After: " + getValueAfter);

        
    }
}

SparseArray.main(null)

Part A:
Value at (3,1): -9
Value at (3,3): 0
Part B:
Before: 4
After: 0

How I solved each problem:

a) For this problem, I started by setting the default value displayed to be 0, since most values in the SparseArray are 0. Then, if the parameters for the method called matched the row and column of one of the entry objects, I had the output change to match the value of that entry. This part was pretty straightforward, and after thinking it through, I figured out what needed to be done within a reasonable time.

b) This part was a lot more difficult for me. I began by trying to figure out a way to actually remove a column from the array. However, since the array does not actually exist, I was stuck on what to do. By asking some peers, I found out many of them were using an entirely new array to simulate removing a column. I was able to replicate their method. However, another thing I had trouble with was remembering to adjust the index numbers for the other columns after one had been removed, which was definitely something we were taught in one of the student lessons.

Reflection

I had a lot of trouble with this problem – especially part B, since the array did not actually exist. This made it hard for me since I was attempting to use methods I would use for a normal array. By making the SparseArray be an interface, the problem required me to understand how the simulated array actually worked, instead of being able to copy the same code from other questions in this FRQ to find, add, and remove elements.