2015 FRQ Question 3

• Question 3: 2D Arrays and Methods
• FRQ 3 Reflection

Question 3: 2D Arrays and Methods

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

import java.util.ArrayList;

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

    public SparseArrayEntry(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getValue() {
        return value;
    }
}

class SparseArray {
    private ArrayList<SparseArrayEntry> entries;

    public SparseArray() {
        entries = new ArrayList<>();
    }

    public void addEntry(SparseArrayEntry entry) {
        entries.add(entry);
    }

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

public class Main {
    public static void main(String[] args) {
        SparseArray sparse = new SparseArray();

        // Adding some entries for testing
        sparse.addEntry(new SparseArrayEntry(1, 1, 100));
        sparse.addEntry(new SparseArrayEntry(1, 2, 200));
        sparse.addEntry(new SparseArrayEntry(1, 3, 300));
        sparse.addEntry(new SparseArrayEntry(2, 1, 400));

        // Testing the getValueAt method
        System.out.println("Shelf 1, Slot 1 has " + sparse.getValueAt(1, 1) + " copies of a particular book.");
        System.out.println("Shelf 1, Slot 2 has " + sparse.getValueAt(1, 2) + " copies of a different book.");
        System.out.println("Shelf 1, Slot 3 has " + sparse.getValueAt(1, 3) + " copies of another book.");
        System.out.println("Shelf 2, Slot 1 has " + sparse.getValueAt(2, 1) + " copies of a certain book.");
        System.out.println("Shelf 3, Slot 2 has " + sparse.getValueAt(3, 2) + " copies of a book.");
    }
}

Main.main(null);

Shelf 1, Slot 1 has 100 copies of a particular book.
Shelf 1, Slot 2 has 200 copies of a different book.
Shelf 1, Slot 3 has 300 copies of another book.
Shelf 2, Slot 1 has 400 copies of a certain book.
Shelf 3, Slot 2 has 0 copies of a book.

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

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

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

    public SparseArrayEntry(int row, int col, int value) {
        this.row = row;
        this.col = col;
        this.value = value;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getValue() {
        return value;
    }
}

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

    public SparseArray(int numRows, int numCols) {
        entries = new ArrayList<>();
        this.numRows = numRows;
        this.numCols = numCols;
    }

    public void addEntry(SparseArrayEntry entry) {
        entries.add(entry);
    }

    public void removeColumns(List<Integer> cols) {
        // Iterate through entries and remove entries with specified columns
        Iterator<SparseArrayEntry> iterator = entries.iterator();
        while (iterator.hasNext()) {
            SparseArrayEntry entry = iterator.next();
            if (cols.contains(entry.getCol())) {
                iterator.remove(); // Remove entry with specified column
            }
        }

        // Assume columns are removed from the end for simplicity, update numCols
        numCols -= cols.size();
    }

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

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }
}

public class Main {
    public static void main(String[] args) {
        SparseArray sparse = new SparseArray(3, 4); // Assume 4 columns originally

        // Adding some entries for testing
        sparse.addEntry(new SparseArrayEntry(1, 1, 5)); // 5 books on shelf 1, position 1
        sparse.addEntry(new SparseArrayEntry(1, 2, 8)); // 8 books on shelf 1, position 2
        sparse.addEntry(new SparseArrayEntry(2, 2, 15)); // 15 books on shelf 2, position 2
        sparse.addEntry(new SparseArrayEntry(3, 1, 7)); // 7 books on shelf 3, position 1
        sparse.addEntry(new SparseArrayEntry(3, 3, 6)); // 6 books on shelf 3, position 3

        // Remove columns 2 and 3
        List<Integer> columnsToRemove = new ArrayList<>();
        columnsToRemove.add(2);
        columnsToRemove.add(3);
        sparse.removeColumns(columnsToRemove);

        // Testing the getValueAt method
        System.out.println("Shelf 1, Position 1 has " + sparse.getValueAt(1, 1) + " books."); // Output should be 5
        System.out.println("Shelf 1, Position 2 has " + sparse.getValueAt(1, 2) + " books."); // Output should be 0
        System.out.println("Shelf 1, Position 3 has " + sparse.getValueAt(1, 3) + " books."); // Output should be 0
        System.out.println("Shelf 2, Position 1 has " + sparse.getValueAt(2, 1) + " books."); // Output should be 7
        System.out.println("Shelf 3, Position 4 has " + sparse.getValueAt(3, 4) + " books."); // Output should be 0 as it does not exist

        System.out.println("# of rows: " + sparse.getNumRows()); // Output should be 3
        System.out.println("# of columns: " + sparse.getNumCols()); // Output should be 2 after removing columns
    }
}

Main.main(null);

FRQ 3 Reflection

The task that presented a significant challenge among the four I tackled was not the concept of Sparse Arrays itself, but rather the intricacies involved in implementing the removeColumns method. Despite my familiarity with the underlying concept, I encountered unexpected index errors that proved time-consuming to resolve. Such errors, particularly in an exam setting like the AP, could be terrible to my time usage, time that would be better spent addressing another FRQ within my stronger areas of expertise. The resolution of these index errors was a long and tedious process, and through it, my understanding of array list manipulation and the implications of modifying indexes during iteration was deepened. The essence of the question was to effectively remove a column, requiring a good understanding for how entries are shifted and managed within the list. In hindsight, this experience has illuminated the importance of a thorough review of array and list operations, especially deletion and insertion, to ensure that I can approach such problems with confidence during the actual AP exam.