Question 3 - 2015 FRQ
Code and reflections on question 3 of the 2015 FRQ
Code:
// Creating Sparse Array
public class SparseArrayEntry{
private int row;
private int col;
private int value; // value of entry in sparse array
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;
}
}
// Representing Sparse Array
public class SparseArray{
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray(){
entries = new ArrayList<SparseArrayEntry>();
SparseArrayEntry entry1 = new SparseArrayEntry(1,4,4);
SparseArrayEntry entry2 = new SparseArrayEntry(2,0,1);
SparseArrayEntry entry3 = new SparseArrayEntry(3,1,-9);
SparseArrayEntry entry4 = new SparseArrayEntry(1,1,5);
entries.add(entry1);
entries.add(entry2);
entries.add(entry3);
entries.add(entry4);
for(SparseArrayEntry entry : entries){
if(entry.getRow() > numRows){
numRows = entry.getRow();
}
if(entry.getCol() > numCols){
numCols = entry.getCol();
}
}
}
public int getNumRows(){
return numRows;
}
public int getNumCols(){
return numCols;
}
// PART A:
public int getValueAt(int row, int col){
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("\nBefore removal method:");
System.out.println("-----------------------");
for(SparseArrayEntry entry : entries){
System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
}
entries.removeIf(entry -> entry.getCol() == col); // attempted using entries.remove(), however it was not accurately removing the correct
int i = 0;
for(SparseArrayEntry entry : entries){
// if(entry.getCol() == col){
// entries.remove(i);
// }
if(entry.getCol() > i){
SparseArrayEntry editedEntry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
entries.set(i, editedEntry);
}
i++;
}
this.numCols -= 1;
System.out.println("\nAfter removal method:");
System.out.println("-----------------------");
for(SparseArrayEntry entry : entries){
System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
}
this.numCols = this.numCols;
}
public static void main(String[] args){
SparseArray spArray = new SparseArray();
System.out.println("Part A Testing (Retrieving data at a certain point):");
System.out.println(spArray.getValueAt(1,4));
System.out.println("\nPart B Testing (Removing data at a certain column):");
spArray.removeColumn(1);
}
}
SparseArray.main(null);
Part A Testing (Retrieving data at a certain point):
4
Part B Testing (Removing data at a certain column):
Before removal method:
-----------------------
1 4 4
2 0 1
3 1 -9
1 1 5
After removal method:
-----------------------
1 3 4
2 0 1
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.
public int getValueAt(int row, int col){
for(SparseArrayEntry entry : entries){
if(entry.getRow() == row && entry.getCol() == col){
return entry.getValue();
}
}
return 0;
}
This part required me to use the given conditionals in order to retrieve the value of the sparse array at a given row and column coordinate. This was fairly simple, as I just needed to iterate through every entry and check whether or not the row and column coordinates entered are the same as the row and column coordinates of an actual value in the sparse array. If there was, it would return the value at that point, if not, it would return 0, as in a sparse array, the values at the points surrounding the coordinates are all 0.
Part B
Write the SparseArray method removeColumn. After removing a specified column from a sparse array: 1) All entries in the list entries with column indexes matching col are removed from the list. 2) 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). 3) The number of columns in the sparse array is adjusted to reflect the column removed.
public void removeColumn(int col){
System.out.println("\nBefore removal method:");
System.out.println("-----------------------");
for(SparseArrayEntry entry : entries){ // printing the sparse array before removal method is used...
System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
}
entries.removeIf(entry -> entry.getCol() == col); // attempted using entries.remove(), however it was not accurately removing the columns that matched the parameter.
int i = 0;
for(SparseArrayEntry entry : entries){
// if(entry.getCol() == col){
// entries.remove(i);
// }
if(entry.getCol() > i){
SparseArrayEntry editedEntry = new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue());
entries.set(i, editedEntry);
}
i++;
}
this.numCols -= 1;
System.out.println("\nAfter removal method:");
System.out.println("-----------------------");
for(SparseArrayEntry entry : entries){ // printing the sparse array after removal method was used...
System.out.println(entry.getRow() + " " + entry.getCol() + " " + entry.getValue());
}
this.numCols = this.numCols;
}
This part took me a long time to figure out, as I needed to do two things… 1) Remove the desired column. 2) Move the other columns accordingly.
In order to remove the desired column, I tried iterating through all of the entries, then using the .remove() method if needed. However, no matter how much I tried, .remove() would not remove all the columns that matched the parameter. After spending 3 hours trying to get it to work with .remove(), I researched online for a different method and found “removeIf()”, which needed the class and the condition as parameters. Upon using removeIf(), I got the program to work easily, deleting all columns which matched what was given to the function as a parameter.
In order to move the other columns accordingly, I needed to create another object under the SparseArrayEntry class in order to store the new values, which just moved everything back by one on the columns side. Then, I used the .set() method in order to transfer all the values in the second SparseArrayEntry object to the original SparseArrayEntry sparse array. This part was fairly easy, as I utilized the CollegeBoard Java Reference Table in order to figure out what I would need for this.