# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業 1
> 貢獻者: 古道梅子-Gudao
> 🐶: Interviewer, 🐱: Interviewee
> [mock interview recording](https://www.youtube.com/watch?v=ia5rzEkO7LM)

## 70. [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
### Problem Description
:::warning
You are climbing a staircase. It takes `n` steps to reach the top.

Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?
:::

### Examples
- Example 1:
- `n = 3`
- `(1 1 1)`, `(1 2)`, `(2 1)` (3 ways)
- Example 2:
- `n = 2`
- `(1, 1)`, `(2)` (2 ways)

### Solutions
#### Intution
- Using Recursive
- base case: `n == 0` or `n == 1`, then return `1`. (because that is the only possible to arrive at the answer)
- sub-problem:
- If choose 1 step, then remain `climbstairs(n-1)` to arrive at the answer.
- If choose 2 step, then remain `climbstairs(n-2)` to arrive at the answer.
- The answer will be : sum of both sub-problem: `climbstairs(n-1)` + `climbstairs(n-2)`

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) {
        // base case
            return 1;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
};

:::success
- **Time Complexity: $O(2^n)$**
- **Space Complexity: $O(n)$**
:::

- 🐢Too slow.... -> Recursive **with memo**.
- Prevent counting the same sub-problem too many times.
- If this sub-problem has been counted before, then return it immediately.

class Solution {
public:
    int climbStairs(int n, unordered_map<int, int>& memo) {
        if (n == 0 || n == 1) {
            // base case
            return 1;
        }
        if (memo.find(n) == memo.end()) {
            // not find
            memo[n] = climbStairs(n-1, memo) + climbStairs(n-2, memo);
        }
        return memo[n];
    }

    int climbStairs(int n) {
        unordered_map<int, int> memo;
        return climbStairs(n, memo);
    }
};

:::success
- **Time Complexity: $O(n)$**
- **Space Complexity: $O(n)$**
:::
- 🐶: Can you solve this problem by iterative approach?
- Iterative
- **Bottom-up** to arrive at thet answer.
- Filling in the DP table by *summing up the values for the previous two steps*.
- Finally, it returns the value in the last cell of the DP table

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        vector<int> dp(n+1);
        // base case
        dp[0] = dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

:::success
- **Time Complexity: $O(n)$**
- **Space Complexity: $O(n)$**
:::
- Space Optimization
- Using only two variables (prev and curr) instead of an entire DP table

class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int prev = 1, curr = 1;
        for (int i = 2; i <= n; i++) {
            int temp = curr;
            curr = prev + curr;
            prev = temp;
        }
        return curr;
    }
};

:::success
- **Time Complexity: $O(n)$**
- **Space Complexity: $O(1)$**
:::

## 1539. [Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/description/)
### Description
:::warning
Given an array arr of positive integers sorted in a **strictly increasing order**, and an integer `k`.

Return the `kth` **positive integer** that is **missing** from this array.
:::

### Examples
- Example 1:
- nums: `[1, 2, 5, 8]`, `k = 2`
- missing numbers: 3, **4**, 6, 7, 9, 10, 11,...
- Example 2:
- nums: `[1, 2, 3, 4]`, `k = 2`
- missing numbers: 5, **6**, 7, 8, 9, 10, 11,...

### Solutions
#### Intution
- Using an integer count that be used to plus 1 everytime.
- Check if the count is in nums or not
- If count **in** nums: `index = index + 1`
- If not in nums: `index` do nothing,

class Solution {
public:
    int findKthPositive(vector<int>& nums, int k) {
        int count = 1, index = 0;
        int n = nums.size(), total_size = n + k;
        while (count <= total_size) {
            // check if index not out of range and count in nums or not            
            if (index < n && nums[index] == count)
                // find it in nums                 
                index++;
            // not in nums, k need to minus first
            // and check if k is equal to 0 or not.
            // if it's, the answer is count.
            else if (--k == 0) return count;
            count++;
        }
        return count;
    }
};

