Quick Note
For each part of this FRQ and the other three FRQs, I included two versions of the solution: one with no runtime (i.e. CollegeBoard’s key) and one with runtime.
Question 3: Arrays/Arraylists (and somewhat 2D Arrays)
Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA.
Notes:
-
Assume that the classes listed in the Java Quick Reference have been imported where appropriate.
-
Unless otherwise noted in the question, assume that parameters in method calls are not null and that methods are called only when their preconditions are satisfied.
-
In writing solutions for each question, you may use any of the accessible methods that are listed in classes defined in that question. Writing significant amounts of code that can be replaced by a call to one of these methods will not receive full credit.
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.
The SparseArray class represents a sparse array. It contains a list of SparseArrayEntry objects, each of which represents one of the non-zero elements in the array. The entries representing the non-zero elements are stored in the list in no particular order. Each non-zero element is represented by exactly one entry in the list.
The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values.
The sample array can be represented by a SparseArray object, sparse, with the following instance variable values. The items in entries are in no particular order; one possible ordering is shown below.
Question 3a
(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.
Complete method getValueAt below.
No Runtime
public 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 {
public int getValueAt(int row, int col){
for(SparseArrayEntry s : entries){
if(s.getRow() == row && s.getCol() == col)
return s.getValue();
}
}
}
With Runtime
import java.util.ArrayList;
import java.util.List;
public class SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray() {
entries = new ArrayList<SparseArrayEntry>();
// Example initialization; this will vary depending on your actual use case.
entries.add(new SparseArrayEntry(1, 4, 4));
entries.add(new SparseArrayEntry(2, 0, 1));
entries.add(new SparseArrayEntry(3, 1, -9));
entries.add(new SparseArrayEntry(1, 1, 5));
numRows = 6;
numCols = 5;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col)
return entry.getValue();
}
return 0; // Return 0 if no entry is found
}
// test cases
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
System.out.println("Value at (3, 1): " + sparse.getValueAt(3, 1)); // Should return -9 since (3,1) is an actual entry
System.out.println("Value at (3, 3): " + sparse.getValueAt(3, 3)); // Should return 0 since (3,3) is not an entry
}
}
SparseArray.main(null);
Value at (3, 1): -9
Value at (3, 3): 0
Question 3b
(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray:
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.
The sample object sparse from the beginning of the question is repeated for your convenience.
Complete method removeColumn below.
No Runtime
public class SparseArray1 {
public void removeColumn(int col){
for(int i = entries.size() - 1; i >= 0; i--){
SparseArrayEntry s = entries.get(i);
if(s.getCol() == col){
entries.remove(i);
} else if(s.getCol() > col){
entries.set(i, new SparseArrayEntry(s.getRow(),s.getCol() - 1, s.getValue()));
}
}
numCols--;
}
}
With Runtime
public class SparseArray1 {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray1() { // Corrected constructor name
entries = new ArrayList<SparseArrayEntry>();
entries.add(new SparseArrayEntry(1, 4, 4));
entries.add(new SparseArrayEntry(2, 0, 1));
entries.add(new SparseArrayEntry(3, 1, -9));
entries.add(new SparseArrayEntry(1, 1, 5));
numRows = 6;
numCols = 5;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col)
return entry.getValue();
}
return 0; // If no entry is found
}
public void removeColumn(int col) {
for (int i = entries.size() - 1; i >= 0; i--) {
SparseArrayEntry entry = entries.get(i);
if (entry.getCol() == col) {
entries.remove(i);
} else if (entry.getCol() > col) {
entries.set(i, new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue()));
}
}
numCols--; // decrement number of columns by 1
}
// displays the sparse array
public void display() {
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
System.out.print(getValueAt(i, j) + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
SparseArray1 sparse = new SparseArray1();
System.out.println("Original SparseArray:");
sparse.display();
sparse.removeColumn(1);
System.out.println("SparseArray after removing column 1:");
sparse.display();
}
}
SparseArray1.main(null);
Original SparseArray:
0 0 0 0 0
0 5 0 0 4
1 0 0 0 0
0 -9 0 0 0
0 0 0 0 0
0 0 0 0 0
SparseArray after removing column 1:
0 0 0 0
0 0 0 4
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Reflection for FRQ 3
This question was by far the most challenging for me to do out of the four, as while I was able to complete it, it took me some time before I began to understand what exactly Sparse arrays were. I found myself having to reread the question a few times in order to comprehend what it was asking me to do. If this happened to me on the actual AP Exam, I would end up losing some valuable time that could have been spent either trying to note down what information the question is giving me or even just complete another FRQ that I know how to answer better. Having completed the question, I definitely have a much better understanding of it now than I did before I saw this. Part A essentially asked to create a method that returned the value of an entry at a specific row and column. If there was an entry for that row and column, then the program would successfully display that value. If there was no entry for that row and column, then the program would just return 0 indicating that there is no entry there. This question centered a lot on 2D arrays, making it that kind of FRQ, although in the runtime version of my response, there were also a few elements of ArrayLists that I had to use as well. Overall, I now know that 2D arrays is something that I will need to heavily review to ensure that I don’t get frozen on a question like this on the real AP Test should I get one as involved as this.