2015 FRQ Question 3 • 17 min read

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

public int getValueAt(int row, int col) {
    // Iterate through entries to find the matching element
    for (SparseArrayEntry entry : entries) {
        if (entry.getRow() == row && entry.getCol() == col) {
            return entry.getValue();
        }
    }
    return 0;  // If no match found, return 0
}

This method loops through the entries list of SparseArrayEntry objects. For each entry, it checks if the row and column match the specified row and col parameters. If a match is found, it returns the value of that entry. If no match is found after looping through all entries, it returns 0.

(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray:

public void removeColumn(int col) {
    // Remove entries with matching column
    entries.removeIf(entry -> entry.getCol() == col);

    // Adjust column indexes for entries with col > specified col
    for (SparseArrayEntry entry : entries) {
        if (entry.getCol() > col) {
            entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
        }
    }

    numCols--;  // Adjust number of columns
}

• We use the removeIf method to remove entries with a column matching col.
• Then, we loop through all entries. If an entry has a column greater than col, we create a new SparseArrayEntry with the column decremented by one.
• Finally, we decrement the numCols variable to reflect the removal of the column.

Blog: Key Algorithm and Matching FRQ Type

Method and Control Structure:

• In getValueAt, we use a for-each loop to iterate through entries and check for the matching row and column.
• The removeColumn method utilizes loops and conditionals to remove entries and adjust column indexes.

Array/ArrayList:

• The entries list in the SparseArray class is an ArrayList that stores SparseArrayEntry objects.

In this implementation, we have completed the getValueAt and removeColumn methods for the SparseArray class. These methods adhere to the specifications given in the FRQ, providing functionality to access and manipulate sparse arrays efficiently.

Final Integration of Class with User Input

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

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 int getValue() {
        return value;
    }
}

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

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

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    public int getValueAt(int row, int col) {
        // Iterate through entries to find the matching element
        for (SparseArrayEntry entry : entries) {
            if (entry.getRow() == row && entry.getCol() == col) {
                return entry.getValue();
            }
        }
        return 0;  // If no match found, return 0
    }

    public void removeColumn(int col) {
        // Remove entries with matching column
        entries.removeIf(entry -> entry.getCol() == col);

        // Adjust column indexes for entries with col > specified col
        for (SparseArrayEntry entry : entries) {
            if (entry.getCol() > col) {
                entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
            }
        }

        numCols--;  // Adjust number of columns
    }

    public void addEntry(SparseArrayEntry entry) {
        entries.add(entry);
        numRows = Math.max(numRows, entry.getRow() + 1);
        numCols = Math.max(numCols, entry.getCol() + 1);
    }

    public void printEntries() {
        for (SparseArrayEntry entry : entries) {
            System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        SparseArray sparse = new SparseArray();

        System.out.print("Enter number of rows: ");
        int numRows = scanner.nextInt();
        System.out.print("Enter number of columns: ");
        int numCols = scanner.nextInt();
        scanner.nextLine();  // Consume newline

        System.out.println("Enter sparse array entries in the format: row col value");
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                System.out.print("Enter value for row " + i + " column " + j + ": ");
                int value = scanner.nextInt();
                if (value != 0) {
                    sparse.addEntry(new SparseArrayEntry(i, j, value));
                }
            }
        }

        System.out.println("Sparse Array Entries:");
        sparse.printEntries();

        System.out.print("Enter the row to get value from: ");
        int getRow = scanner.nextInt();
        System.out.print("Enter the column to get value from: ");
        int getCol = scanner.nextInt();

        int retrievedValue = sparse.getValueAt(getRow, getCol);
        System.out.println("Value at (" + getRow + ", " + getCol + "): " + retrievedValue);

        System.out.print("Enter the column to remove: ");
        int removeCol = scanner.nextInt();
        sparse.removeColumn(removeCol);

        System.out.println("Sparse Array Entries after removing column " + removeCol + ":");
        sparse.printEntries();

        scanner.close();
    }
}
SparseArray.main(null)

Enter number of rows: Enter number of columns: Enter sparse array entries in the format: row col value
Enter value for row 0 column 0: Enter value for row 0 column 1: Enter value for row 0 column 2: Enter value for row 1 column 0: Enter value for row 1 column 1: Enter value for row 1 column 2: Enter value for row 2 column 0: Enter value for row 2 column 1: Enter value for row 2 column 2: Enter value for row 3 column 0: Enter value for row 3 column 1: Enter value for row 3 column 2: Sparse Array Entries:
1 1 2
1 2 1
Enter the row to get value from: Enter the column to get value from: Value at (0, 2): 0
Enter the column to remove: Sparse Array Entries after removing column 1:
1 2 1

Explanation

• We have added a Scanner object scanner to read user input.
• The main method now prompts the user to input the number of rows and columns for the sparse array.
• It then allows the user to input values for each position in the sparse array.
• After inputting the values, it prints the sparse array entries.
• Next, it prompts the user to enter a row and column to get the value from, and it retrieves and prints that value.
• Finally, it asks the user for a column to remove and prints the sparse array entries after removing that column.