FRQ3 • 12 min read

Question 3a

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

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 removeColumn(int col) {
        Iterator<SparseArrayEntry> iterator = entries.iterator();
        while (iterator.hasNext()) {
            SparseArrayEntry entry = iterator.next();
            if (entry.getCol() == col) {
                iterator.remove();
            } else if (entry.getCol() > col) {
                entry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
            }
        }
        numCols--; // change the # of columns

        
    }

    public int getValueAt(int row, int col) {
        for (SparseArrayEntry e : entries) {
            if (e.getRow() == row && e.getCol() == col) {
                return e.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, 3);

        // testing the program
        sparse.addEntry(new SparseArrayEntry(1, 1, 5));
        sparse.addEntry(new SparseArrayEntry(1, 2, 7));
        sparse.addEntry(new SparseArrayEntry(2, 2, -3));
        sparse.addEntry(new SparseArrayEntry(3, 1, -9));
        sparse.addEntry(new SparseArrayEntry(3, 3, 2));

        // REMOVE COLUMN 2
        sparse.removeColumn(2);

        // Testing the getValueAt method
        System.out.println("Value at (1, 1): " + sparse.getValueAt(1, 1)); // Output: 5
        System.out.println("Value at (1, 2): " + sparse.getValueAt(1, 2)); // Output: 0 (removed)
        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: 2

        System.out.println("NumRows: " + sparse.getNumRows()); // Output: 3
        System.out.println("NumCols: " + sparse.getNumCols()); // Output: 2
    }
}


Main.main(null);

Treasure at (1, 4): 2
Treasure at (2, 0): 3
Treasure at (3, 1): -7
Treasure at (0, 0): 0

3b

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

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;
    }

    // Getters
    public int getRow() { return row; }
    public int getCol() { return col; }
    public int getValue() { return value; }

    // Setters
    public void setCol(int col) { this.col = col; }
}

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

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

    // Other methods
    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 void removeColumn(int col) {
        Iterator<SparseArrayEntry> iter = entries.iterator();
        while (iter.hasNext()) {
            SparseArrayEntry entry = iter.next();
            if (entry.getCol() == col) {
                iter.remove();
            } else if (entry.getCol() > col) {
                entry.setCol(entry.getCol() - 1);
            }
        }
        numCols--;
    }

    // Getters for numRows and numCols
    public int getNumRows() { return numRows; }
    public int getNumCols() { return numCols; }
}

public class Main {
    public static void main(String[] args) {
        SparseArray sparse = new SparseArray(6, 5);
        sparse.addEntry(new SparseArrayEntry(1, 1, 5));
        sparse.addEntry(new SparseArrayEntry(2, 0, 1));
        sparse.addEntry(new SparseArrayEntry(3, 1, -9));
        sparse.addEntry(new SparseArrayEntry(1, 4, 4));

        // Testing removeColumn
        sparse.removeColumn(1);
        
        // Output the entries and array dimensions after removal
        for (int i = 0; i < sparse.getNumRows(); i++) {
            for (int j = 0; j < sparse.getNumCols(); j++) {
                if (sparse.getValueAt(i, j) != 0) {
                    System.out.println("Row: " + i + " Col: " + j + " Value: " + sparse.getValueAt(i, j));
                }
            }
        }
        System.out.println("Number of rows: " + sparse.getNumRows());
        System.out.println("Number of cols: " + sparse.getNumCols());
    }
}


Main.main(null);

Row: 1 Col: 3 Value: 4
Row: 2 Col: 0 Value: 1
Number of rows: 6
Number of cols: 4

This one was extremely hard for me, as I had very little knowledege on sparsearrays and how to even approach this question. I have to admit, I definetely used outside resources and still have a slight struggle for it. I understood it a little bit and was able to code it after sometime but initially it took a long time to learn this one as it was very hard for me to grasp the concept.