:::success
- **Time Complexity: $O(n+k)$**
- **Space Complexity: $O(1)$**
:::
- 🐶: Can you solve this problem in less then $O(n+k)$ complexity?
- Thinking:
- nums: `[1, 2, 5, 8]` (but the counting numbers should be as follows: 1, 2, 3, 4, 5, 6,...)
- `number of missing positive` in nums are: `[1-1, 2-2, 5-3, 8-4]` = `[0, 0, 2, 4]`
- So, we need to find the **first index** that **large or equal** than `k`.
- And the answer will be in range(`nums[index - 1] ~ nums[index]`)
- The number of missing positive at `index - 1`:
- `nums[index - 1] - (index - 1 + 1)` = `nums[index - 1] - index` -----**(eq1.)**
- The number of missing positive from `index - 1` to `k`:
- `k` - **(eq1.)** = `k` - (`nums[index - 1] - index`) -----**(eq2.)**
- The actual kth value starting from `nums[index - 1]`:
- `nums[index - 1]` - **(eq2.)** = `index + k`
- So, We can using binary search to find the index.

class Solution {
public:
    int findKthPositive(vector<int>& nums, int k) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] - mid - 1 < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left + k;
    }
};

:::success
- **Time Complexity: $O(logn)$**
- **Space Complexity: $O(1)$**
:::

## 1838. [Frequency of the Most Frequent Element](https://leetcode.com/problems/frequency-of-the-most-frequent-element/)
### Description
:::warning
The **frequency** of an element is the number of times it occurs in an array.

You are given an integer array `nums` and an integer `k`. In one operation, you can choose an index of `nums` and increment the element at that index by `1`.

Return the maximum possible frequency of an element after performing **at most** `k` operations.
:::

### Examples
- Example 1:
- nums: `[1, 4, 2]`, `k = 5`
- nums can become: `[4, 4, 4]`
- return **3**
- Example 1:
- nums: `[1, 4, 8, 13]`, `k = 5`
- nums can become: `[4, 4, 8, 13]`
- nums can become: `[1, 8, 8, 13]`
- nums can become: `[1, 4, 13, 13]`
- return **2**
- Example 1:
- nums: `[3, 6, 9]`, `k = 2`
- return **1**

### Solutions
#### Intution
- Sort the input array `nums`.
- For every new element `nums[right]` to the sliding window and add it to `prefix_sum`.
- check if `prefix_sum + k >= nums[right] * sliding window size(right - left + 1)` is vaild that mean we can using less or equal than k times operation to get current window size.
- if not, we need to reduce the window size by move the left index:
- so, `prefix_sum -= nums[left]`, `left = left + 1`
- and we need do check this until `prefix_sum + k >= nums[right] * sliding window size(right - left + 1)` become `true`

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int res = 1, n= nums.size(), left = 0, right;
        long prefix_sum = 0;
        sort(nums.begin(), nums.end());
        for (right = 0; right < n; right++) {
            prefix_sum += A[right];
            while (prefix_sum + k < (long)nums[right] * (right - left + 1)) {
                prefix_sum -= A[left++];
            }
            res = max(res, right - left + 1);
        }
        return res;
    }
};

:::success
- **Time Complexity: $O(nlogn)$**, (sorting)
- **Space Complexity: $O(1)$**
:::
- The window can be incorrectly large during some portion of the array; but every time it **expands**, it is **valid**; **otherwise**, it will only **remain its size**, not increase.
- Therefore, it can correctly compute the the largest window size.
- Essentially, we **GROW** the window when it's valid, and **SHIFT** the window when it's invalid.

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        int n= nums.size(), left = 0, right;
        long prefix_sum = 0;
        sort(nums.begin(), nums.end());
        for (right = 0; right < n; right++) {
            prefix_sum += A[right];
            if (prefix_sum + k < (long)nums[right] * (right - left + 1)) {
                prefix_sum -= A[left++];
            }
        }
        return right - left;
    }
};

:::success
- **Time Complexity: $O(nlogn)$**
- **Space Complexity: $O(1)$**
:::

### 自評
- 英文口說需加強
- 雙方缺乏互動
- Interviewer可以嘗試換個情境來說明題目
- 打字速度有點慢
- 提出改進方法後不要馬上實作，要先和interviewer討論
- 可以提出一些問題的運用情境等等
- 面試時記得關掉grammarly

---

## 第二次作業-他評 01
* 三題影片與筆記幾乎使用全英文, 也都有附上 Optimization, 但少了 Testing, 稍微美中不足. Nevertheless, 可看得出你對自己有一定的要求.
* [48:20](https://www.youtube.com/watch?v=ia5rzEkO7LM&t=2900s): 陸續開始有雜音干擾.

### 關於 interviewer
- [ ] 優點
* 對於題目描述得很具體，舉例也相當清楚.
* 我認為你的英文口說不錯. 或許是不習慣邊打字邊說話吧!

### 關於 interviewee
- [ ] 優點
* Approach說明清楚, [1539. Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/description/)的 Optimization, 是很精彩的解法.