2015 FRQ 3 (Array List)
2015 FRQ 3 Solution + Reflection
Question 3: Array List
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.
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.
Reflection
Part A was very simple overall which was just a simple for-each loop that iterated through every sparseArrayEntry object in the entries array then checked if the row and column value returned by the getCol and getRow methods matched the values passed into the function of getValueAt. If it did, it would then run the getValue method of the object and return the value. If no object was found, it would return 0. This was a very simple question about on how to iterate through an array list and was not too difficult.
Part B
Write the SparseArray method removeColumn. After removing a specified column from a sparse array:
- 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.
Reflection
This was most probably the hardest section of the exam out of all the other FRQ segments with their being two major parts to the problem removing the column in the sparseArray and also editing the column value of those that were greater than the column value that was removed. The solution to this at first in my opinion was to use a loop of some kind and eventually I had written it using each type of loop for, for-each, and finally while the second portion the ability to edit the column functioning across all the varying implementations with just iterating through the arrayList then if the column-value was greater than passed in column value at the element at that a index I would then create a new sparseArrayEntry object with the a column-value one less than the element that was there then setting it to the index of the prior element using the set() method. However, I simply couldn’t remove all sparseArrayEntry objects in the arrayList no matter what I did in array using remove() method the only method I found to be able to remove all elements was to the use the removeIf() method to be able to properly remove all the elements that had a column value that was equal to the passed in column value, logically this makes no sense as there is no reason that the remove() method should not work. This was a very difficult question and I was not able to solve it in a conventional approach which was very frustrating.
public class SparseArrayEntry {
// The row index and column index for this entry in the sparse array
private int row;
private int col;
// The value of this entry in the sparse array
private int value;
// Constructs a SparseArrayEntry object that represents a sparse array element with row index r and column index c, containing value v.
public SparseArrayEntry(int r, int c, int v){
row = r;
col = c;
value = v;
}
// Returns the row index of this sparse array element.
public int getRow(){
return row;
}
// Returns the column index of this sparse array element.
public int getCol(){
return col;
}
// Returns the value of this sparse array element.
public int getValue(){
return value;
}
}
public class SparseArray{
/** The number of rows and columns in the sparse array. */
private int numRows;
private int numCols;
/** The list of entries representing the non-zero elements of the sparse array. Entries are stored in the
list in no particular order. Each non-zero element is represented by exactly one entry in the list.*/
private List<SparseArrayEntry> entries;
// Constructs an empty SparseArray.
public SparseArray(){
entries = new ArrayList<SparseArrayEntry>();
SparseArrayEntry e1 = new SparseArrayEntry(1,4,4);
SparseArrayEntry e2 = new SparseArrayEntry(2,0,1);
SparseArrayEntry e3 = new SparseArrayEntry(3,1,-9);
SparseArrayEntry e4 = new SparseArrayEntry(1,1,5);
entries.add(e1);
entries.add(e2);
entries.add(e3);
entries.add(e4);
for(SparseArrayEntry entry : entries){
if(entry.getRow() > numRows){
numRows = entry.getRow();
}
if(entry.getCol() > numCols){
numCols = entry.getCol();
}
}
}
// Returns the number of rows in the sparse array.
public int getNumRows(){
return numRows;
}
// Returns the number of columns in the sparse array.
public int getNumCols(){
return numCols;
}
// Part A
public int getValueAt(int row, int col){
int cols = this.getNumCols();
int rows = this.getNumRows();
for(SparseArrayEntry entry : entries){
if(entry.getRow() == row && entry.getCol() == col){
return entry.getValue();
}
}
return 0;
}
// Part B
public void removeColumn(int col){
System.out.println("Number of Cols");
for(SparseArrayEntry entry : entries){
System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
}
System.out.println("\nRemoving Column " + this.getNumCols());
// Possibly illegal move as it is not in the look up table for the exam 🤓
// Literally the only thing that actually works
entries.removeIf(entry -> entry.getCol() == col);
int i = 0;
while(i < entries.size()){
SparseArrayEntry entry = entries.get(i);
// Literally doesn't work if the loop was a for it wouldn't work either. Nor would a for-each it literally doesn't work in a loop other than using the method above
// if (entry.getCol() == col){
// entries.remove(entry);
// }
if (entry.getCol() > col){
int newCol = entry.getCol()-1;
SparseArrayEntry newEntry = new SparseArrayEntry(entry.getRow(), newCol, entry.getValue());
entries.set(i, newEntry); // Need to use set otherwise the subtraction for the new columns doesn't work
}
i++;
}
System.out.println("\nAfter removal");
for(SparseArrayEntry entry : entries){
System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
}
this.numCols = this.numCols - 1;
System.out.println("\nNumber of Columns: " + this.getNumCols());
}
public static void main(String[] args){
SparseArray sparse = new SparseArray();
System.out.println("getValueAt Method (Part A)\n");
System.out.println("Getting Value at 3,3");
System.out.println(sparse.getValueAt(3,3));
System.out.println("\nGetting Value at 3,1");
System.out.println(sparse.getValueAt(3,1));
System.out.println("\nremoveColumn Method (Part B)\n");
sparse.removeColumn(1);
}
}
SparseArray.main(null)
getValueAt Method (Part A)
Getting Value at 3,3
0
Getting Value at 3,1
-9
removeColumn Method (Part B)
Number of Cols
1 4 4
2 0 1
3 1 -9
1 1 5
Removing Column 4
After removal
1 3 4
2 0 1
Number of Columns: 3