Question 1
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.
This question involves reasoning about one-dimensional and two-dimensional arrays of integers. You will write three static methods, all of which are in a single enclosing class, named DiverseArray (not shown). The first method returns the sum of the values of a one-dimensional array; the second method returns an array that represents the sums of the rows of a two-dimensional array; and the third method analyzes row sums.
(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.
Complete method arraySum below.
/ * * Returns the sum of the entries in the one-dimensional array arr.
- /
public static int arraySum (int [ ] arr)
public class partA {
public static int arraySum (int[] arr) {
int sum = 0;
for (int i = 0; i < arr.length; i ++) {
sum += arr[i];
}
return sum;
}
public static void main(String[] args) {
int[] array = {1, 3, 2, 7, 3};
int sum = arraySum(array);
System.out.println("Sum: " + sum);
}
}
partA.main(null);
Sum: 16
(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}.
Assume that arraySum works as specified, regardless of what you wrote in part (a). You must use arraySum appropriately to receive full credit.
Complete method rowSums below.
/ * * Returns a one-dimensional array in which the entry at index k is the sum of
-
the entries of row k of the two-dimensional array arr2D.
-
/
public static int [ ] rowSums(int [ ] [ ] arr2D)
public class partB {
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 rows = arr2D.length;
int[] sums = new int[rows];
for (int r = 0; r < rows; r ++) {
sums[r] = arraySum(arr2D[r]);
}
return sums;
}
public static String arrToString(int[] arr) {
String output = "[";
for (int i = 0; i < arr.length; i ++) {
output += Integer.toString(arr[i]);
if (i != arr.length - 1) {
output += ", ";
}
}
output += "]";
return output;
}
public static void main(String[] args) {
int[][] arr2D = {
{1, 3, 2, 7, 3},
{10, 10, 4, 6, 2},
{5, 3, 5, 9, 6},
{7, 6, 4, 2, 1}
};
int[] sums = rowSums(arr2D);
System.out.println("Sum of each row:");
System.out.println(arrToString(sums));
}
}
partB.main(null);
Sum of each row:
[16, 32, 28, 20]
(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.
Assume that arraySum and rowSums work as specified, regardless of what you wrote in parts (a) and(b). You must use rowSums appropriately to receive full credit. Complete method isDiverse below.
/ * * Returns true if all rows in arr2D have different row sums;
-
false otherwise.
-
/public static boolean isDiverse(int [ ] [ ] arr2D)
public class partC {
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 rows = arr2D.length;
int[] sums = new int[rows];
for (int r = 0; r < rows; r ++) {
sums[r] = arraySum(arr2D[r]);
}
return sums;
}
public static String arrToString(int[] arr) {
String output = "[";
for (int i = 0; i < arr.length; i ++) {
output += Integer.toString(arr[i]);
if (i != arr.length - 1) {
output += ", ";
}
}
output += "]";
return output;
}
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;
}
public static void main(String[] args) {
int[][] arr1 = {
{1, 3, 2, 7, 3},
{10, 10, 4, 6, 2},
{5, 3, 5, 9, 6},
{7, 6, 4, 2, 1}
};
int[][] arr2 = {
{1, 1, 5, 3, 4},
{12, 7, 6, 1, 9},
{8, 11, 10, 2, 5},
{3, 2, 3, 0, 6}
};
System.out.println("Is the first 2D array diverse?");
System.out.println("Array: " + arrToString(rowSums(arr1)));
System.out.println("Diverse: " + isDiverse(arr1));
System.out.println();
System.out.println("Is the second 2D array diverse?");
System.out.println("Array: " + arrToString(rowSums(arr2)));
System.out.println("Diverse: " + isDiverse(arr2));
}
}
partC.main(null);
Is the first 2D array diverse?
Array: [16, 32, 28, 20]
Diverse: true
Is the second 2D array diverse?
Array: [14, 35, 36, 14]
Diverse: false
Reflection:
Being the first time using Java by itself in a while, I had a couple syntax errors. Need to remember that using .length does not have parentheses and other minor stuff like that.
In terms of the question itself, it was really easy.
The types are as follows:
- part a was arrays
- part b was 2d arrays
- part c is method/control structures
Question 2
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.
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.
Solution:
public class HiddenWord {
public String secret;
// just public to be used as a constructor
public HiddenWord(String word) {
this.secret = word;
}
public String getHint(String guess) {
String word = this.secret;
String hint = "";
int len = word.length();
// Not necessary but I felt like it
if (len != guess.length()) {
return "Invalid guess";
}
for (int i = 0; i < len; i ++) {
char guessChar = guess.charAt(i);
char wordChar = word.charAt(i);
if (word.indexOf(guessChar) != -1) {
if (wordChar == guessChar) {
hint += guessChar;
}
else {
hint += "+";
}
}
else {
hint += "*";
}
}
return hint;
}
}
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"));
+A+++
H****
H*++*
HAR*S
HARPS
Reflection
Again, the code itself wasn’t hard, just syntax stuff. This time, it was with making a constructor, where I autopiloted and added “void” to it, which makes Java treat it as a method instead of a contructor.
This one’s type was method and control structures. Woo.
Question 3
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.
(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.
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 addEntry(SparseArrayEntry entry)
{
entries.add(entry);
}
public int getNumRows()
{ return numRows; }
public int getNumCols()
{ return numCols; }
public int getValueAt(int row, int col) {
for (int i = 0; i < entries.size(); i ++) {
SparseArrayEntry entry = entries.get(i);
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
}
// dont care if theres a better way im lazy rn
SparseArray sparse = new SparseArray();
SparseArrayEntry entry1 = new SparseArrayEntry(1, 4, 4);
SparseArrayEntry entry2 = new SparseArrayEntry(2, 0, 1);
SparseArrayEntry entry3 = new SparseArrayEntry(3, 1, -9);
SparseArrayEntry entry4 = new SparseArrayEntry(1, 1, 5);
sparse.addEntry(entry1);
sparse.addEntry(entry2);
sparse.addEntry(entry3);
sparse.addEntry(entry4);
// Test
sparse.getValueAt(2, 0);
1
(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*
The shaded entries in entries, below, correspond to the shaded column above.
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 addEntry(SparseArrayEntry entry)
{
entries.add(entry);
}
public int getNumRows()
{ return numRows; }
public int getNumCols()
{ return numCols; }
public int getValueAt(int row, int col)
{
for (int i = 0; i < entries.size(); i ++) {
SparseArrayEntry entry = entries.get(i);
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
public void removeColumn(int col)
{
for (int i = 0; i < entries.size(); i ++) {
if (entries.get(i).getCol() == col) {
entries.remove(i);
i --;
}
}
}
}
// dont care if theres a better way im lazy rn
SparseArray sparse = new SparseArray();
SparseArrayEntry entry1 = new SparseArrayEntry(1, 4, 4);
SparseArrayEntry entry2 = new SparseArrayEntry(2, 0, 1);
SparseArrayEntry entry3 = new SparseArrayEntry(3, 1, -9);
SparseArrayEntry entry4 = new SparseArrayEntry(1, 1, 5);
sparse.addEntry(entry1);
sparse.addEntry(entry2);
sparse.addEntry(entry3);
sparse.addEntry(entry4);
// Test
System.out.println("Before running removeColumn()");
System.out.println(sparse.getValueAt(1, 1));
System.out.println(sparse.getValueAt(3, 1));
sparse.removeColumn(1);
System.out.println("After running removeColumn()");
System.out.println(sparse.getValueAt(1, 1));
System.out.println(sparse.getValueAt(3, 1));
Before running removeColumn()
5
-9
After running removeColumn()
0
0
Reflection
This one was actually pretty challenging because I didn’t expect to have to write my own method for adding entries to the sparse array. Also its a data structure I’m unfamiliar with. Didn’t have any syntax issues this time, but did encounter an issue when writing the removeColumn() method, as I didn’t realize I had to decrement i each time I removed something.
Type is methods and control structures & arrays
Question 4
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.
This question involves the design of an interface, writing a class that implements the interface, and writing a method that uses the interface.
(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 number);
}
(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 minimum;
private int maximum;
public Range(int min, int max)
{
minimum = min;
maximum = max;
}
@Override
public boolean contains(int number) {
if (minimum <= number && number <= maximum) {
return true;
}
else {
return false;
}
}
}
(c)
The MultipleGroups class (not shown) represents a collection of NumberGroup objects and isa NumberGroup. The MultipleGroups class stores the number groups in the instance variable groupList (shown below), which is initialized in the constructor.
private List
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 Range implements NumberGroup {
private int minimum;
private int maximum;
public Range(int min, int max)
{
minimum = min;
maximum = max;
}
@Override
public boolean contains(int number) {
if (minimum <= number && number <= maximum) {
return true;
}
else {
return false;
}
}
}
public class MultipleGroups implements NumberGroup {
private List<NumberGroup> groupList;
public MultipleGroups()
{
groupList = new ArrayList<NumberGroup>();
}
public void addNumberGroup(NumberGroup group)
{
groupList.add(group);
}
@Override
public boolean contains(int number)
{
for (int i = 0; i < groupList.size(); i ++)
{
if (groupList.get(i).contains(number))
{
return true;
}
}
return false;
}
}
MultipleGroups multiple1 = new MultipleGroups();
multiple1.addNumberGroup(new Range(5, 8));
multiple1.addNumberGroup(new Range(10, 12));
multiple1.addNumberGroup(new Range(1, 6));
System.out.println(multiple1.contains(2));
System.out.println(multiple1.contains(9));
System.out.println(multiple1.contains(6));
true
false
true
Reflection
Despite needing to learn how interfaces work, this was definitely the easiest one so far. Literally no syntax errors at all, and I came out of it knowing how interfaces work. This was a very cool FRQ because I learned a new data structure (interface) and got practice with inheritance.
Type: writing classes