COMP2521 Final - Coding Review

⚠️ Universal Constraints ⚠️ 通用约束（所有题）

No global or static variables → automatic zero marks禁止全局变量和静态变量 → 自动零分
No additional #includes禁止额外 #include
No hardcoded return values — must solve generally不能 hardcode 返回值，必须通用解法
You MAY define helper functions, structs, #defines可以定义辅助函数、结构体、宏
Memory leaks are NOT penalised (but memory errors may cause wrong results)内存泄漏不扣分（但内存错误可能导致结果不一致）

🔗 Q1 — Linked List: Recursive append 🔗 Q1 — 链表：递归 append

10 marks⭐ Easiest coding question

Append list l2 to the end of list l1. Return the combined list. 把链表 l2 接到 l1 后面，返回合并后的链表。

NO loops — while, for, do, goto all forbidden → zero marks禁止循环 — while/for/do/goto 全部禁止 → 零分
NO malloc/calloc — reuse existing nodes only禁止 malloc/calloc — 只能复用已有节点
MUST use recursion必须用递归

Core Insight 核心思路

Ask: what is append(l1, l2)? 问自己：append(l1, l2) 是什么？

If l1 is empty → just return l2如果 l1 是空的 → 直接返回 l2
If l1 is not empty → keep l1's head, but set its next = append(l1->next, l2)如果 l1 不是空的 → 保留 l1 的头节点，但它的 next = append(l1->next, l2)

Trace through example 示例追踪

append([3,1,4], [1,5]) = 3 → append([1,4], [1,5]) = 3 → 1 → append([4], [1,5]) = 3 → 1 → 4 → append([], [1,5]) = 3 → 1 → 4 → [1,5] ✓

Final Code 完整代码

struct node *append(struct node *l1, struct node *l2) {
    // base case: l1 is empty, just return l2
    if (l1 == NULL) {
        return l2;
    }
    // recursive case: keep current head, fix its next
    l1->next = append(l1->next, l2);
    return l1;
}

Edge Cases 边界情况

Input	Expected Output
l1=[], l2=[1,3,3,7]	[1,3,3,7]
l1=[3,1,4], l2=[]	[3,1,4]
l1=[], l2=[]	[]

🔗 Q2 — Linked List: flas (First Longest Ascending Sublist) 🔗 Q2 — 链表：flas（第一最长严格递增子列）

10 marksMedium

Find the start node of the longest strictly-increasing consecutive sublist. If tied, return the first. Minimum length = 2. 找最长严格递增连续子列的起始节点。并列时返回第一个。最少2个元素才算。

NO arrays → zero marks禁止数组 → 零分
Do NOT modify the input list不能修改输入链表

The 4 Variables You Need 需要追踪的 4 个变量

curStart — where current ascending run begins当前递增段的起始节点
curLen — length of current run当前段的长度
bestStart — where the longest run so far begins目前最长段的起始节点
bestLen — length of the longest run so far目前最长段的长度

Walk through example 示例追踪

List: [1, 3, 2, 4, 5, 6] cur=1, next=3: 3>1 ✓ curLen=2 cur=3, next=2: 2<3 ✗ BREAK! curLen(2) > bestLen(0) → update best=1 reset: curStart=2, curLen=1 cur=2, next=4: 4>2 ✓ curLen=2 cur=4, next=5: 5>4 ✓ curLen=3 cur=5, next=6: 6>5 ✓ curLen=4 Loop ends. ⚠️ Must check last segment after loop! curLen(4) > bestLen(2) → update best=2 Return: pointer to node [2] ✓

⚠️ Most common mistake: forgetting to check the last segment after the loop. If list is [1,2,3,4,5], the loop never breaks — best never updates inside the loop! ⚠️ 最常见错误：循环结束后忘记检查最后一段。如果链表是 [1,2,3,4,5]，循环里永远不会断，best 永远不会在循环内更新！

Final Code 完整代码

struct node *flas(struct node *l) {
    if (l == NULL || l->next == NULL) return NULL;

