12 problems with worked solutions and 9-point rubrics. Use Java with java.util imports. Advanced CS is a school honors course; these are Code Scholars practice problems.
Problem 1 · Java Design and Encapsulation · 20 minutes · 9 points
Protect a score collection
A ScoreBook owns a fixed collection of integer scores. Clients must not be able to modify its internal array through the constructor argument or a getter. Null constructor input is invalid. An empty collection has average 0.0. Assume the sum fits in a Java long.
A. Implement the constructor and getScores so neither exposes the internal array.
B. Implement average without integer division.
C. Write a test that would expose an aliasing bug and state the time and auxiliary space costs of each operation.
public static class ScoreBook {
private final int[] scores;
public ScoreBook(int[] input) { /* implement */ }
public int[] getScores() { /* implement */ }
public double average() { /* implement */ }
}
Show worked solution and rubric
public static class ScoreBook {
private final int[] scores;
public ScoreBook(int[] input) {
if (input == null) throw new IllegalArgumentException("null scores");
scores = input.clone();
}
public int[] getScores() { return scores.clone(); }
public double average() {
if (scores.length == 0) return 0.0;
long total = 0;
for (int score : scores) total += score;
return (double) total / scores.length;
}
}
The constructor and getter each create a new array. The final field prevents reassignment of the reference; it does not make the array itself immutable.
Create a book from [80, 90], then change the input array and the returned getter array. The book must still return [80, 90] and average 85.0. [1, 2] must average 1.5.
For n scores: construction is O(n) time and O(n) additional storage; getScores is O(n) time and O(n) output storage; average is O(n) time and O(1) auxiliary space.
Scoring rubric
3 points: rejects null, copies input, and returns a copy.
3 points: handles empty input, uses a safe sum, and performs floating-point division.
3 points: tests both alias paths and explains the operation costs.
Implement countEven(a, index), returning the number of even values from index through the end of a non-null array. The precondition is 0 <= index <= a.length. Use recursion and no loops, array copies, or mutable global state.
A. Write countEven.
B. Trace countEven(new int[]{-2, 3, 0, 8}, 0), showing the contribution of each call.
C. Explain termination, then give time and stack-space complexity in terms of the number of remaining elements.
public static int countEven(int[] a, int index) { /* implement */ }
Show worked solution and rubric
public static int countEven(int[] a, int index) {
if (index == a.length) return 0;
int contribution = a[index] % 2 == 0 ? 1 : 0;
return contribution + countEven(a, index + 1);
}
The contributions are 1, 0, 1, 1, followed by the base case 0. Returning up the stack gives 1, 2, 2, 3; the final answer is 3.
Each call increases index by one. The nonnegative number a.length - index decreases until it reaches zero. An empty suffix returns 0 without accessing the array.
For m remaining elements, time is O(m) and stack space is O(m). Java does not guarantee tail-call optimization. Negative even values and zero both satisfy remainder == 0.
Scoring rubric
3 points: correct base case, even test, and combination of results.
3 points: correct trace and final count of 3.
3 points: decreasing measure and both complexity bounds.
Problem 3 · Sorting, Searching, and Efficiency · 25 minutes · 9 points
Find the first qualifying score
Given a non-null ascending int array, firstAtLeast must return the first index whose value is at least target, or a.length if none exists. Duplicates are allowed. Also implement a stable in-place insertion sort for preparing an unsorted array.
A. Implement firstAtLeast using binary search, including empty arrays.
B. Implement insertionSort. Explain why equal elements retain their relative order.
C. Trace firstAtLeast on [2, 4, 4, 9] for target 4. Give both algorithms’ time and auxiliary space costs.
public static int firstAtLeast(int[] a, int target) { /* implement */ }
public static void insertionSort(int[] a) { /* implement */ }
Show worked solution and rubric
public static int firstAtLeast(int[] a, int target) {
int lo = 0, hi = a.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= target) hi = mid;
else lo = mid + 1;
}
return lo;
}
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
For target 4, the half-open search bounds (lo, hi) change from (0, 4) to (0, 2), (0, 1), then (1, 1). Return 1, the first 4.
Values strictly greater than key shift right. Equal values do not shift past key; that strict comparison preserves the order of equal keys.
Binary search takes O(log n) time for nonempty input and O(1) auxiliary space. Insertion sort has O(n) best-case and O(n²) worst-case time, with O(1) auxiliary space.
Scoring rubric
3 points: binary search returns the leftmost qualifying index or length.
3 points: correct insertion sort with a strict greater-than comparison.
3 points: trace, stability explanation, and complexity bounds.
Implement removeAll for a finite, acyclic singly linked list of integers. Remove every node equal to key and return the new head. Relink existing nodes; do not copy retained values into a new list.
Before removal: head points to the first 4.
A. Implement removeAll, including empty lists and consecutive matches at the head.
B. Draw the references before and after removing 4 from 4 → 4 → 2 → 4 → null.
C. Explain your loop invariant and give time and auxiliary space bounds.
public static class ListNode {
int value; ListNode next;
ListNode(int value, ListNode next) { this.value = value; this.next = next; }
}
public static ListNode removeAll(ListNode head, int key) { /* implement */ }
Show worked solution and rubric
public static class ListNode {
int value; ListNode next;
ListNode(int value, ListNode next) { this.value = value; this.next = next; }
}
public static ListNode removeAll(ListNode head, int key) {
ListNode dummy = new ListNode(0, head);
ListNode previous = dummy;
while (previous.next != null) {
if (previous.next.value == key) previous.next = previous.next.next;
else previous = previous.next;
}
return dummy.next;
}
The result is the original node containing 2, whose next reference becomes null. No retained data node is allocated.
All retained nodes through previous have been checked and do not equal key; previous.next is the next unchecked node. After deletion, previous stays in place so a consecutive match is not skipped.
Each iteration removes or passes one original node. Time is O(n); auxiliary space is O(1), including the single dummy node. If every node matches, dummy.next becomes null.
After removal: the original node containing 2 points to null.
Scoring rubric
3 points: removes head, internal, tail, and consecutive matches.
3 points: accurate before/after references without copying retained nodes.
3 points: invariant, termination, O(n) time and O(1) space.
Implement evaluatePostfix for a valid nonempty postfix expression. Tokens are signed decimal integers or the operators +, -, and *. Use a Deque<Integer> as a stack. Every operation and the final result fit in int. The expression leaves exactly one value.
Immediately before subtraction: 3 is the top/right operand; 8 is the left operand.
A. Implement the evaluator.
B. Show the stack, bottom to top, after each token in ["8", "3", "-", "2", "*"].
C. Explain why operand order matters and give time and auxiliary space bounds for n tokens, assuming fixed-width integer tokens.
public static int evaluatePostfix(String[] tokens) { /* implement */ }
Show worked solution and rubric
public static int evaluatePostfix(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*")) {
int right = stack.pop(), left = stack.pop();
if (token.equals("+")) stack.push(left + right);
else if (token.equals("-")) stack.push(left - right);
else stack.push(left * right);
} else stack.push(Integer.parseInt(token));
}
return stack.pop();
}
Bottom-to-top snapshots: [8], [8, 3], [5], [5, 2], [10]. The result is 10.
The most recently pushed value is the right operand. Reversing the operands changes subtraction: 8 - 3 is 5, not -5. A token such as -3 is an integer, not the single-character operator -.
Each token is processed once, with constant-time stack operations. Time is O(n), and the stack uses O(n) space in the worst case.
Scoring rubric
3 points: parses integers, recognizes operators, and uses the stack correctly.
3 points: correct operand order and all five trace snapshots.
3 points: explains signed tokens and O(n) time/space.
A FIFO queue contains Job objects with an id and a positive remaining count. serveRound processes exactly the jobs present when the method starts. Remove each once, subtract one from remaining, and re-enqueue it only if work remains. Return the processed IDs in order. Use the same Job objects and preserve FIFO order.
Initial queue: front at left, back at right.
A. Implement serveRound.
B. Trace the initial queue [A:2, B:1, C:3], front to back. Give the returned IDs and final queue.
C. Explain why while (!queue.isEmpty()) is incorrect here and give complexity in terms of the initial queue length k.
public static class Job {
String id; int remaining;
Job(String id, int remaining) { this.id = id; this.remaining = remaining; }
}
public static List<String> serveRound(Queue<Job> queue) { /* implement */ }
Show worked solution and rubric
public static class Job {
String id; int remaining;
Job(String id, int remaining) { this.id = id; this.remaining = remaining; }
}
public static List<String> serveRound(Queue<Job> queue) {
int initialSize = queue.size();
List<String> processed = new ArrayList<>();
for (int i = 0; i < initialSize; i++) {
Job job = queue.remove();
processed.add(job.id);
job.remaining--;
if (job.remaining > 0) queue.add(job);
}
return processed;
}
The returned IDs are [A, B, C]. Queue states are [B:1, C:3, A:1], then [C:3, A:1], then [A:1, C:2].
A loop that waits for an empty queue also processes jobs re-enqueued during this round. It may finish all work rather than giving each initial job one turn.
Assuming an ArrayDeque queue: O(k) time, O(k) output space, and O(1) auxiliary space excluding the returned list. An initially empty queue returns an empty list.
After one round: B has completed; A and C remain in FIFO order.
Scoring rubric
3 points: captures initial size and processes each original job once.
3 points: decrements, re-enqueues unfinished jobs, and traces FIFO correctly.
3 points: empty case and accurate time/output/auxiliary-space costs.
Each inner list contains the student IDs recorded during one session. A student may appear several times in that session and should count only once. Write attendanceCounts to return a map from student ID to the number of sessions attended. Inputs and IDs are non-null; sessions may be empty.
A. Implement attendanceCounts using a set for each session and a map for totals.
B. Give the result for [["Ana", "Ana", "Ben"], ["Ben", "Cara"], []]. Map iteration order does not matter.
C. Explain the different jobs of the set and map, and analyze expected time and space for T input entries, U unique IDs, and largest session size S.
public static Map<String, Integer> attendanceCounts(List<List<String>> sessions) {
Map<String, Integer> totals = new HashMap<>();
for (List<String> session : sessions) {
Set<String> seen = new HashSet<>();
for (String id : session) {
if (seen.add(id)) totals.put(id, totals.getOrDefault(id, 0) + 1);
}
}
return totals;
}
The result is {Ana=1, Ben=2, Cara=1}. The first Ana increments the map; the repeated Ana in the same session does not.
The set represents membership in the current session. It must be reset between sessions. The map stores counts across all sessions.
With expected constant-time hash operations and treating ID hashing as constant: O(T + N) time for N sessions, including empty sessions. Storage is O(U + S), counting the returned map and the current set.
Scoring rubric
3 points: a fresh set per session and one increment per distinct ID.
3 points: correct totals and safe initialization of missing keys.
3 points: explains roles, expected hash costs, and empty-session overhead.
An Integer[] table uses null for empty slots and linear probing with no deletions. The positive-length table was built using the same insertion rule. Hash key using Math.floorMod(key, table.length). Return an existing key’s index if present; otherwise insert at the first empty slot. Return -1 if a new key cannot fit. Zero and negative keys are valid.
A. Implement insertLinear with wraparound and a bounded probe sequence.
B. Starting with five empty slots, insert 4, 9, and -1 in order. Show the resulting array.
C. Explain duplicate handling, why a zero sentinel would fail, and worst-case time and auxiliary space.
public static int insertLinear(Integer[] table, int key) { /* implement */ }
Show worked solution and rubric
public static int insertLinear(Integer[] table, int key) {
int start = Math.floorMod(key, table.length);
for (int step = 0; step < table.length; step++) {
int index = (int) (((long) start + step) % table.length);
if (table[index] == null) {
table[index] = key;
return index;
}
if (table[index].intValue() == key) return index;
}
return -1;
}
All three keys hash to index 4. The insertions occupy indices 4, 0, and 1, so the final array is [9, -1, null, null, 4].
Existing equal keys return their index without inserting a duplicate. Because there are no deletions and all keys follow this insertion rule, an existing key cannot lie beyond the first empty slot in its probe sequence.
Null separates empty from every valid integer, including zero. With capacity m, at most m slots are examined: O(m) worst-case time and O(1) auxiliary space. The bounded loop terminates on a full table.
Scoring rubric
3 points: correct hash, wraparound, and at most capacity probes.
3 points: handles null, duplicates, zero, negative keys, and full tables.
3 points: correct trace and complexity explanation.
Problem 9 · Binary Search Trees · 20 minutes · 9 points
Count keys in a range
A binary search tree contains unique int keys. For every node, all left keys are smaller and all right keys are larger. Implement countRange(root, low, high) to count keys in the inclusive interval, with low <= high. Skip subtrees that cannot contain qualifying keys.
BST with unique keys. Count keys in the inclusive range [4, 10].
A. Implement countRange recursively with pruning.
B. For the pictured tree, count the keys in [4, 10] and identify a subtree that may be skipped.
C. Explain the pruning rules and give worst-case time and stack space in terms of n nodes and tree height h.
public static class TreeNode {
int key; TreeNode left, right;
TreeNode(int key) { this.key = key; }
}
public static int countRange(TreeNode root, int low, int high) { /* implement */ }
Show worked solution and rubric
public static class TreeNode {
int key; TreeNode left, right;
TreeNode(int key) { this.key = key; }
}
public static int countRange(TreeNode root, int low, int high) {
if (root == null) return 0;
if (root.key < low) return countRange(root.right, low, high);
if (root.key > high) return countRange(root.left, low, high);
return 1 + countRange(root.left, low, high)
+ countRange(root.right, low, high);
}
The qualifying keys are 4, 6, 7, 8, and 10: count 5. At node 3, skip its left subtree containing 1. At node 14, skip its right subtree (empty in this example).
If root.key < low, root and every key to its left are too small. If root.key > high, root and every key to its right are too large. Otherwise count root and search both sides.
Worst-case time is O(n), such as a range covering the entire tree. Stack space is O(h): O(log n) for a balanced tree, but O(n) for a chain. Do not claim every BST operation is always logarithmic.
Scoring rubric
3 points: null case, inclusive endpoints, and correct counts.
3 points: prunes only impossible subtrees and gives the count of 5.
3 points: justification and O(n) worst-case time/O(h) stack.
A max-heap is stored in a zero-based int array. The active heap occupies indices 0 through size - 1. For siftDown, index is valid and both child subtrees are already max-heaps; only the value at index may violate heap order. Implement siftDown and an in-place buildMaxHeap for any non-null array.
Before siftDown: the two child subtrees are heaps, but 3 is smaller than its children.
A. Implement siftDown, choosing the larger child at each step.
B. Implement buildMaxHeap using bottom-up heap construction.
C. Trace siftDown([3, 9, 7, 8, 2], 5, 0). Explain the complexity of each method and distinguish heap order from sorted order.
public static void siftDown(int[] a, int size, int index) { /* implement */ }
public static void buildMaxHeap(int[] a) { /* implement */ }
Show worked solution and rubric
public static void siftDown(int[] a, int size, int index) {
while (index < size / 2) {
int child = 2 * index + 1;
if (child + 1 < size && a[child + 1] > a[child]) child++;
if (a[index] >= a[child]) return;
int temp = a[index]; a[index] = a[child]; a[child] = temp;
index = child;
}
}
public static void buildMaxHeap(int[] a) {
for (int i = a.length / 2 - 1; i >= 0; i--) siftDown(a, a.length, i);
}
Swap 3 with the larger child 9: [9, 3, 7, 8, 2]. Then swap 3 with 8: [9, 8, 7, 3, 2].
Bottom-up construction starts with the last parent and moves toward the root. Each call has heap-ordered child subtrees because their roots were handled earlier.
siftDown takes O(log n) worst-case time; bottom-up buildMaxHeap takes O(n) time because most nodes are close to leaves. Both use O(1) auxiliary space. A max-heap guarantees parent >= children; siblings and separate subtrees need not be sorted.
After siftDown: max-heap order is restored.
Scoring rubric
3 points: selects larger child, swaps correctly, and respects size.
3 points: bottom-up build starts at the last parent and handles empty input.
3 points: correct trace, O(log n)/O(n) distinction, and heap-order explanation.
A graph uses vertices 0 through n - 1 and adjacency lists. All edges have equal cost. Implement shortestPath(graph, start, goal), returning one shortest path as vertex IDs, or an empty list if unreachable. Inputs and indices are valid. Cycles and disconnected components are allowed; do not change the graph.
Undirected graph: 0 to 3 has two paths of length 2; vertex 4 is isolated.
A. Implement BFS with a queue and a predecessor array. Mark a vertex when it is enqueued.
B. Reconstruct the path after reaching the goal. What happens when start equals goal?
C. For adjacency lists [[1,2],[0,3],[0,3],[1,2],[]], find a path from 0 to 3 and explain why DFS does not generally guarantee a shortest path. Analyze time and space.
public static List<Integer> shortestPath(List<List<Integer>> graph, int start, int goal) { /* implement */ }
Show worked solution and rubric
public static List<Integer> shortestPath(List<List<Integer>> graph, int start, int goal) {
int[] parent = new int[graph.size()];
Arrays.fill(parent, -1);
Queue<Integer> queue = new ArrayDeque<>();
parent[start] = start;
queue.add(start);
while (!queue.isEmpty()) {
int vertex = queue.remove();
if (vertex == goal) break;
for (int next : graph.get(vertex)) {
if (parent[next] == -1) {
parent[next] = vertex;
queue.add(next);
}
}
}
List<Integer> path = new ArrayList<>();
if (parent[goal] == -1) return path;
for (int at = goal; at != start; at = parent[at]) path.add(at);
path.add(start);
Collections.reverse(path);
return path;
}
For the listed neighbor order, BFS discovers 1 then 2 from 0, and discovers 3 from 1. The path is [0, 1, 3]. [0, 2, 3] is equally short.
BFS explores vertices by increasing edge distance, so the first discovery gives a shortest unweighted path. DFS may explore a long branch before a short one.
parent doubles as a visited marker; marking on enqueue prevents duplicate queue entries. start == goal returns [start]. An unreachable goal returns []. With adjacency lists, worst-case time is O(V + E), and auxiliary space is O(V).
Scoring rubric
3 points: FIFO BFS, marks on enqueue, and handles cycles.
3 points: reconstructs a valid path and handles same/unreachable endpoints.
3 points: correct example, BFS shortest-path argument, and O(V + E)/O(V) bounds.
Problem 12 · Computing and Society · 20 minutes · 9 points
Audit an automated placement system
A school uses a model to recommend students for advanced CS. On a held-out set, 100 qualified students in Group A include 20 rejected by the model; 100 qualified students in Group B include 40 rejected. Qualification was assessed independently of the model. The team proposes automatic rejection without appeal and indefinite storage of student records.
A. Compute each group’s false-negative rate and the difference in percentage points. Explain what this evidence does and does not establish.
B. Propose two concrete changes before deployment: one addressing placement harm and one addressing privacy. Explain how each reduces harm.
C. Design a monitoring and appeal process, including a measurable outcome to track. Explain one tradeoff.
Write a response labeled A, B, and C. Use the supplied counts and name the decisions your recommendations would change.
Show worked solution and rubric
A. False-negative rates among qualified students are 20/100 = 20% for Group A and 40/100 = 40% for Group B. The gap is 20 percentage points. Group B’s measured rate is twice Group A’s. These data show a disparity in this sample; they do not establish its cause, the false-positive rates, overall accuracy, or performance on future cohorts.
B. Require human review of negative recommendations and a documented appeal route before denying access. Audit labels and group-specific errors; test revised thresholds on held-out data. For privacy, collect only necessary fields, restrict access by role, and set a justified deletion schedule rather than indefinite retention.
C. Track group-specific false-negative rates and appeal reversals each term using an independent qualification assessment, with sample sizes and uncertainty. Investigate a pre-agreed disparity threshold and pause automatic adverse decisions if harm persists. Human review adds time and staffing cost, but reduces the risk of an unchallengeable mistaken rejection.
Scoring rubric
3 points: 20%, 40%, a 20-percentage-point gap, and limits of the evidence.
3 points: actionable placement safeguard and a justified privacy control.
3 points: measurable monitoring, meaningful appeal, and an explicit tradeoff.
