Divide & Conquer — Reasoning Check

Apply the module invariants, traces, and boundary conditions.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. A sorted-array-to-BST test verifies only that inorder traversal equals [2,4,6,8]. A right-leaning chain passes. Which additional property is required by the problem?

Select one answer.

The root must be smaller than every other output key. Every internal node must have two nonempty children. The output must use exactly the reference implementation's choice of root. At every node, the left and right subtree heights differ by at most one.

2. A top-down list merge sort finds the second node of 8 -> 3 as the start of the right half, but does not change any Next pointer before calling SortList(head). What fails?

Select one answer.

The algorithm terminates normally but always returns descending order. The right recursive call contains both nodes, but the left call is empty. The two values cannot be compared until the list is reversed. The left recursive call still receives both nodes, so its subproblem does not shrink.

3. Nodes A, B, and C appear in that order with values 2, 1, and 2. A merge sort reuses nodes and takes from the left sublist on equal values. Which output satisfies its stable node-preserving contract?

Select one answer.

New nodes with values 1 -> 2 -> 2, replacing A, B, and C. B -> A -> C, containing the three original node objects. B -> A, because equal-valued nodes should be deduplicated. B -> C -> A, because equal values may be reversed in a stable sort.

4. A min-heap merges the disjoint sorted lists [0,9], [2,3], and [1,8], keeping one current head per nonempty list. After emitting 0 and then 1, what value is emitted next? Enter one integer.

5. A 4-by-4 binary grid contains fifteen 1s and a single 0 in its bottom-right corner. Construct the quad tree, collapsing every uniform region into one leaf. How many leaf nodes result? Enter one integer.

6. Four sorted lists have lengths [6,2,1,1]. Charge a merge of lengths a and b exactly a+b node-units, including all tail nodes. What is the total cost when adjacent pairs are merged in balanced rounds?

Select one answer.

27 node-units. 20 node-units. 17 node-units. 10 node-units.

Auto-advance on pass

Join Discord