    struct node *bestStart = NULL;
    int bestLen = 0;

    struct node *curStart = l;
    int curLen = 1;

    for (struct node *cur = l; cur->next != NULL; cur = cur->next) {
        if (cur->next->val > cur->val) {
            curLen++;                       // still ascending
        } else {
            if (curLen > bestLen) {         // broke: check if new best
                bestLen = curLen;
                bestStart = curStart;
            }
            curStart = cur->next;           // reset current run
            curLen = 1;
        }
    }

    // ⚠️ Always check last segment after loop
    if (curLen > bestLen) {
        bestLen = curLen;
        bestStart = curStart;
    }

    if (bestLen < 2) return NULL;
    return bestStart;
}

Edge Cases 边界情况

Input	Expected
[]	NULL
[5]	NULL
[3,2,1]	NULL (no ascending sublist)
[1,2,3,4,5]	pointer to 1 (full list)
[5,1,2,3]	pointer to 1 (length 3)
[1,2,3,2,3,4]	pointer to first 1 (both length 3 — tie → first one)

🌐 Q3 — Graph: Max Degree Difference 🌐 Q3 — 图：最大度数差

10 marks⭐ Simple — Two nested loops

Directed graph. For each vertex compute |in-degree − out-degree|. Return the maximum over all vertices. 有向图。对每个节点计算 |入度 − 出度|，返回所有节点中的最大值。

💡 Reading the adjacency matrix: 💡 读邻接矩阵：

in-degree of v = scan column v (who points to v)v 的入度 = 扫描第 v 列（谁指向 v）
out-degree of v = scan row v (where v points to)v 的出度 = 扫描第 v 行（v 指向谁）

Final Code 完整代码

int maxDegreeDiff(Graph g) {
    int max = 0;

    for (int v = 0; v < g->nV; v++) {
        int inDeg = 0;
        int outDeg = 0;

        for (int u = 0; u < g->nV; u++) {
            if (g->edges[u][v]) inDeg++;   // column v: who points to v
            if (g->edges[v][u]) outDeg++;  // row v: where v points
        }

        int diff = inDeg - outDeg;
        if (diff < 0) diff = -diff;        // abs value
        if (diff > max) max = diff;
    }

    return max;
}

Note: Use manual absolute value if (diff < 0) diff = -diff to be safe. abs() requires <stdlib.h> which may already be included via Graph.h. 注意：为了安全，手写绝对值 if (diff < 0) diff = -diff。abs() 需要 <stdlib.h>，Graph.h 里可能已经包含了。

🗺️ Q4 — Graph: dayTrip (BFS, dual edge types) 🗺️ Q4 — 图：dayTrip（BFS，双类型边）

15 marksMedium-Hard

Find all cities reachable from start vertex within 1 day. Two road types exist. 找从起点出发，在1天内能到达的所有城市。有两种道路类型。

STD road: 1 road = 1 full day1 条 = 1 整天
FAST road: 1 road = half a day → need 2 FAST to use a full day1 条 = 半天 → 2 条 FAST = 1 天

Reachability Rules 可到达规则

Route	Cost	Reachable?
1 STD road	1 day	✅ Yes
1 FAST road	0.5 day	✅ Yes (under 1 day)
2 FAST roads	1 day	✅ Yes
1 FAST + 1 STD	1.5 days	❌ No
2 STD roads	2 days	❌ No

⚡ Key Insight: Use "half-day units" (0, 1, 2). Max allowed = 2. ⚡ 关键思路：用"半天"为单位（0, 1, 2），最大允许 = 2。

FAST edge: +1 half-day半天
STD edge: +2 half-days (= 1 full day)半天（= 1 整天）

BFS Trace (from vertex 0) BFS 追踪（从节点 0 出发）

