# 2025 年「資訊科技產業專案設計」課程作業 4
> Contributor : 包拯 Moon 魚玄機 Daisy
> [Mock Interview Record-1](https://youtu.be/fy5PZQ6Ob4I)
> [Mock Interview Record-2](https://youtu.be/tZfLBY8qKNU)

>Daisy :santa: : Interviewer
>Moon :christmas_tree: : Interviewee

## [141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/)
:santa: : Welcome to our interview.

Today I'll give you a question about linked list cycle.

The head of a linked list is provided, how would you determine whether there's a cycle in this linked list?

==Repeat== ==Example==
:christmas_tree: : Okay.

Let me think about it.

A cycle occurs if I traverse the list and encounter a duplicate node.

If we have a linked list like `3 -> 2 -> 0 -> 4` and `4` points pack to `2`, then there's a cycle and the function should return `true`.

Is my understanding correct ?

:santa: : Exactly. How would you approach this ?

==Approach==
:christmas_tree: :
I know there's a solution called `Fast and Slow Pointers`.

Starting from head, the fast pointer moves two steps at a time while the slow one moves one step.

If there's a cycle, they will eventually meet.

==Code==
:santa: : Sounds perfect.

If you can code it up, that will be great.

:christmas_tree: : Of course.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    // First I'll handle edge cases to check there's at least two node in the list.
    if (head == NULL || head->next == NULL) return false;
    // And then I initialize two pointers, both starting from head.
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    // The fast pointer moves two steps, slow moves one step.
    // Here I use a while loop to ensure that the fast pointer can move two steps without accessing NULL.
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        // If they meet, there's a cycle
        if (slow==fast) return true;
    }
     // If fast pointer reaches the end, there's no cycle then we return false.
    return false;
}

The time complexity is O(n), because the pointer will traverse all the nodes in the worst case.

And the space complexity is O(1) becasue we only use two additional pointers.

==Optimization== [142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/)
:santa: : This solution works well.

Now let's make it more practical.

Imagine you're debugging and you've detected a cycle.

How would you figure out where that cycle begins ?

:christmas_tree: : That's indeed a pretty important issue.

I remember that this problem could be solved by reseting the slow pointer to the head,
while keeping the fast pointer at the meeting point found in the previous step.

Then I advance both pointers one node at a time.

The point where they meet again is the cycle start.

:santa: : Well.

Could you explain why they'll meet at the cycle start ?

Isn't that a coincidence ?

:christmas_tree: : Sure.

Let me assume the distance from head to cycle start is `L`, distance from cycle start to the meeting point is `d`, and the length of the cycle is `C`.

Since the fast pointer moves twice as fast as the slow one, when they meet:

Slow pointer traveled `L + d`.
Fast pointer traveled `L + nC + d`, `n` is the number of complete cycles.

Since fast moves twice the distance, I can write the equation like this :

Twice L plus d is equal to L plus n C plus d
$$ 2(L+d) = L + nC + d $$

It can be simplified to :

L equals to n C minus d
$$ L = nC - d $$

This proves that moving `L` steps from head equals to moving (nC - d) steps from the meeting point, which brings us to the cycle start.

:santa: : Seems that your logic is clear enough.

Would you like to modify the code to handle it?

:christmas_tree: : Sure. Here it is.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL) return NULL;
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast){
// I just have to modify the part after two pointers meet.
// I reset slow pointer back to head.
            slow = head;
            while(slow != two){
        // Then move both one step at a time.
                slow = slow->next;
                fast = fast->next;
            }
// They'll meet again, and the meeting point is the cycle start.
            return slow;
        }
    }
    return NULL;
// If there's no cycle, we just return NULL.
}

:santa: : Well done.

And that's all for today's interview.

We'll contact you by email in a few days.

Have a nice day.

:christmas_tree: : Thanks for your time. I'm looking forward to it.

##

## [2215. Find the Difference of Two Arrays](https://leetcode.com/problems/find-the-difference-of-two-arrays/)

>🌸: interviewer 由 包拯-Moon 擔任
🍀: interviewee 由 魚玄機-Daisy 擔任

