Practice 2015 FRQ Question 3 • 9 min read

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

// Class to represent an entry in the sparse array
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 to represent the sparse array
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 int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }
}

//Proof it works
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); 

        System.out.println("Should print 3:");
        System.out.println(sparseArray.getValueAt(1, 2)); 
        System.out.println("Should print 5:");
        System.out.println(sparseArray.getValueAt(3, 4)); 
        System.out.println("Should print 0:");
        System.out.println(sparseArray.getValueAt(0, 0)); 
    }
}
Main.main(null);

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

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) { // new thingy
        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++) {
            if (entries.get(i).getCol() > col) {
                SparseArrayEntry h = entries.get(i);
                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;
    }
}
// Proof it works
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");
        System.out.println("Should print 3:");
        System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
        System.out.println("Should print 5:");
        System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
        System.out.println("Should print 7:");
        System.out.println(sparseArray.getValueAt(2, 3)); // Should print 7
        System.out.println("");

        sparseArray.removeColumn(3);

        System.out.println("Shifted Array");
        System.out.println("Should print 3:");
        System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
        System.out.println("Should print 5:");
        System.out.println(sparseArray.getValueAt(3, 3)); // Should print 5 (shifted from column 4 to 3)
        System.out.println("Should print 7:");
        System.out.println(sparseArray.getValueAt(2, 2)); // Should print 7 (shifted from column 3 to 2)
    }
}

Main.main(null);