AP CSA 2015 Free Response Questions
Question 1
Type: Array/2D Array
Blog This FRQ was interesting and a good review in many ways because it required me to return back to basics but also requried me to think about new applications. The Key Algorithm was Array iteration and comparison, as it went over different types of arrays and how to get information from them, therefore iterating over them. This key algorithm fits into the type because array iteration and comparison falls into arrays.
Part A
Calculate Array Sum - Iterate through an array and sum its elements
public static int arraySum(int[] arr)
{
int sum = 0;
for(int n : arr)
sum += n;
return sum;
}
// Testing
int[] array = {1, 2, 3};
System.out.print("Original Array: ");
System.out.println(Arrays.toString(array));
System.out.print("Sum: ");
System.out.print(arraySum(array)); // should return 6
Original Array: [1, 2, 3]
Sum: 6
Part B
Check Array Diversity - Use the array sum to determine if arrays are diverse by comparing their sums.
public static int[] rowSums(int[][] arr2D)
{
int[] sums = new int[arr2D.length];
for(int i = 0; i < sums.length; i++) {
sums[i] = arraySum(arr2D[i]);
}
return sums;
}
// Testing
int[][] my2DArray = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println("Sample get: ");
System.out.print(my2DArray[0][1]); // Output: 2
System.out.println("\nSum");
System.out.print(Arrays.toString(rowSums(my2DArray))); // Output: [6, 15, 24]
Sample get:
2
Sum
[6, 15, 24]
Part C
Diverse Arrays in 2D Array - Check each row of a 2D array for diversity using the methods from parts (a) and (b).
public static boolean isDiverse(int[][] arr2D)
{
int[] sums = rowSums(arr2D);
for(int i = 0; i < sums.length; i++)
for(int j = i+1; j < sums.length; j++)
if(sums[i] == sums[j])
return false;
return true;
}
// Testing
int[][] my2DArray = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println("First Array Sum");
System.out.print(Arrays.toString(rowSums(my2DArray)));
System.out.println("Is the first array diverse? ");
System.out.println(isDiverse(my2DArray));
System.out.println();
int[][] my2DArray2 = { {3, 2, 1}, {1, 2, 3}, {2, 3, 1}};
System.out.println("Diverse Array Sum");
System.out.print(Arrays.toString(rowSums(my2DArray2)));
System.out.println();
System.out.println("Is the second array diverse? ");
System.out.print(isDiverse(my2DArray2));
First Array Sum
[6, 15, 24]Is the first array diverse?
true
Diverse Array Sum
[6, 6, 6]
Is the second array diverse?
false
Question 2
Type: Method and Control Structures
Blog This FRQ is about how to compare and perform operations with strings. I had to iterate through a guessed word and generate hints based on matching characters and presence in the hidden word, which is (un)surprisingly harder. Using methods and control structures and Java string operations, I was able to complete the hidden word challenge.
public class HiddenWord {
private String hidden;
public HiddenWord(String h) {
hidden = h;
}
public String getHint(String guess) {
String r = "";
for (int i = 0; i < guess.length(); i++) {
if (guess.charAt(i) == hidden.charAt(i))
r += "" + guess.charAt(i);
else if (hidden.indexOf(guess.charAt(i)) > -1)
r += "+";
else
r += "*";
}
return r;
}
// Testing method
public static void main(String[] args) {
HiddenWord hw = new HiddenWord("hello");
System.out.println(hw.getHint("blalo")); // Example usage
}
}
HiddenWord.main(null);
*+*lo
Quesiton 3
Type: List/List Iteration
Blog This question taught me to review how classes worked with lists to manipulate data. In a sparse array, which is an efficient way to store and manipulate data with a significant number of zero or null values, I was tested on navigating and modifying a list of SparseArrayEntry objects to retrieve values and remove columns, showcasing the importance of list iteration and modification in data structure management. This ties back into list iteration because these list operations were simple, but they had to be executed through a variety of classes, increasing the complexity of the quesiton.
Part A
Value Retrieval - Iterate through a list of SparseArrayEntry objects to find the value at a specific row and column.
import java.util.ArrayList;
import java.util.List;
// Class to represent an entry in the sparse array
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
// Class to represent the sparse array
class SparseArray {
private List<SparseArrayEntry> entries;
private int numRows;
private int numCols;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new ArrayList<>();
}
public void addEntry(int row, int col, int value) {
entries.add(new SparseArrayEntry(row, col, value));
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry e : entries) {
if (e.getRow() == row && e.getCol() == col) {
return e.getValue();
}
}
return 0;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
}
// Example usage
public class Main {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(5, 5); // 5x5 sparse array
sparseArray.addEntry(1, 2, 3); // Add an entry at row 1, column 2 with value 3
sparseArray.addEntry(3, 4, 5); // Add another entry at row 3, column 4 with value 5
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
System.out.println("Should print 0:");
System.out.println(sparseArray.getValueAt(0, 0)); // Should print 0 (default value)
}
}
Main.main(null);
Should print 3:
3
Should print 5:
5
Should print 0:
0
Part B
Column Removal - Modify the list of SparseArrayEntry objects to remove entries in a specific column and adjust the column indices of remaining entries.
import java.util.ArrayList;
import java.util.List;
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
class SparseArray {
private List<SparseArrayEntry> entries;
private int numRows;
private int numCols;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new ArrayList<>();
}
public void addEntry(int row, int col, int value) {
entries.add(new SparseArrayEntry(row, col, value));
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry e : entries) {
if (e.getRow() == row && e.getCol() == col) {
return e.getValue();
}
}
return 0;
}
public void removeColumn(int col) { // new thingy
numCols--;
for (int i = entries.size() - 1; i >= 0; i--) {
if (entries.get(i).getCol() == col) {
entries.remove(i);
}
}
for (int i = 0; i < entries.size(); i++) {
if (entries.get(i).getCol() > col) {
SparseArrayEntry h = entries.get(i);
SparseArrayEntry e = new SparseArrayEntry(h.getRow(), (h.getCol() - 1), h.getValue());
entries.set(i, e);
}
}
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
}
// Testing
public class Main {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(5, 5);
sparseArray.addEntry(1, 2, 3);
sparseArray.addEntry(3, 4, 5);
sparseArray.addEntry(2, 3, 7);
System.out.println("Original Array");
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 4)); // Should print 5
System.out.println("Should print 7:");
System.out.println(sparseArray.getValueAt(2, 3)); // Should print 7
System.out.println("");
sparseArray.removeColumn(3);
System.out.println("Shifted Array");
System.out.println("Should print 3:");
System.out.println(sparseArray.getValueAt(1, 2)); // Should print 3
System.out.println("Should print 5:");
System.out.println(sparseArray.getValueAt(3, 3)); // Should print 5 (shifted from column 4 to 3)
System.out.println("Should print 7:");
System.out.println(sparseArray.getValueAt(2, 2)); // Should print 7 (shifted from column 3 to 2)
}
}
Main.main(null);
Original Array
Should print 3:
3
Should print 5:
5
Should print 7:
7
Shifted Array
Should print 3:
3
Should print 5:
5
Should print 7:
0
Question 4
Type: Classes
Blog This question made me think a lot about how to impliment classes and how the Java’s object-oriented structure could be put to use in different ways to make it a more beneficial programming language. This question explored the implementation of interfaces and the composite pattern through the NumberGroup interface and its implementations, while challenging me to apply these concepts to create a flexible system for checking if numbers belong to any of a collection of ranges, which demonstrates the power of abstraction and composition in object-oriented design.
Part A
| Create an Interface - Make an interface : |
public interface NumberGroup
{
public boolean contains(int num);
}
// Testing Stuff
public class Range implements NumberGroup {
private int min;
private int max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
@Override
public boolean contains(int num) {
return num >= min && num <= max;
}
}
public class Main {
public static void main(String[] args) {
NumberGroup range = new Range(5, 10);
System.out.println(range.contains(5)); // true
System.out.println(range.contains(10)); // true
System.out.println(range.contains(7)); // true
System.out.println(range.contains(4)); // false
System.out.println(range.contains(11)); // false
}
}
Main.main(null);
true
true
true
false
false
Part B
Implementing Interface - Implement the NumberGroup interface in a Range class to check if a number is within a range.
Whelp, I accedentally did that implimentation without realizing it! Here it is, reimplimented in a different way:
public class Range implements NumberGroup
{
private int[] list;
public Range(int min, int max)
{
list = new int[Math.abs(max-min+1)];
for(int i = 0; i < list.length; i++)
list[i] = min + i;
}
public boolean contains(int num)
{
for(int n: list)
if(num == n)
return true;
return false;
}
}
// Testing Stuff
public class Main {
public static void main(String[] args) {
NumberGroup range = new Range(5, 10);
System.out.println(range.contains(5)); // true
System.out.println(range.contains(10)); // true
System.out.println(range.contains(7)); // true
System.out.println(range.contains(4)); // false
System.out.println(range.contains(11)); // false
}
}
Main.main(null);
true
true
true
false
false
Part C
Composite Group - Create a MultipleGroups class that holds multiple NumberGroup objects and checks if a number is in any of the groups.
public boolean contains(int num)
{
for(NumberGroup n : groupList)
if(n.contains(num))
return true;
return false;
}
// Testing
public class MultipleGroups {
public static void main(String[] args) {
Range range1 = new Range(1, 5);
Range range2 = new Range(10, 15);
Range range3 = new Range(20, 25);
System.out.println(range1.contains(3)); // true (3 is in the range 1-5)
System.out.println(range2.contains(9)); // false (9 is not in the range 10-15)
System.out.println(range3.contains(12)); // false (12 is not in the range 20-25)
System.out.println(range1.contains(20)); // false (20 is not in the range 1-5)
System.out.println(range3.contains(30)); // false (30 is not in the range 20-25)
}
}
MultipleGroups.main(null);
true
false
false
false
false