Collegeboard FRQ Practice
Question 1:
(a) Write a static method arraySum that calculates and returns the sum of the entries in a specified one-dimensional array. The following example shows an array arr1 and the value returned by a call to arraySum.
(b) Write a static method rowSums that calculates the sums of each of the rows in a given two-dimensional array and returns these sums in a one-dimensional array. The method has one parameter, a two-dimensional array arr2D of int values. The array is in row-major order: arr2D [r] [c] is the entry at row r and column c. The method returns a one-dimensional array with one entry for each row of arr2D such that each entry is the sum of the corresponding row in arr2D. As a reminder, each row of a two-dimensional array is a one-dimensional array.
(c) A two-dimensional array is diverse if no two of its rows have entries that sum to the same value. In the following examples, the array mat1 is diverse because each row sum is different, but the array mat2 is not diverse because the first and last rows have the same sum. Write a static method isDiverse that determines whether or not a given two-dimensional array is diverse. The method has one parameter: a two-dimensional array arr2D of int values. The method should return true if all the row sums in the given array are unique; otherwise, it should return false. In the arrays shown above, the call isDiverse (mat1) returns true and the call isDiverse(mat2) returns false.
Key Algorithm: 2D Arrays + Arrays
public class Main {
public static int arraySum (int[] arr)
{
int sum = 0;
for (int i = 0; i < arr.length; i++)
{
sum += arr[i];
}
return sum;
}
public static int[] rowSums(int[][] arr2D) {
int[] sums = new int[arr2D.length];
for (int i = 0; i < arr2D.length; i++) {
int sum = 0;
for (int j = 0; j < arr2D[i].length; j++) {
sum += arr2D[i][j];
}
sums[i] = sum;
}
return sums;
}
public static boolean isDiverse(int[][] arr2D)
{
int[] sums = rowSums(arr2D);
HashSet<Integer> set = new HashSet<>();
for (int num : sums) {
if (set.contains(num)) {
return false;
}
set.add(num);
}
return true;
}
public static void main(String[] args)
{
int[] arr2 = {1, 3, 2, 7, 3};
System.out.println(arraySum(arr2));
int[][] arr1 = {
{1, 1, 5, 3, 4},
{12, 7, 6, 1, 9},
{8, 11, 10, 2, 5},
{3, 2, 3, 0, 6}
};
int[] sums = rowSums(arr1);
for (int i = 0; i < sums.length; i++)
{
System.out.print(sums[i] + " ");
}
System.out.println();
System.out.println(isDiverse(arr1));
}
}
Main.main(null);
16
14 35 36 14
false
Question 2:
Consider a guessing game in which a player tries to guess a hidden word. The hidden word contains only capital letters and has a length known to the player. A guess contains only capital letters and has the same length as the hidden word.
After a guess is made, the player is given a hint that is based on a comparison between the hidden word and the guess. Each position in the hint contains a character that corresponds to the letter in the same position in the guess. The following rules determine the characters that appear in the hint.
The HiddenWord class will be used to represent the hidden word in the game. The hidden word is passed to the constructor. The class contains a method, getHint, that takes a guess and produces a hint.
For example, suppose the variable puzzle is declared as follows.
HiddenWord puzzle = new HiddenWord(“HARPS”);
The following table shows several guesses and the hints that would be produced.
Write the complete HiddenWord class, including any necessary instance variables, its constructor, and the method, getHint, described above. You may assume that the length of the guess is the same as the length of the hidden word.
Key Algorithm: Classes and Array/ArrayList
public class HiddenWord {
private String word;
public HiddenWord (String word)
{
this.word = word;
}
public String getHint (String guess)
{
String result ="";
for (int i = 0; i < guess.length(); i++)
{
if (guess.charAt(i) == word.charAt(i))
{
result += guess.charAt(i);
}
else if (word.indexOf(guess.charAt(i)) != -1)
{
result += "+";
}
else
{
result += "*";
}
}
return result;
}
public static void main(String[] args)
{
HiddenWord puzzle = new HiddenWord("HARPS");
System.out.println(puzzle.getHint("AAAAA"));
System.out.println(puzzle.getHint("HELLO"));
System.out.println(puzzle.getHint("HEART"));
System.out.println(puzzle.getHint("HARMS"));
System.out.println(puzzle.getHint("HARPS"));
}
}
HiddenWord.main(null);
+A+++
H****
H*++*
HAR*S
HARPS
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.
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.
(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.
(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.
When sparse has the state shown above, the call sparse.removeColumn(1) could result insparse having the following values in its instance variables (since entries is in no particular order, it would be equally valid to reverse the order of its two items). The shaded areas below show the changes.
Complete removeColumn method.
Key Algorithm: Method and Control Structures
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 {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray() {
entries = new ArrayList<SparseArrayEntry>();
}
public void add(SparseArrayEntry entry) {
entries.add(entry);
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) //Part A
{
for (SparseArrayEntry i: entries)
{
if (i.getRow() == row && i.getCol() == col)
{
return i.getValue();
}
}
return 0;
}
public void removeColumn(int col) {
int i = 0;
while (i < entries.size())
{
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()));
i++;
}
else
{
i++;
}
}
numCols--;
}
public void printEntries() {
for (SparseArrayEntry entry : entries) {
System.out.println("Row: " + entry.getRow() + ", Column: " + entry.getCol() + ", Value: " + entry.getValue());
}
}
}
public class Main {
public static void main(String[] args)
{
SparseArray sparseArray = new SparseArray();
sparseArray.add(new SparseArrayEntry(1, 1, 5));
sparseArray.add(new SparseArrayEntry(1, 4, 4));
sparseArray.add(new SparseArrayEntry(2, 0, 1));
sparseArray.add(new SparseArrayEntry(3, 1, -9));
System.out.println("Before Remove: ");
sparseArray.printEntries();
sparseArray.removeColumn(1); // Remove column 1
System.out.println("After Remove: ");
sparseArray.printEntries();
}
}
Main.main(null);
Before Remove:
Row: 1, Column: 1, Value: 5
Row: 1, Column: 4, Value: 4
Row: 2, Column: 0, Value: 1
Row: 3, Column: 1, Value: -9
After Remove:
Row: 1, Column: 3, Value: 4
Row: 2, Column: 0, Value: 1