# 資訊科技產業專案設計 作業四
## Mock Interview
🦹‍♂️ : Richard (Interviewer)
👨‍💻 : Mason (Interviewee)
### 34. Find First and Last Position of Element in Sorted Array
**Description**
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

example:
nums = [5,7,7,8,8,10], target = 8

**Interview**
🦹‍♂️ : Hello Mason, we're glad to have you here in our interview, would you like to briefly introduce yourself and your previous job?
👨‍💻 :
🦹‍ : It sounds impressive, I'm sure you'll do well in the following process. I've just sent you a document and there's a small exercise on it, can you see it?
👨‍💻 : Yes, (Mason answer or question)
🦹‍ : Let me briefly introduce the question for you, now we'll give you an sorted array of integer `nums`, and a target number `target`. We want you to give us the leftmost position of `target` and the rightmost position of `target`.
🦹‍ : If there's no problem, you can tell me your approach and maybe start to implement your solution
👨‍💻 : (Mason answer correctly!)
🦹‍ : Can you calculate the time complexity of your algorithm?
👨‍💻 : (Mason answer)
🦹‍ : Can you lower the time complexity to $O(log(n))$
👨‍💻 : (Mason answer)
如果在這邊你使用遞迴解法或者helper function, 我會問在function call的成本跟時間複雜度之間, 你怎麼分析何者的成本比較低
🦹‍ : I think your solution is pretty well, but you use (recursive or helper function) more function call in this solution. I wonder how do you make the tradeoff between complexity and the cost of function call?

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int findLeftIndex(int* nums, int numsSize, int target) {
    int low = 0, high = numsSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

int findRightIndex(int* nums, int numsSize, int target) {
    int low = 0, high = numsSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] <= target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return high;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    result[0] = -1; // Initialize with [-1, -1]
    result[1] = -1;

    int left = findLeftIndex(nums, numsSize, target);
    int right = findRightIndex(nums, numsSize, target);

    // Check if the target is within the range found
    if (left <= right && right < numsSize && nums[left] == target && nums[right] == target) {
        result[0] = left;
        result[1] = right;
    }

    return result;
}

-if (nums[mid] <= target) {
-    low = mid + 1;
-} else {
-    high = mid - 1;
-}
+nums[mid] <= target ? low = mid + 1 : high = mid - 1;

### 287. Find the Duplicate Number
**Description**
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

**Interview**
🦹‍♂️ : Hello Mason, we're glad to have you here in our interview, would you like to briefly introduce yourself and your previous job?
👨‍💻 : (Mason answer)
🦹‍ : It sounds impressive, I'm sure you'll do well in the following process. I've just sent you a document and there's a small exercise on it, can you see it?
👨‍💻 : Yes, (Mason answer or question)

int findDupclicate(int *nums, int numsSize) {
    int *table = calloc(sizeof(int), numsSize);
    for (int i=0; i<numsSize; i++) {
        if (table[nums[i]])
            return nums[i];
        table[nums[i]]++;
    }
    return -1; // error case
}

🦹‍ : We'll give you an array of integer `nums`, the length of `nums` is `numsSize`, the elements in this array are in the range between `1`~`numsSize`. There'll be exactly 2 elements with the same value, please tell us which value is repeated.
🦹‍ : If there's no problem, you can tell me your approach and maybe start to implement your solution
👨‍💻 : (Mason answer correctly!)
🦹‍ : Can you calculate the time complexity and space complexity of your algorithm?
👨‍💻 : (Mason answer)
🦹‍ : Can you make the time complexity to $O(n)$ and space complexity to $O(1)$ ?

int findDuplicate(int* nums, int numsSize) {
    // Initialize the tortoise and hare pointers
    int tortoise = nums[0];
    int hare = nums[0];

    // Find the meeting point of the tortoise and hare
    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
    } while (tortoise != hare);

    //  Find the entrance to the cycle
    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }

    return hare;
}