Collegeboard 2015 Practice Exam FRQ 3 • 9 min read

2D Arrays

• This FRQ showed me how to use classes and lists to handle data. It focused on working with a Sparse Array, which is good for storing data with lots of zeros or null values. I had to navigate and change a list of SparseArrayEntry objects to get values and remove columns. It showed me the importance of managing data structures with lists. Since the Sparse Array used in this FRQ was a 2D Array, the main topic of this FRQ is 2D Arrays.

Program

public class SparseArrayEntry {

    // The row index and column index for this entry in the sparse array
    private int row;
    private int col;

    // The value of this entry in the sparse array
    private int value;

    // Constructs a SparseArrayEntry object that represents a sparse array element with row index r and column index c, containing value v.
    public SparseArrayEntry(int r, int c, int v) {
        row = r;
        col = c;
        value = v;
    }

    // Returns the row index of this sparse array element.
    public int getRow() {
        return row;
    }

    // Returns the column index of this sparse array element.
    public int getCol() {
        return col;
    }

    // Returns the value of this sparse array element.
    public int getValue() {
        return value;
    }
}

public class SparseArray {

    // The number of rows and columns in the sparse array
    private int numRows;
    private int numCols;

    // The list of entries representing the non-zero elements of the sparse array. Entries are stored in the list in no particular order. Each non-zero element is represented by exactly one entry in the list.
    private List<SparseArrayEntry> entries;

    // Constructs an empty SparseArray
    public SparseArray(int rows, int cols) {
        numRows = rows;
        numCols = cols;
        entries = new ArrayList<>();
    }

    //Returns the number of rows in the sparse Array.
    public int getNumRows() {
        return numRows;
    }

    //Returns the number of columns in the sparse Array.
    public int getNumCols() {
        return numCols;
    }


    // THIS IS PART A
    public void addEntry(int row, int col, int value) {
        entries.add(new SparseArrayEntry(row, col, value));
    }

    // Returns the vale of the element at row index row and column index col in the sparse array
    // Precondition:  0 <= row < getNumRows()
    //                0 <= col < getNumCols()
    public int getValueAt(int row, int col) {
        for (SparseArrayEntry entry : entries) {
            if (entry.getRow() == row && entry.getCol() == col) {
                return entry.getValue();
            }
        }
        return 0; // Default value for missing entries
    }

    // THIS IS PART B
    public void removeColumn(int col) {
        Iterator<SparseArrayEntry> iterator = entries.iterator(); // iterator to iterate through the entries in the sparse array
        while (iterator.hasNext()) { // iterate through entries
            SparseArrayEntry entry = iterator.next();// get next entry
            if (entry.getCol() == col) { // checks if current column is the column to be removed
                iterator.remove(); // removes column
            }
        }
        numCols--; // decrease total number of columns
    }

    public static void main(String[] args) {
        SparseArray sparseArray = new SparseArray(10, 10);
        sparseArray.addEntry(5, 4, 5215);
        sparseArray.addEntry(5, 5, 123);
        sparseArray.addEntry(2, 3, 999);

        System.out.println(sparseArray.getValueAt(5, 4)); // prints 1
        System.out.println(sparseArray.getValueAt(5, 5)); // prints 123
        System.out.println(sparseArray.getValueAt(2, 3)); // prints 9
        System.out.println(sparseArray.getValueAt(4, 1)); // prints 0

        sparseArray.removeColumn(4); // removes column 4

        System.out.println(sparseArray.getValueAt(5, 4)); // prints 0 because column 4 is removed
    }
}

SparseArray.main(null);

5215
123
999
0
0