Problem 1 · Simulation · 9 points
Pour between two buckets
Implement pour(a,b,capacity_b), returning the new amounts after pouring as much as possible from A into B. All inputs are integers with a>=0 and 0<=b<=capacity_b.
- A. Implement a single pour without a loop.
- B. Trace (7,3,8) and then (2,8,8).
- C. Prove conservation of total volume and valid output bounds.
Show worked solution and rubric
def pour(a, b, capacity_b):
moved = min(a, capacity_b - b)
return a - moved, b + moved
- A. Transfer the smaller of a and the free capacity capacity_b-b. Subtract from A and add to B simultaneously.
- B. The first result is (2,8). The second is (2,8), because B is already full.
- C. The new total is (a-moved)+(b+moved)=a+b. Since moved<=a and moved<=capacity_b-b, neither amount becomes negative and B does not overflow.
Scoring rubric
- 3 points: Transfer the smaller of a and the free capacity capacity_b-b
- 3 points: The first result is (2,8)
- 3 points: The new total is (a-moved)+(b+moved)=a+b
Problem 2 · Complete Search and Brute Force · 9 points
Find the best affordable pair
Implement best_pair(prices,budget): choose exactly two distinct indices whose prices sum to at most budget, maximizing that sum. Prices and budget are nonnegative integers. Return -1 if no pair fits.
- A. Enumerate each unordered index pair exactly once.
- B. Trace prices=[4,7,4], budget=8.
- C. Explain why equal values can still be separate choices and give complexity.
Show worked solution and rubric
def best_pair(prices, budget):
best = -1
for i in range(len(prices)):
for j in range(i + 1, len(prices)):
total = prices[i] + prices[j]
if total <= budget:
best = max(best, total)
return best
- A. Use i<j, so no item is reused and each unordered pair appears once. Update the best sum only when it is affordable.
- B. The pair at indices 0 and 2 costs 8, which is optimal. Each pair involving 7 costs 11 and is too expensive.
- C. Equal prices at different indices represent different items. Time O(n²), auxiliary space O(1); fewer than two items return -1.
Scoring rubric
- 3 points: Use i<j, so no item is reused and each unordered pair appears once
- 3 points: The pair at indices 0 and 2 costs 8, which is optimal
- 3 points: Equal prices at different indices represent different items
Problem 3 · Sorting and Greedy Reasoning · 9 points
Minimize walking to a meeting point
Given integer positions on a line, choose an integer meeting point minimizing the sum of absolute walking distances. Implement meeting(positions), returning (point,total). Input is nonempty. Choose the lower median for ties.
- A. Implement using a sorted copy.
- B. Trace [1,2,10,12].
- C. Justify the median using paired endpoints and give costs.
Show worked solution and rubric
def meeting(positions):
ordered = sorted(positions)
point = ordered[(len(ordered) - 1) // 2]
return point, sum(abs(x - point) for x in ordered)
- A. Sort without changing input and choose index (n-1)//2. Sum absolute differences from that coordinate.
- B. The lower median is 2. Distances are 1,0,8,10, totaling 19; any point from 2 through 10 also minimizes the total.
- C. For each pair of extreme positions, every point between them gives the same minimum pair contribution. The middle interval or middle point satisfies all pairs. Time O(n log n), copy O(n).
Scoring rubric
- 3 points: Sort without changing input and choose index (n-1)//2
- 3 points: The lower median is 2
- 3 points: For each pair of extreme positions, every point between them gives the same minimum pair contribution
Problem 4 · Frequency Maps and Sets · 9 points
Find the earliest repeated tag
Implement first_repeat(tags), returning the first tag whose second appearance is encountered during a left-to-right scan. Return None if all tags are unique. Tags are strings.
- A. Implement using a set.
- B. Trace ["B","A","A","B"].
- C. Explain why choosing the alphabetically smallest duplicate or first distinct tag is wrong.
Show worked solution and rubric
def first_repeat(tags):
seen = set()
for tag in tags:
if tag in seen:
return tag
seen.add(tag)
return None
- A. Check membership before adding. The first already-seen tag is the earliest second occurrence.
- B. The result is A, whose second occurrence is index 2; B does not repeat until index 3.
- C. The problem is ordered by repeated appearance, not by alphabetical order or first appearance. Expected O(n) set operations and O(u) stored tags; string hashing also depends on tag lengths.
Scoring rubric
- 3 points: Check membership before adding
- 3 points: The result is A, whose second occurrence is index 2; B does not repeat until index 3.
- 3 points: The problem is ordered by repeated appearance, not by alphabetical order or first appearance
Problem 5 · Coordinate Geometry · 9 points
Measure rectangle overlap
Each axis-aligned rectangle is (x1,y1,x2,y2) with x1<x2 and y1<y2. Implement overlap(a,b), the positive intersection area or 0 for disjoint or touching rectangles.
- A. Derive overlap width and height with min and max.
- B. Trace A=(0,0,4,3), B=(2,1,6,5).
- C. Explain edge touching and containment; give costs.
Show worked solution and rubric
def overlap(a, b):
width = max(0, min(a[2], b[2]) - max(a[0], b[0]))
height = max(0, min(a[3], b[3]) - max(a[1], b[1]))
return width * height
- A. The common horizontal interval starts at the larger left edge and ends at the smaller right edge. Clamp width and height separately at zero.
- B. Width is min(4,6)-max(0,2)=2. Height is min(3,5)-max(0,1)=2. Area is 4 square units.
- C. Touching edges give zero width or height. For containment the formula returns the smaller rectangle area. A fixed number of arithmetic operations uses O(1) time and space.
Scoring rubric
- 3 points: The common horizontal interval starts at the larger left edge and ends at the smaller right edge
- 3 points: Width is min(4,6)-max(0,2)=2
- 3 points: Touching edges give zero width or height
Problem 6 · Correctness and Boundary Testing · 9 points
Build an oracle for adjacent descents
Implement descents(values), counting indices i with values[i]>values[i+1]. Then design a small exhaustive checker against the mathematical definition.
- A. Implement the linear scan.
- B. Trace [3,3,1,2,0] and give boundary cases.
- C. Explain how exhaustive small tests help and what they cannot prove.
Show worked solution and rubric
def descents(values):
total = 0
for i in range(len(values) - 1):
if values[i] > values[i + 1]:
total += 1
return total
- A. Compare adjacent pairs for indices 0 through len(values)-2. Equal neighbors are not descents.
- B. The descents are 3>1 and 2>0, giving 2. Empty and singleton lists give zero; sorted nondecreasing lists also give zero.
- C. Enumerate all short arrays over a small alphabet and compare with a separate sum of pairwise comparisons. Passing finite tests finds many boundary bugs but does not prove correctness for all inputs.
Scoring rubric
- 3 points: Compare adjacent pairs for indices 0 through len(values)-2
- 3 points: The descents are 3>1 and 2>0, giving 2
- 3 points: Enumerate all short arrays over a small alphabet and compare with a separate sum of pairwise comparisons
