{%hackmd theme-dark %}
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi)」課程第 4 次作業
> 貢獻者 蘇傑利-Jerry Su

### 如何進行？
1. 使用[pramp](https://www.pramp.com/#/)
2. 題目分配
a. [Coin Change(Medium)](https://leetcode.com/problems/coin-change/) Jerry Su 問 MAJAJA
b. [Hamming Distance(Easy)](https://leetcode.com/problems/hamming-distance/) MAJAJA 問 Jerry Su
c. [Single Number(Easy)](https://leetcode.com/problems/single-number/) MAJAJA 問 Jerry Su

## 322. [Coin Change](https://leetcode.com/problems/coin-change/)
- [影片](https://youtube.com/watch?v=CgKeruA30Bs&feature=shares)
- Medium
- Jerry Su 問 MAJAJA
### Question in Pramp
Example :

Input  : coins = [1,2,5], Amount = 11
Output : 3
Input  :coins = [1,3,4,5] Amount = 7
Output : 2
Input  :coins = [2,4,6]   Amount = 3
Output : -1

Constraints :

1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1 (size of int and >=1)
0 <= amount <= 104

### 面試環節
> :mouse: : You are given a vector and a integer like this example.

int coinChange(vector<int>& coins, int amount) {
}

> :mouse: : Coins representing coins of different denominations and the amount representing a total amount of money.
> :mouse: : explain the example
> coins = [1,3,4,5] Amount = 7 1x7 = 7 （more） 3+4 = 7 and 2(less)
> coins = [2,4,6] Amount = 3 This is no answer so output is -1
> :mouse: : For this question, do you have any idea to solve?
> 🐒 : Repeat
> :mouse: : Ya,you're right.
> 🐒 : Example
> :mouse: : For this question,do you know how to do?
> 🐒 : Approach
> :mouse: : Now, you can write your code.
> 🐒 : Code
> :mouse: : Can you use the example to test your code?
> 🐒 : Test
> :mouse: : Besides this method, is there any other way to optimize it?
>🐒 : Optimization(DP?)

### 完整Code

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for(int i = 1; i < amount + 1; i++) { //dp(1 ~ amount)
            for(int j = 0; j < coins.size(); j++){  //coints
                if( (i - coins[j]) >= 0){
                    dp[i] = min(dp[i],dp[i - coins[j] ] + 1);
                }
            }
        }
        return dp[amount] >= amount + 1 ? -1 : dp[amount];   
    }

### 例子說明/參考
>以這題來說用例子說明會比較簡單,可以先看這個[20分鐘的簡單講解](https://www.youtube.com/watch?v=H9bfqozjoqs&ab_channel=NeetCode)
>若使用影片的例子作為例子就是 coins = [1,3,4,5] Amount = 7

1. Step 1 建立一個dp array / vector

vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

>所以 dp = [0,8,8,8,8,8,8,8]

2. Step 2 用兩個for來做dp

for(int i = 1; i < amount + 1; i++) { //dp(1 ~ amount)
            for(int j = 0; j < coins.size(); j++){  //coints
                if( (i - coins[j]) >= 0){
                    dp[i] = min(dp[i],dp[i - coins[j] ] + 1);
                }
            }
        }

核心的判斷為 ``` i - coins[j]) >= 0 ``` ,每一次dp的狀況如下(用以上的例子):


3. Step 3 檢查是否是amount + 1

return dp[amount] >= amount + 1 ? -1 : dp[amount];

## 461. [Hamming Distance](https://leetcode.com/problems/hamming-distance/)
- [影片](https://youtube.com/watch?v=TvhfgUZIp5U&feature=shares)
- Easy
- MAJAJA 問 Jerry Su

[Hamming Distance in wikipedia](https://en.wikipedia.org/wiki/Hamming_distance)可以先從這裡做一個簡單複習

### 面試環節
1. 從Flip-N-write問問題
>Phash change memory is a kind of non-valatile memory and each bit has a certain number of writes, which means that if you keep writing, the bit will soon be broken.
>For this case, we can use FNW algorithm and the main idea is compare the new data bits with the old data bits.For example,the more than half of them are different, the new data will be flipped to reduce the number of bits to be written.
>Do you know how to compare these two data bits(new and old)

2. 相關程式怎麼寫REACTO？
> 從REACTO 問/回答問題
3. 是否還可以運用在哪裡?哪裡可以看到?實際上有運用過嗎?
> This function can compare the similarity of the image.For a 800x600x3 image , the size is very large so we can downsize the image by image hashing .
> 800 x 600 x 3 --image hash---> 32bits
> Ather that , using hamming distance to compare the 32bits.
### 完整程式1
不看解答的話，一開始的解法為：

int hammingDistance(int x, int y){
    int temp = x^y;
    int count = 0;
    for(int i = 0; i < 32; i++){
        if(((temp>>i)&1) ==1){
            count++;
        }
    }
    return count;
}

### 完整程式2
optimization
not same -->O(n = size of int)
same x y -->O(1)
看了其他人怎麼做後 :

int hammingDistance(int x, int y){
    int output = 0;
    int count = 0;
    output = x ^ y;
    while(output != 0){
        if((output & 1) == 1 ){
            count++;
        }
        output = output >> 1;
    }
    return count;
}

## 136. [Single Number](https://leetcode.com/problems/single-number/)
- [影片](https://youtube.com/watch?v=fmuqTPOvwkM&feature=shares)
- Easy
- MAJAJA 問 Jerry Su

### 面試環節
R+E
:mouse: : For this question, the array "nums" and the numsSize is the size of "nums".
:mouse: : In this example, I can use ```nums = [4,1,2,1,2]``` and the answer is 4. Am I right?
A
:mouse: : My main idea is use XOR to do and i will use example to show how to do.
>1 = 0001
>2 = 0010
>3 = 0011
>[1,3,1] we use
>0001 XOR 0011 = 0010
>0010 XOR 0001 = 0011
>Answer = 3, we can use this technique to do.

C
:mouse: : I will use a for loop and XOR to complete the code
T
:mouse: : Use 2 test to do the test
>[4,1,2,1,2] , [1] and [3,3,8]
O
>...

### 完整程式1

int singleNumber(int* nums, int numsSize){
    int temp = 0;
    for(int i = 0; i < numsSize; i++){
        temp = temp ^ nums[i];
    }
    return temp;
}

## 檢討自己整學期的表現
我覺得最最最重要的檢討是從這堂課發現自己的不足的地方，所以我分為以下4個部分做檢討
1. 與老師一對一討論

A. 老師問了很多基本的問題，都答不出來，都是事後才發現問的問題其實不會很難但是就是會一時之間答不出來。幸運的是這個情況不是發生在下星期開始第一個實習面試，而是發生在與老師的對談上

B. 雖然老師說應該要多說自己在實驗室衛星上的東西在履歷上，但是我認為我要加強作業系統和密碼學上的不足因為我所做的計劃和這些有關，是肯定無法逃避的

C. 題目整理 : reentrancy, gcm aes, 費馬小定理, round robin

D. 檢討改進 : 在後半年的計劃當中，我至少要熟FreeRTOS的api，並且多用作業系統說學到的東西(mutex/semaphore)運用在計劃上。下學期的話就借由修課(有開)來補強密碼學的基本知識(至少要可以回答老師的問題)。總的來說，下學期所學的知識非常重要，也可能是面試會被問到的問題

2. 與同學prampt的面試
A. 英文上，避免同一個詞重複使用(就如中文上一直 “然後”)
B. 要習慣一道題目上來，就可以一直講解或是說明使用什麼方法
C. 看回去自己的表現後，發現很多可以補強的地方是自己從來沒有發現到的
3. 老師邀請的講者
A. 實體課的部分我都有參與所以收穫良多，尤其是可以看到不同年齡層所講的東西都不太一樣。我認為剛畢業的chovy最為接近，也是我們可以學習的目標。

4. 作業上的檢討
A. 作業上的題目我基本都挑選bitwise為主是因為我的計劃上需要讀/寫這些code，我都有把leetcode的題目盡可能地往下做延伸。雖然有些應用看不是很懂，但是我都盡可能地了解，至少知道有這個東西。