Problem 2 · Arrays, Strings, and Pattern Techniques · 9 points
Find the longest target-sum window
Implement longestSum(int[] a, long target) returning the length of the longest contiguous subarray whose sum equals target. Values may be negative. Empty input returns 0; a length-zero answer is allowed. Assume prefix sums and their differences fit long.
A. Use prefix sums and a hash map of earliest indices.
B. Trace [1,-1,5,-2,3] with target 3.
C. Explain why a nonnegative sliding-window rule fails and analyze expected costs.
Show worked solution and rubric
public static int longestSum(int[] a, long target) {
Map<Long,Integer> first = new HashMap<>();
first.put(0L, -1);
long prefix = 0;
int best = 0;
for (int i = 0; i < a.length; i++) {
prefix += a[i];
Integer j = first.get(prefix - target);
if (j != null) best = Math.max(best, i - j);
first.putIfAbsent(prefix, i);
}
return best;
}
A. Store prefix zero at index -1. At index i, a prior prefix equal to current-target gives a valid subarray; keep its earliest index to maximize length.
B. The first four elements sum to 3, giving length 4. The complete array sums to 6; no length-5 solution exists.
C. Negative values can decrease a growing window sum, so moving one boundary by a sum comparison is unsound. Expected time O(n), map space O(n).
Scoring rubric
3 points: Store prefix zero at index -1
3 points: The first four elements sum to 3, giving length 4
3 points: Negative values can decrease a growing window sum, so moving one boundary by a sum comparison is unsound
Problem 4 · Hash Tables, Heaps, and Priority Structures · 9 points
Keep the kth largest value
Implement kthLargest(int[] a,int k), counting duplicates as separate values. Reject k<1 or k>a.length. Use a min-heap of at most k elements.
A. Implement and state the heap invariant.
B. Trace [5,1,5,3] for k = 2.
C. Compare with sorting and state time and storage costs.
Show worked solution and rubric
public static int kthLargest(int[] a, int k) {
if (k < 1 || k > a.length) throw new IllegalArgumentException("k");
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int value : a) {
heap.add(value);
if (heap.size() > k) heap.remove();
}
return heap.element();
}
A. After each prefix, keep its largest min(k,prefix length) elements. If insertion creates k+1 entries, removing the minimum discards an element outside the largest k.
B. After all values the heap contains [5,5], so the result is 5. Duplicates count independently.
C. Each heap operation takes O(log(k+1)); total O(n log(k+1)), auxiliary O(k). Sorting all input is O(n log n) and may mutate the array.
Scoring rubric
3 points: After each prefix, keep its largest min(k,prefix length) elements
3 points: After all values the heap contains [5,5], so the result is 5
3 points: Each heap operation takes O(log(k+1)); total O(n log(k+1)), auxiliary O(k)
Problem 5 · Trees and Balanced Search Structures · 9 points
Validate a strict binary search tree
A Node has int value and Node left,right. Implement validBst(Node root); duplicates are not allowed. Check global ancestry bounds, not just immediate children.
Invalid BST: 12 is in the left subtree of 10, although it exceeds 10.
A. Implement with open lower and upper bounds.
B. Explain why root 10, left child 5, and left-right grandchild 12 is invalid.
C. Explain integer endpoints and analyze balanced and skewed trees.
Show worked solution and rubric
public static class Node {
int value; Node left, right;
Node(int value) { this.value = value; }
}
public static boolean validBst(Node root) {
return within(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private static boolean within(Node node, long low, long high) {
if (node == null) return true;
if (node.value <= low || node.value >= high) return false;
return within(node.left, low, node.value) && within(node.right, node.value, high);
}
A. Pass an allowed open interval down the recursion: a left child inherits the lower bound and parent value as upper; a right child inherits parent value as lower.
B. The value 12 belongs to the entire left subtree of 10 and must be below 10, even though it is above its own parent 5.
C. Use long bounds to permit Integer.MIN_VALUE and MAX_VALUE as legitimate nodes. Time O(n), stack O(h): O(log n) balanced and O(n) skewed.
Scoring rubric
3 points: Pass an allowed open interval down the recursion: a left child inherits the lower bound and parent value as upper; a right child inherits parent value as lower.
3 points: The value 12 belongs to the entire left subtree of 10 and must be below 10, even though it is above its own parent 5.
3 points: Use long bounds to permit Integer.MIN_VALUE and MAX_VALUE as legitimate nodes
Problem 6 · Graphs and Network Algorithms · 9 points
Order prerequisite tasks
A directed graph uses outgoing adjacency lists: u -> v means u must finish before v. Implement order(graph) returning a topological order, or an empty list if a cycle exists. For an empty graph, return an empty list.
A. Implement Kahn’s algorithm with indegrees.
B. Trace [[2],[2],[]] and [[1],[0]].
C. Explain cycle detection and time/space costs.
Show worked solution and rubric
public static List<Integer> order(List<List<Integer>> graph) {
int n = graph.size(); int[] indegree = new int[n];
for (List<Integer> edges : graph) for (int v : edges) indegree[v]++;
Queue<Integer> ready = new ArrayDeque<>();
for (int v = 0; v < n; v++) if (indegree[v] == 0) ready.add(v);
List<Integer> result = new ArrayList<>();
while (!ready.isEmpty()) {
int u = ready.remove(); result.add(u);
for (int v : graph.get(u)) if (--indegree[v] == 0) ready.add(v);
}
return result.size() == n ? result : new ArrayList<>();
}
A. Compute all indegrees, enqueue zero-indegree vertices, and remove their outgoing edges when processed. Enqueue a neighbor exactly when its indegree reaches zero.
B. A valid first output is [0,1,2]. The second graph has a cycle and no initial zero-indegree vertex, so output is empty.
C. If fewer than V vertices are removed, the remaining subgraph contains a directed cycle. Time O(V+E); indegrees, queue, and result occupy O(V).
Scoring rubric
3 points: Compute all indegrees, enqueue zero-indegree vertices, and remove their outgoing edges when processed
3 points: A valid first output is [0,1,2]
3 points: If fewer than V vertices are removed, the remaining subgraph contains a directed cycle
Implement merge(int[] left,int[] right) returning a new sorted array. Both inputs are already nondecreasing. If values tie, choose the left value first. Assume their combined length fits an array.
A. Implement the two-pointer merge.
B. Trace left=[1,3,3], right=[2,3]. Label origins on paper.
C. Explain stability, empty inputs, and costs.
Show worked solution and rubric
public static int[] merge(int[] left, int[] right) {
int[] out = new int[left.length + right.length];
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length)
out[k++] = left[i] <= right[j] ? left[i++] : right[j++];
while (i < left.length) out[k++] = left[i++];
while (j < right.length) out[k++] = right[j++];
return out;
}
A. Maintain pointers to the first unread item in each array. Choose <= from the left on a tie and copy the remaining tail after either input is exhausted.
B. The origins are 1L,2R,3L,3L,3R. The values are [1,2,3,3,3]. The ordering inside each input is preserved.
C. Choosing left on equality preserves relative order across consecutive sorted runs. Empty inputs copy the other input. Time O(n+m); output O(n+m), auxiliary workspace excluding output O(1).
Scoring rubric
3 points: Maintain pointers to the first unread item in each array
3 points: The origins are 1L,2R,3L,3L,3R
3 points: Choosing left on equality preserves relative order across consecutive sorted runs
Implement minCoins(int[] coins,int amount) for positive coin values and nonnegative amount. Unlimited copies are available. Return -1 if impossible. Assume amount <=10000.
A. Give a bottom-up dynamic programming solution.
B. Trace coins=[1,3,4], amount=6 and compare greedy.
C. State the recurrence, base case, and complexity.
Show worked solution and rubric
public static int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins) if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
A. dp[x] is the minimum coins for exact amount x. Initialize dp[0]=0 and other entries to a sentinel amount+1; test every coin not exceeding x.
B. The optimal answer is 2 using 3+3. Taking the largest first gives 4+1+1, so greedy uses 3 coins and is not optimal.
C. The recurrence is dp[x]=min(dp[x-c]+1) over allowed coins c<=x. Time O(amount*number of coins), space O(amount). A sentinel final value means unreachable.
Scoring rubric
3 points: dp[x] is the minimum coins for exact amount x
3 points: The optimal answer is 2 using 3+3
3 points: The recurrence is dp[x]=min(dp[x-c]+1) over allowed coins c<=x
