2015 Practice FRQ Question 3 • 17 min read

Description

Analysis and breakdown of Question 3 from the 2015 AP Exam

Question 3: 2D ARRAYS

image image

Question breakdown and approach:

This question involves implementing two methods for a SparseArray class, which represents a sparse array using a list of SparseArrayEntry objects. The SparseArrayEntry class represents non-zero elements in the sparse array with their row and column indexes. The methods to be implemented are as follows: (a) Write the getValueAt method in the SparseArray class, which returns the value of the sparse array element at a given row and column. If an entry with the specified row and column exists in the list of entries, the method returns the associated value. Otherwise, it returns 0. (b) Write the removeColumn method in the SparseArray class, which removes a specified column from the sparse array. The method should remove all entries in the list with column indexes matching the specified column, adjust the column indexes greater than the specified column, and update the number of columns in the sparse array. Approach: (a) For getValueAt, iterate through the list of entries and check if there is an entry with the specified row and column. Return the associated value if found, otherwise return 0. (b) For removeColumn, iterate through the list of entries and remove entries with the specified column. Adjust the column indexes greater than the specified column by decrementing them. Update the number of columns in the sparse array.

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. In the example above, the call sparse.getValueAt(3, 1) would return -9, and sparse.getValueAt(3, 3) would return 0.

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);
    }
     
    // FRQ method part a, asking for getValueAt
    public int getValueAt(int row, int col) {
        for (SparseArrayEntry e : entries) {
            if (e.getRow() == row && e.getCol() == col) {
                return e.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, 5));
        sparse.addEntry(new SparseArrayEntry(2, 2, -3));
        sparse.addEntry(new SparseArrayEntry(3, 1, -9));

        // Testing the getValueAt method
        System.out.println("Value at (1, 1): " + sparse.getValueAt(1, 1)); // Output: 5
        System.out.println("Value at (2, 2): " + sparse.getValueAt(2, 2)); // Output: -3
        System.out.println("Value at (3, 1): " + sparse.getValueAt(3, 1)); // Output: -9
        System.out.println("Value at (3, 3): " + sparse.getValueAt(3, 3)); // Output: 0
    }
}

Main.main(null);

Value at (1, 1): 5
Value at (2, 2): -3
Value at (3, 1): -9
Value at (3, 3): 0

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.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 List<SparseArrayEntry> entries;
    private int numRows;
    private int numCols;

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

    public void addEntry(int row, int col, int value) {
        entries.add(new SparseArrayEntry(row, col, value));
    }

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

    public void removeColumn(int col) {
        numCols--;
    
        for (int i = entries.size() - 1; i >= 0; i--) {
            if (entries.get(i).getCol() == col) {
                entries.remove(i);
            }
        }
    
        for (int i = 0; i < entries.size(); i++) {
            SparseArrayEntry h = entries.get(i);
            if (h.getCol() >= col) {
                SparseArrayEntry e = new SparseArrayEntry(h.getRow(), (h.getCol() - 1), h.getValue());
                entries.set(i, e);
            }
        }
    }
    


    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }
}

public class Main {
    public static void main(String[] args) {
        SparseArray sparseArray = new SparseArray(5, 5);
        sparseArray.addEntry(1, 2, 3);
        sparseArray.addEntry(3, 4, 5);
        sparseArray.addEntry(2, 3, 7);

        System.out.println("Original Array:");
        printSparseArray(sparseArray);

        sparseArray.removeColumn(3);

        System.out.println("\nShifted Array after removing column 3:");
        printSparseArray(sparseArray);
    }

    private static void printSparseArray(SparseArray sparseArray) {
        for (int i = 0; i < sparseArray.getNumRows(); i++) {
            for (int j = 0; j < sparseArray.getNumCols(); j++) {
                System.out.print(sparseArray.getValueAt(i, j) + "\t");
            }
            System.out.println();
        }
    }
}
Main.main(null);

Original Array:
0	0	0	0	0	
0	0	3	0	0	
0	0	0	7	0	
0	0	0	0	5	
0	0	0	0	0	

Shifted Array after removing column 3:
0	0	0	0	
0	0	3	0	
0	0	0	0	
0	0	0	5	
0	0	0	0

Summary:

This question was definitely more challenging because it involved a combination of complex tasks. Firstly, it required implementing methods for sparse array manipulation, which involves dealing with a data structure that doesn’t store every element explicitly. This required understanding the logic behind sparse arrays and how to efficiently manipulate them. I had to do a lot of research as well as ChatGPTing in order to better my understanding of sparse arrays and their manipulation. This is a topic which I feel I need more work in as I felt I understood the problem but still had lots of difficulty when actually coding the solution.