2015 FRQ Question 3 • 10 min read

Question 3

A two-dimensional array of integers in which most elements are zero is called a sparse array. Because most elements have a value of zero, memory can be saved by storing only the non-zero values along with their row and column indexes. The following complete SparseArrayEntry class is used to represent non-zero elements in a sparse array. A SparseArrayEntry object cannot be modified after it has been constructed.

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

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

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

    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 void setCol(int col) {
        this.col = col;
    }

    public int getValue() {
        return value;
    }; 
}

public class SparseArray {
    private int numRows;
    private int numCols; 
    private List<SparseArrayEntry> entries; 
    
    public SparseArray() {
        entries = new ArrayList<SparseArrayEntry>(); 
    }
    
    public void add(SparseArrayEntry entry) {
        entries.add(entry);
    }
    
    public int getNumRows() {
        return numRows;
    }
    
    public int getNumCols() {
        return numCols;
    }

    public int getValueAt(int row, int col) {
        for (SparseArrayEntry x : entries) {
            if (x.getCol() == col) {
                if (x.getRow() == row) {
                    return x.getValue();
                }
            }
        }
        return 0;
    }
    public void removeColumn(int col) {
        for (int i = 0; i < entries.size(); i++) {
            SparseArrayEntry entry = entries.get(i);
            int cols = entry.getCol();
            if (cols == col) {
                entries.remove(i);
                i--;
            } else if (cols > col) {
                entry.setCol(cols - 1);
            }
        }
    }

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

        sparseArray.add(new SparseArrayEntry(2, 0, 1));
        sparseArray.add(new SparseArrayEntry(1, 1, 5));
        sparseArray.add(new SparseArrayEntry(1, 4, 4));
        sparseArray.add(new SparseArrayEntry(3, 1, -9));
        
        for (SparseArrayEntry entry : sparseArray.entries) {
            System.out.println("Row: " + entry.getRow() + ", Column: " + entry.getCol() + ", Value: " + entry.getValue());
        }
        System.out.println();
        System.out.println("Value at row 3 and column 1: " + sparseArray.getValueAt(3, 1));
        sparseArray.removeColumn(1);
        System.out.println();
        for (SparseArrayEntry entry : sparseArray.entries) {
            System.out.println("Row: " + entry.getRow() + ", Column: " + entry.getCol() + ", Value: " + entry.getValue());
        }
    }
}
SparseArray.main(null);

Row: 2, Column: 0, Value: 1
Row: 1, Column: 1, Value: 5
Row: 1, Column: 4, Value: 4
Row: 3, Column: 1, Value: -9

Value at row 3 and column 1: -9

Row: 2, Column: 0, Value: 1
Row: 1, Column: 3, Value: 4

Reflection

This FRQ was focused on 2D Arrays, specifically sparse arrays. This FRQ was much more difficult, and I also partly struggled on the different methods with the getters and setters. The first part was fairly simple, but the second part took a lot of my time. A lot of the struggles came with me creating a new setter for the columns and not changing the iteration properly. I forgot to do the i-- which caused my code to improperly reform the remaining columns when one was deleted. Overall, this FRQ is definitely a point of study and I should do more practice with problems like these.