# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023-homework1)」作業 1 > 貢獻者: 吸鎖-seesaw ## [136. Single Number](https://leetcode.com/problems/single-number/description/) > [模擬面試錄影](https://youtu.be/DDvWYRLwvGs) ### 面試問答 A:interviewee B:interviewer A:我們這邊有一道題目，會給你一個integer的零陣列nums，每個元素會出現兩次除了一個數字只出現一次，請你找到只出現一次的數字。 A:array的長度介在1到30000間，整數的值介在負三萬到三萬間 B:所以我會拿到ㄧ個input 大小介在一到三萬的整數陣列，裡面每個值都介在正負三萬並且包含0，裡頭所有的值都會出現兩次，然後要把只有出現一次的 那個值印出來。 A:對的 B:好的，那我最直觀的想法應該會是用兩層for迴圈去做，將array裡的每一項去和整個array去比對一次，然後。 A:聽起來沒什麼問題，那我們就開始coding吧 #### 法ㄧ：暴力解 可以用兩層for迴圈去將每一項和整個array比對一遍，將只有出現過一次的數字印出來。 ```c int singleNumber(int* nums, int numsSize){ for(int i =0;i<numsSize;i++){ int currentnum= nums[i]; int count=0; for(int j =0;j<numsSize;j++){ if(currentnum ==nums[j]){ count++; } } if (count==1){ return currentnum; break; } } return 0; } ``` A:這個方法在時間複雜度會是$O(n^2)$，有沒有辦可以降低他時間複雜度的方法。 B:如果用hash map的方法去嘗試，應該可以降低他的時間複雜度。 B:會做兩次的for迴圈，第一個for迴圈會去將給的nums 的array值去做mapping，接下來第二個for迴圈去讀取key的值，再把key值為一的印出來。 A:那我們開始coding吧 #### 法二:Hash map 剛剛的所說的方法時間複雜度會是$O(n^2)$，如果要讓他的時間複雜度降低的話，可以用 hash map的方法，整體架構大概是兩個for迴圈，第一圈for迴圈用一個新的MAP array去紀錄出現次數，第二個for迴圈再去把MAP array等於1的值印出來。 ```c int singleNumber(int* nums, int numsSize){ const int offset = 30000; int map[60001] = {0}; for (int i = 0; i < numsSize; i++) { map[nums[i]+offset]++; } for (int i = 0; i < 60001; i++) { if (map[i] == 1) return i-offset; } return 0; } ``` A:這個做法的時間複雜度降低了，但空間複雜上升了，有沒有辦法去優化它的空間複雜度嗎 B:也許可以用Bitwise operation去嘗試，我們可以試著用XOR operation，我們知道XOR具有交換性，a ^ b ^ a=(a ^ a)^ b=且 a^a=0，即可找出single number。 #### 法三:XOR ```c int singleNumber(int* nums, int numsSize){ int res = *nums; for(int i=1; i < numsSize ;i++){ res ^=nums[i]; } return res; } ``` ## [202. Happy Number](https://leetcode.com/problems/happy-number/) > [模擬面試錄影](https://youtu.be/MyifnUr9vqQ) ### 面試問答 A:interviewee B:interviewer A:So here is a int number n starting with a positive number, and replace it by the sum of the squares of its digits.Repeat the process until the number equals 1 which is a happy number,or loops endlessly in a cycle which does not include 1,which is not a happy number. B:So i have to check whether if it's sum of the squared digits equals to 1 or not and kept repeating it . A:You're right. B:So I'll take 2 as an example 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 so it repeats after doing some ditgit squared sum . I will approach this problem by using a new array to memorize the new replaced num and check if it has appeared before,if it has appeared before and isn't 1 then return false. A:So what's the size of the array you are going to create to memorize. B:The constraint of the of n is between 1 and 2 to the power of 31 ,so we can estimate the max digit is 10 so the max ditgit squared sum would be 810. A:Great! But the time complexity is $O(n^2)$ according to your method , is the a way to lower it? B:Maybe we can try to check the duplication by using hash map,creat a length of 810 integer array ,and also a digit squared sum function. ```c int squaredSum(int n) { int tot = 0; while (n) { int tmp = n % 10; tot += tmp * tmp; n /= 10; } return tot; } bool isHappy(int n) { bool Map[810]= {0}; int ss = squaredSum(n); while (ss != 1) { if (Map[ss]) return false; Map[ss] = true; ss = squaredSum(ss); } return true; } ``` ## [50. Pow(x, n)](https://leetcode.com/problems/powx-n/description/) > [模擬面試錄影](https://youtu.be/edMJuMiqS_M) ### 面試問答 A:interviewee B:interviewer A:這邊我希望你去做出個power的function，也就是x的n次方，他的條件限制會如檔案所示。 B:好那我們要來寫一個x的n次方的函式，最直觀的解法就是用一個迴圈去將答案相乘幾次。 A:你這樣做的時間複雜度是O(n)，那有沒有降低他時間複雜度的方式? B:先來看看條件有什麼限制，x有正有負的而且是個double，n的話可以分正負基偶去討論， ``` if n >0 even (n = 2m), x^n = x^(2m) = (x^2)^m if n >0 positive odd (n = 2m+1), x^n = x^(2m+1) = x(x^2)^m if n <0 even (n = -2m), x^n = (1/x)^(2m) = ((1/x)^2)^m if n <0 odd (n = -2m-1), x^n = (1/x)^(2m+1) = (1/x)((1/x)^2)^m ``` 所以我們這邊呼叫自己，所以可以考慮用遞迴的方式去做，所以我們要找到終止條件，那我們可以去設定n等於0時回傳，而接下來根據四種n的值狀況分別去做各自的遞迴呼叫。 ```c double myPow(double x, int n) { long m = n; if (n == 0) return 1.0; else if(n==1) return x; if (n < 0) { x = 1.0 / x; m = -m; } if (m % 2!=0) { return myPow(x * x, m / 2) * x; } else { return myPow(x * x, m / 2); } } ``` ## 初步總檢討 - 針對第一個問題時，我的REACTO的e做得蠻不好的沒有去很有效地透過舉例去找尋問題的解法思路或規律。 - 程式碼編排混亂，如格式空格等一致的話會更方便別人閱讀 - 思考時常會自言自語，可以改成想好之後再講或是邊講解程式碼讓別人給的上你的思路 --- ## 第二次作業-他評01 ### interviewer - [ ] 優點 * 有引導 interviewee 降低時間或空間複雜度 - [ ] 可改進之處 * 可以包裝題目，避免聽到關鍵字就讓 interviewee 背出答案 ### interviewee - [ ] 優點 * [12:56](https://youtu.be/DDvWYRLwvGs?si=jY7iNRayRl1mvMoF&t=776) ~ [14:53](https://youtu.be/DDvWYRLwvGs?si=4z4HyBiY1ygn--aN&t=893): 這邊的舉例講解很清楚詳細，讓人一看就明白 * 英文表達清楚 - [ ] 可改進之處 * [6:11](https://youtu.be/DDvWYRLwvGs?si=V6cdmO0OOkyaDRe-&t=371) ~ [6:57](https://youtu.be/DDvWYRLwvGs?si=V6cdmO0OOkyaDRe-&t=417): 表達的有點混亂，可以想好再講 ## 第二次作業-他評02 ### interviewer - [ ] 優點 * 有適當引導對方改善空間。 - [ ] 可改進之處 * 跟受試者討論改善空間時，可以請對方先自行分析，而不是給出對方的程式的時間複雜度。 ### interviewee - [ ] 優點 * 解釋例子時很清楚詳細。 - [ ] 可改進之處 * 第一題一開始只有做到 R 的部分，並且確認面試官想問的意思，沒有 E 的部分，應該自己舉例再跟面試官確認想法。 ## 第二次作業-他評03 ### 針對 Interviewer 的檢討: * 可以包裝一下題目 * 看到 Interviewee 降低時間複雜度，但造成空間複雜度上升這件事提出來很棒！ * 口語清晰 ### 針對 Interviewee 的檢討: * 方法說明得很清楚 * 口齒清晰 * [10:46](https://youtu.be/DDvWYRLwvGs?t=646) 滑鼠頻繁移動，可以反白在你要說的那一行就停下 * [14:36](https://youtu.be/DDvWYRLwvGs?t=876) 使用的是陣列，不應該說是 map 函數 * [16:02](https://youtu.be/DDvWYRLwvGs?t=962) 盡量避免嘆氣的行為 * [1:22](https://youtu.be/MyifnUr9vqQ?t=82)確認題目後有舉出例子，確認自己的想法很棒! ## 第二次作業-他評03 - [ ] 可改進的地方 * 不應用有intelli sense的編輯器 => 沒auto complete，error detect、warning才是見真章的時候（第二題沒放後綴名則變純編輯器了） * 50. Pow(x, n) 影片闕失 ### interviewer - [ ] 優點 * 開頭絲滑切入coding interview - [ ] 可改進之地方 * [26:13](https://youtu.be/DDvWYRLwvGs?t=1574)不應該叫interviewee同學(有點危） ### interviewee - [ ] 優點 * 有編寫邊講解、舉例、優化 - [ ] 可改進之地方 * 沒有測試 * 講解的時候可以搭配圖解，那interviewer會更好理解 * 縮排沒弄好看著很不習慣（如果interviewer有強迫症） * [07:30](https://youtu.be/DDvWYRLwvGs?t=469) return 了 break就是多餘的了，上面的num 打錯字編輯器已經提示錯誤了但還是沒發現，在interviewer發呆的過程中很容易被發現 * 講的時間有點長，interviewer可能沒有那麼多時間跟你面試 * LeetCode 50: 你的code放到leetcode跑runtime 3ms應該用非遞歸(runtime 0ms)方式如下： ```cpp double myPow(double x, int n) { if(n<0) x = 1/x; double result =1; while ( n !=0){ if (n%2!=0){ result *= x; } x *= x; n/=2; } return result; } ``` ## 第二次作業-他評05 ### interviewer - [ ] 優點 * 有循序漸進的引導面試者優化程式碼。 - [ ] 可改進之處 * [8:38](https://youtu.be/DDvWYRLwvGs?si=4WmUYFOSPPzqbOU6&t=518): 不該由面試官給出時間複雜度的答案。 ### interviewee - [ ] 優點 * 清楚的解釋自己想法，並善用舉例。 * 口齒清晰，語速洽當 - [ ] 可改進之處 * [0:58](https://youtu.be/DDvWYRLwvGs?si=Er5l_L0o5KbeNwES&t=58): Repeat和Examples還有Approach可以分開。 * [8:18](https://youtu.be/DDvWYRLwvGs?si=iLQVIKwJlFtyu_h8&t=498): 說第一個想法有點奇怪，好像已經確定有很多答案了。