### 模擬面試過程
🌸 Interviewer: Hello, welcome and thanks for joining us today.
Our team works on large-scale data reconciliation across multiple systems. For example, different services may maintain their own lists of identifiers, and we often need to quickly determine which data exists in one system but not another.
🌸 Interviewer: Here’s a problem I’d like you to work on.
We have two systems, each returning an integer array:
* nums1 represents identifiers from System A
* nums2 represents identifiers from System B

The arrays may contain duplicate values.
Your task is to return a result containing two lists:
1. All distinct integers that appear in nums1 but not in nums2
2. All distinct integers that appear in nums2 but not in nums1

Each integer should appear at most once in the output.
🌸 Interviewer: Do you have any questions about the problem description?
🍀 interviewee: Yes, I’d like to clarify a couple of points.
First, is there any constraints on the order of the output?
🌸 Interviewer: No, the order of the output does not matter.
🍀 interviewee: Okay. And if a number appears multiple times in nums1 but not in nums2, it should only appear once in the result?
🌸 Interviewer: Yes, that’s correct.
🍀 interviewee: Great. Let me give a quick example to make sure I understand correctly.

nums1 = [1, 2, 3, 3]
nums2 = [2, 4]
Output = [[1, 3],[4]]

🌸 Interviewer: That’s correct.
🍀 interviewee: Here’s my initial approach.
I would start with sorting both arrays, and use two pointers to traverse them. I will compare values from two arrays, and save elements that appear only in one array in the answer array. And also try to skip duplicate elements.
🌸 Interviewer: That sounds reasonable. You can go ahead and write the code.

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2)
    {
        vector<vector<int>> ans(2);
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int i=0, j=0;
        while(i<nums1.size() && j<nums2.size())
        {
            if(nums1[i]<nums2[j])
            {
                ans[0].push_back(nums1[i]);
                while(i<nums1.size()-1 && nums1[i+1]==nums1[i])
                {
                    i++;
                }
                i++;
            }
            else if(nums1[i]>nums2[j])
            {
                ans[1].push_back(nums2[j]);
                while(j<nums2.size()-1 && nums2[j+1]==nums2[j])
                {
                    j++;
                }
                j++;
            }
            else
            {
                while(i<nums1.size()-1 && nums1[i+1]==nums1[i])
                {
                    i++;
                }
                while(j<nums2.size()-1 && nums2[j+1]==nums2[j])
                {
                    j++;
                }
                i++;
                j++;
            }
        }
        while(i<nums1.size())
        {
            ans[0].push_back(nums1[i]);
            while(i<nums1.size()-1 && nums1[i+1]==nums1[i])
            {
                i++;
            }
            i++;
        }
        while(j<nums2.size())
        {
            ans[1].push_back(nums2[j]);
            while(j<nums2.size()-1 && nums2[j+1]==nums2[j])
            {
                j++;
            }
            j++;
        }
        return ans;
    }
};

🌸 Interviewer: Great. What is the complexity of your approach?
🍀 Interviewee: The time complexity is O(nlogn+mlogm), due to sorting. And the space complexity is O(1).
🌸 Interviewer: This solution works, but can you see any downsides?
🍀 Interviewee: Yes. While it avoids extra memory, the sorting step increases the time complexity.
Also, the logic is relatively complex and easy to get wrong, especially with duplicate handling.
🌸 Interviewer: How would you improve it?
🍀 Interviewee: Well, I would convert both arrays into hash sets, so it can automatically remove duplicate values and check whether an element already exists in constant time.
🌸 Interviewer: That sounds good. You can go ahead and write the code.

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2)
    {
        vector<vector<int>> ans(2);
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        for(int i: set1)
        {
            if(!set2.count(i))
            {
                ans[0].push_back(i);
            }
        }
        for(int i: set2)
        {
            if(!set1.count(i))
            {
                ans[1].push_back(i);
            }
        }
        return ans;
    }
};

🌸 Interviewer: Okay. What is the complexity of this new approach?
🍀 Interviewee: The time complexity is O(n+m), where n is the length of nums1 and m is the length of nums2 to iterate both array and bulid the two hash sets. And the space complexity is O(n+m), since it store the element in two hash sets.
🌸 Interviewer: That makes sense. Thank you for joining today's interview.
🍀 Interviewee: Thank you for your time.