2015 Collegeboard FRQ
Question 3
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.
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.
b.
(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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.util.List;
import java.util.ArrayList;
public class SparseArrayEntry{
private int row;
private int col;
private int value;
public SparseArrayEntry(int r, int c, int v){
this.row = r;
this.col = c;
this.value = v;
}
public int getRow(){
return row;
}
public int getCol(){
return col;
}
public int getValue(){
return value;
}
public void setCol(int c) {
this.col = c;
}
public void setRow(int r) {
this.row = r;
}
}
public class SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray(ArrayList<SparseArrayEntry> entries, int numRows, int numCols) {
this.entries = entries;
this.numRows = numRows;
this.numCols = numCols;
}
// part a
public int getValueAt(int row, int col){
for (SparseArrayEntry entry : entries){ // entries stores ArrayList not 2D array!!
if (entry.getRow() == row && entry.getCol() == col){
return entry.getValue();
}
}
return 0;
}
// part b
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) {
entry.setCol(entry.getCol() - 1);
}
}
numCols--;
}
public void printArray() {
for (int i = 0; i < numRows; i++) {
for (int j = 0; j < numCols; j++) {
System.out.print(getValueAt(i, j) + " ");
}
System.out.println();
}
}
// test
public static void main(String[] args) {
ArrayList<SparseArrayEntry> entries = new ArrayList<>();
entries.add(new SparseArrayEntry(1, 1, 9));
entries.add(new SparseArrayEntry(2, 3, 7));
entries.add(new SparseArrayEntry(2, 4, 8));
SparseArray arr = new SparseArray(entries, 5, 5);
// test part a
System.out.println("Value at (2,3): " + arr.getValueAt(2, 3));
// test part b
arr.printArray();
arr.removeColumn(1);
System.out.println("Remove Column 1:");
arr.printArray();
}
}
SparseArray.main(null);
1
2
3
4
5
6
7
8
9
10
11
12
Value at (2,3): 7
0 0 0 0 0
0 9 0 0 0
0 0 0 7 8
0 0 0 0 0
0 0 0 0 0
Remove Column 1:
0 0 0 0
0 0 0 0
0 0 7 8
0 0 0 0
0 0 0 0
Blog
The specific type of FRQ 3 is 2D Array and Array/Array List. This FRQ introduced me to a sparse array, which I upon looking up I found out is a data structure that represents arrays with default value zero and storing non zero elements. We want to get a value at a position in a sparse array, and be able to remove a specified column in, and this is done through ArrayList entries and SparseArrayEntry objects to represent the non zero elements. removeColumn method iterates through the entries ArrayList from the end to remove elements if the column matches the specified column to be removed, then updates the remaining entries positions to keep the array structure and numCols. I found this frq interesting since it shows how ArrayLists can be used for dynamic data strcutures as we can add and remove elements from ArrayLists unlike traditional arrays.