Problem 1 · First Programs and Values · 9 points
Convert elapsed seconds
A nonnegative int total stores elapsed seconds. Implement describe(int total) returning hours:minutes:seconds as unpadded numbers.
- A. Implement the conversion with division and remainder.
- B. Trace total = 3665.
- C. Explain why integer division is appropriate and test zero and an exact hour.
Show worked solution and rubric
public static String describe(int total) {
int h = total / 3600;
int m = (total % 3600) / 60;
int s = total % 60;
return h + ":" + m + ":" + s;
}
- A. Divide by 3600 for full hours; divide the remainder by 60 for minutes. The final remainder is seconds.
- B. 3665 gives 1:1:5 because 3665 = 3600 + 60 + 5.
- C. Integer division removes partial units. Zero gives 0:0:0; 3600 gives 1:0:0.
Scoring rubric
- 3 points: Divide by 3600 for full hours; divide the remainder by 60 for minutes
- 3 points: 3665 gives 1:1:5 because 3665 = 3600 + 60 + 5.
- 3 points: Integer division removes partial units
Problem 2 · Making Decisions · 9 points
Classify a score
Implement grade(int score): return Invalid outside 0..100, A for 90..100, B for 80..89, and Other otherwise.
- A. Write the classifier with mutually exclusive branches.
- B. Give results for -1, 79, 80, 89, 90, 100, and 101.
- C. Explain why checking score >= 80 before score >= 90 would be wrong in an else-if chain.
Show worked solution and rubric
public static String grade(int score) {
if (score < 0 || score > 100) return "Invalid";
if (score >= 90) return "A";
if (score >= 80) return "B";
return "Other";
}
- A. Reject invalid inputs first, then test descending cutoffs so a wider range does not hide the A branch.
- B. The results are Invalid, Other, B, B, A, A, Invalid. Each cutoff must be tested on both sides.
- C. A score of 95 would satisfy >=80 first and incorrectly return B. Ordered branches stop after their first match.
Scoring rubric
- 3 points: Reject invalid inputs first, then test descending cutoffs so a wider range does not hide the A branch.
- 3 points: The results are Invalid, Other, B, B, A, A, Invalid
- 3 points: A score of 95 would satisfy >=80 first and incorrectly return B
Problem 3 · Repetition · 9 points
Sum multiples without overshooting
Implement sumMultiples(int n), the sum of positive multiples of 3 not exceeding n. Assume 0 <= n <= 10000.
- A. Implement the method with a loop.
- B. Trace n = 10 and n = 2.
- C. State a loop invariant and give time and auxiliary-space complexity.
Show worked solution and rubric
public static int sumMultiples(int n) {
int sum = 0;
for (int i = 3; i <= n; i += 3) sum += i;
return sum;
}
- A. Start at 3 and advance by 3 while the value is <=n. The bound includes an exact multiple.
- B. For 10, add 3,6,9 to obtain 18; for 2, no iterations occur and the result is 0.
- C. Before each iteration sum contains all positive multiples of 3 smaller than the current i. Time is O(n), auxiliary space O(1).
Scoring rubric
- 3 points: Start at 3 and advance by 3 while the value is <=n
- 3 points: For 10, add 3,6,9 to obtain 18; for 2, no iterations occur and the result is 0.
- 3 points: Before each iteration sum contains all positive multiples of 3 smaller than the current i
Problem 4 · Working With Text · 9 points
Collapse adjacent repeated characters
Implement collapse(String s) for a non-null string of basic Latin characters. Keep only the first character of each consecutive run; do not remove later nonadjacent occurrences.
- A. Implement collapse using StringBuilder.
- B. Trace "aaabbcca" and the empty string.
- C. Explain the boundary check and analyze time and auxiliary space.
Show worked solution and rubric
public static String collapse(String s) {
StringBuilder out = new StringBuilder();
for (int i = 0; i < s.length(); i++)
if (i == 0 || s.charAt(i) != s.charAt(i - 1)) out.append(s.charAt(i));
return out.toString();
}
- A. Append a character only when its index is zero or it differs from its predecessor. This compares original neighbors.
- B. The outputs are abca and the empty string. The last a is kept because it starts a new run.
- C. The i==0 short-circuit protects charAt(i-1). For n characters, time and result-builder storage are O(n); the input is unchanged.
Scoring rubric
- 3 points: Append a character only when its index is zero or it differs from its predecessor
- 3 points: The outputs are abca and the empty string
- 3 points: The i==0 short-circuit protects charAt(i-1)
Problem 5 · Collections of Values · 9 points
Copy passing scores
Implement passing(int[] scores) returning a new ArrayList<Integer> containing scores >=60 in original order. Input is non-null.
- A. Implement without changing the array.
- B. Trace [59,60,100,60] and explain duplicates.
- C. Give results for empty input and analyze complexity.
Show worked solution and rubric
public static ArrayList<Integer> passing(int[] scores) {
ArrayList<Integer> result = new ArrayList<>();
for (int score : scores) if (score >= 60) result.add(score);
return result;
}
- A. Traverse the array and append each value that satisfies the threshold. A new list prevents the result from changing the input.
- B. The result is [60,100,60]. Both 60 values remain because they are separate qualifying observations.
- C. Empty input returns an empty list. Time is O(n); the returned list requires O(k) space for k passing scores.
Scoring rubric
- 3 points: Traverse the array and append each value that satisfies the threshold
- 3 points: The result is [60,100,60]
- 3 points: Empty input returns an empty list
Problem 6 · Methods and Classes · 9 points
Maintain a bounded counter
Design Counter with positive capacity. It starts at zero. add() increments and returns true only when below capacity; otherwise it returns false. Expose getCount(), keeping fields private.
- A. Implement constructor, fields, add, and getter.
- B. Trace three calls to add for capacity 2.
- C. Explain the invariant and how clients are prevented from bypassing it.
Show worked solution and rubric
public static class Counter {
private final int capacity;
private int count;
public Counter(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity");
this.capacity = capacity;
}
public boolean add() {
if (count == capacity) return false;
count++;
return true;
}
public int getCount() { return count; }
}
- A. Validate capacity in the constructor, then protect both fields. The add method is the only operation that changes count.
- B. The returns are true,true,false and count ends at 2. A rejected call leaves count unchanged.
- C. The invariant is 0<=count<=capacity. Private fields and validated methods prevent direct assignment; nonpositive capacity is rejected.
Scoring rubric
- 3 points: Validate capacity in the constructor, then protect both fields
- 3 points: The returns are true,true,false and count ends at 2
- 3 points: The invariant is 0<=count<=capacity