dist[0]=0 → queue: [0] Pop 0 (dist=0): FAST neighbours 1,3 → dist[1]=1, dist[3]=1 ✓ add STD neighbours 2,3 → dist[2]=2 ✓ add (dist[3] already 1, skip) Pop 1 (dist=1): FAST neighbour 2 → dist[2] already set, skip STD neighbours → 1+2=3 > 2, skip Pop 3 (dist=1): FAST neighbour 5 → dist[5]=1+1=2 ≤ 2 ✓ add STD neighbours → 1+2=3 > 2, skip Pop 2, 5 (dist=2): all edges would exceed 2, skip Result: {1, 2, 3, 5} ✓

Final Code 完整代码

int dayTrip(Graph g, Vertex s, Vertex vs[]) {
    int dist[g->nV];
    for (int i = 0; i < g->nV; i++) dist[i] = -1;
    dist[s] = 0;

    // BFS queue (array-based)
    int queue[g->nV];
    int head = 0, tail = 0;
    queue[tail++] = s;

    while (head < tail) {
        int v = queue[head++];

        for (int u = 0; u < g->nV; u++) {
            // FAST edge: +1 half-day
            if (g->fast[v][u] && dist[u] == -1) {
                dist[u] = dist[v] + 1;
                if (dist[u] <= 2) queue[tail++] = u;
            }
            // STD edge: +2 half-days (1 full day)
            if (g->std[v][u] && dist[u] == -1) {
                dist[u] = dist[v] + 2;
                if (dist[u] <= 2) queue[tail++] = u;
            }
        }
    }

    // Collect reachable vertices (exclude start)
    int count = 0;
    for (int i = 0; i < g->nV; i++) {
        if (dist[i] != -1 && i != s) {
            vs[count++] = i;
        }
    }
    return count;
}

⚠️ Exam trap: Check the actual field names in Graph.h! They might be stdEdges/fastEdges or something else. Always look before writing. ⚠️ 考试陷阱：一定要看 Graph.h 里的实际字段名！可能是 stdEdges/fastEdges 或其他名字。先看再写。

Summary: what can reach where 总结：哪些节点可以继续走

Current dist =	STD → new dist	FAST → new dist
0 (start)	0+2=2 ✅	0+1=1 ✅
1 (one FAST away)	1+2=3 ❌	1+1=2 ✅
2 (full day)	2+2=4 ❌	2+1=3 ❌

🌳 Q5 — BST: Min Diff at Level L 🌳 Q5 — BST：第 L 层最小差

15 marksHardest — O(n) required for full marks

Given a BST and integer l, find the minimum absolute difference between any two values on level l. Return 0 if fewer than 2 values on that level. 给 BST 和整数 l，找第 l 层所有节点值中的最小绝对差。如果该层少于 2 个节点，返回 0。

⚠️ O(n) solution = 15/15. Slower solution = max 9/15. ⚠️ O(n) 解法 = 15/15。更慢的解法 = 最多 9/15。

⚡ Key Insight: BFS level-by-level ⚡ 关键思路：BFS 逐层遍历

Use BFS with a queue that tracks (node, level). When we reach level l, collect values. BST left-to-right at any level is sorted → min diff = minimum of consecutive differences. 用 BFS，队列里存 (节点, 层级)。到达第 l 层时收集节点值。BST 在任意层从左到右的值是有序的 → 最小差 = 相邻值差的最小值。

Final Code 完整代码

int minDiff(struct node *t, int l) {
    if (t == NULL) return 0;

    // BFS queue: parallel arrays for node and level
    struct node *nodeQ[10000];
    int levelQ[10000];
    int head = 0, tail = 0;

    nodeQ[tail] = t;
    levelQ[tail] = 0;
    tail++;

    int prevVal = 0;
    int foundFirst = 0;
    int minD = 0;

    while (head < tail) {
        struct node *curr = nodeQ[head];
        int currLevel = levelQ[head];
        head++;

        if (currLevel == l) {
            if (!foundFirst) {
                prevVal = curr->val;
                foundFirst = 1;
            } else {
                int diff = curr->val - prevVal;  // BST: left-to-right is sorted
                if (diff < 0) diff = -diff;
                if (minD == 0 || diff < minD) minD = diff;
                prevVal = curr->val;
            }
        }

        // Only enqueue children if we haven't reached level l yet
        if (currLevel < l) {
            if (curr->left != NULL) {
                nodeQ[tail] = curr->left;
                levelQ[tail] = currLevel + 1;
                tail++;
            }
            if (curr->right != NULL) {
                nodeQ[tail] = curr->right;
                levelQ[tail] = currLevel + 1;
                tail++;
            }
        }
    }

    return minD;
}

