Trimester 2 Final (2015 FRQ)
2015 FRQ Solutions all in one place with no reflections.
Question 1: 2D Arrays
Part 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.
public static int arraySum(int[] arr){
int arrSum = 0;
for(int i = 0; i < arr.length; i++){
arrSum += arr[i];
}
return arrSum;
}
int[] arr = {1,2,3,4};
arraySum(arr);
10
Part 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. For example, if mat1 is the array represented by the following table, the call rowSums(mat1) returns the array {16, 32, 28, 20}.
public static int[] rowSums(int[][] arr2d){
int[] sumArr = new int[arr2d.length];
for(int i = 0; i < arr2d.length; i++){
int rowSum = arraySum(arr2d[i]);
sumArr[i] = rowSum;
};
return sumArr;
}
int[][] mat1 = new int[][]{
{1,3,2,7,3},
{10,10,4,6,2},
{5,3,5,9,6},
{7,6,4,2,1}
};
System.out.println(Arrays.toString(rowSums(mat1)));
[16, 32, 28, 20]
Part 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.
public static boolean isDiverse(int[][] mat1){
boolean diverse = false;
int[] rowSums = rowSums(mat1);
for(int i = 0; i < rowSums.length; i++){
for(int j = i+1; j < rowSums.length; j++){
if (rowSums[i] != rowSums[j]){
continue;
} else{
return diverse;
}
}
}
diverse = true;
return diverse;
}
System.out.println("Call 1 Mat 1");
System.out.println(isDiverse(mat1));
int[][] mat2 = {
{1,1,5,3,4},
{12,7,6,1,9},
{8,11,10,2,5},
{3,2,3,0,6}
};
System.out.println("\nCall 2 Mat 2");
System.out.println(isDiverse(mat2));
Call 1 Mat 1
true
Call 2 Mat 2
false
Question 2: Classes
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.
public class HiddenWord{
private String hiddenWord;
public HiddenWord(String hiddenWord){
this.hiddenWord = hiddenWord.toUpperCase().strip();
}
public String getHiddenWord(){
return this.hiddenWord;
}
public String getHint(String guess){
guess = guess.strip().toUpperCase();
String word = this.getHiddenWord();
int wordLength = word.length();
char[] hintArr = new char[wordLength];
for(int i = 0; i < wordLength; i++){
hintArr[i] = '*';
}
for(int i = 0; i < guess.length(); i++){
if(guess.charAt(i) == word.charAt(i)){
hintArr[i] = guess.charAt(i);
} else if(word.indexOf(guess.charAt(i)) != -1){
hintArr[i] = '+';
}
}
String hint = String.valueOf(hintArr);
return hint;
}
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: 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.
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.
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;
}
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;
}
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 loop 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\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\n");
sparse.removeColumn(1);
}
}
SparseArray.main(null)
getValueAt Method
Getting Value at 3,3
0
Getting Value at 3,1
-9
removeColumn Method
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
Question 4: Methods And Control Structures
Part A
A number group represents a group of integers defined in some way. It could be empty, or it could contain one or more integers. Write an interface named NumberGroup that represents a group of integers. The interface should have a single contains method that determines if a given integer is in the group. For example, if group1 is of type NumberGroup, and it contains only the two numbers -5 and 3, then group1.contains(-5) would return true, and group1.contains(2) would return false. Write the complete NumberGroup interface. It must have exactly one method.
public interface NumberGroup{
boolean contains(int value);
}
Part B
A range represents a number group that contains all (and only) the integers between a minimum value and a maximum value, inclusive. Write the Range class, which is a NumberGroup. The Range class represents the group of int values that range from a given minimum value up through a given maximum value, inclusive. For example, the declaration NumberGroup range1 = new Range(-3, 2); represents the group of integer values -3, -2, -1, 0, 1, 2. Write the complete Range class. Include all necessary instance variables and methods as well as a constructor that takes two int parameters. The first parameter represents the minimum value, and the second parameter represents the maximum value of the range. You may assume that the minimum is less than or equal to the maximum.
public class Range implements NumberGroup{
private int minVal;
private int maxVal;
public Range(int minVal, int maxVal){
this.minVal = minVal;
this.maxVal = maxVal;
}
@Override
public boolean contains(int value){
if (value >= this.minVal && value <= this.maxVal){
return true;
} else{
return false;
}
}
public static void main(String[] args){
Range range1 = new Range(-3,2);
System.out.println(range1.contains(-1));
System.out.println(range1.contains(3));
}
}
Range.main(null);
true
false
Part C
The MultipleGroups class (not shown) represents a collection of NumberGroup objects and is a NumberGroup. The MultipleGroups class stores the number groups in the instance variable groupList (shown below), which is initialized in the constructor. private List<NumberGroup> groupList; Write the MultipleGroups method contains. The method takes an integer and returns true if and only if the integer is contained in one or more of the number groups in groupList. For example, suppose multiple1 has been declared as an instance of MultipleGroups and consists of the three ranges created by the calls new Range(5, 8), new Range(10, 12), and new Range(1, 6). The following table shows the results of several calls to contains.
public class MultipleGroups{
private List<NumberGroup> groupList;
private MultipleGroups(List<NumberGroup> groupList){
this.groupList = groupList;
}
public boolean contains(int value){
for(NumberGroup group : groupList){
if(group.contains(value)){
return true;
}
}
return false;
}
public static void main(String[] args){
Range range1 = new Range(-3, 2);
Range range2 = new Range(4, 9);
List<NumberGroup> groupList = new ArrayList<NumberGroup>();
groupList.add(range1);
groupList.add(range2);
MultipleGroups multiGroup = new MultipleGroups(groupList);
System.out.println(multiGroup.contains(3));
}
}
MultipleGroups.main(null);
false