✅ Why O(n)? ✅ 为什么是 O(n)？

Each node is visited at most once. We stop enqueuing children once we've reached level l — no wasted work going deeper. Total work = O(n). 每个节点最多访问一次。到达第 l 层后不再把子节点加入队列，不浪费时间继续往深走。总工作量 = O(n)。

Edge Cases 边界情况

Situation	Return
Level l doesn't exist in tree	0
Only 1 node at level l	0
2+ nodes at level l	minimum \|a - b\| of any two adjacent values

📚 Bonus: listSetUnion 📚 附录：listSetUnion（链表集合并集）

Merge two sorted linked lists (sets) into one — each value appears only once. Both lists are sorted ascending. 合并两个有序链表（集合）为一个，每个值只出现一次。两个链表都是升序的。

Three cases per recursive step: 每次递归的三种情况：

l1 smaller: take l1 head, recurse with l1->next and l2l1 更小：取 l1 头，用 l1->next 和 l2 递归
l2 smaller: take l2 head, recurse with l1 and l2->nextl2 更小：取 l2 头，用 l1 和 l2->next 递归
Equal: take one, skip the other → recurse with l1->next and l2->next相等：取一个，跳过另一个 → 用 l1->next 和 l2->next 递归

struct node *listSetUnion(struct node *l1, struct node *l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    if (l1->val == l2->val) {
        // equal: take l1, skip l2, advance both
        l1->next = listSetUnion(l1->next, l2->next);
        return l1;
    }
    if (l1->val < l2->val) {
        l1->next = listSetUnion(l1->next, l2);
        return l1;
    }
    l2->next = listSetUnion(l1, l2->next);
    return l2;
}

💡 Why it doesn't get stuck: Every recursive call advances at least one pointer. Both eventually reach NULL, terminating the recursion. 💡 为什么不会卡住：每次递归至少让一个指针往前走。两个最终都会到 NULL，递归必然终止。

Coding Review (Q1–Q5) 编程题复习（Q1–Q5）

⚠️ Universal Constraints ⚠️ 通用约束（所有题）

🔗 Q1 — Linked List: Recursive append 🔗 Q1 — 链表：递归 append

Core Insight 核心思路

Trace through example 示例追踪

Final Code 完整代码

Edge Cases 边界情况

🔗 Q2 — Linked List: flas (First Longest Ascending Sublist) 🔗 Q2 — 链表：flas（第一最长严格递增子列）

The 4 Variables You Need 需要追踪的 4 个变量

Walk through example 示例追踪

Final Code 完整代码

Edge Cases 边界情况

🌐 Q3 — Graph: Max Degree Difference 🌐 Q3 — 图：最大度数差

Final Code 完整代码

🗺️ Q4 — Graph: dayTrip (BFS, dual edge types) 🗺️ Q4 — 图：dayTrip（BFS，双类型边）

Reachability Rules 可到达规则

BFS Trace (from vertex 0) BFS 追踪（从节点 0 出发）

Final Code 完整代码

Summary: what can reach where 总结：哪些节点可以继续走

🌳 Q5 — BST: Min Diff at Level L 🌳 Q5 — BST：第 L 层最小差

Final Code 完整代码

Edge Cases 边界情况

📚 Bonus: listSetUnion 📚 附录：listSetUnion（链表集合并集）

🎯 Test Your Coding Knowledge 🎯 测试你的编程知识