--- title: 2021 年資訊科技產業專案設計課程面試範例 tags: INFO2021 --- # 2021 年「資訊科技產業專案設計」 >貢獻者: 歐帝-Odd > ==[video](https://youtu.be/YiiU9Y3CEek)== # 69. Sqrt(x) ## Easy ## Description Given a non-negative integer `x`, compute and return the square root of `x`. Since the return type is an integer, the decimal digits are **truncated**, and only **the integer part** of the result is returned. **Note**: You are not allowed to use any built-in exponent function or operator, such as `pow(x, 0.5)` or `x ** 0.5`. ### **Example 1:** Input: x = 4 Output: 2 ### **Example 2:** Input: x = 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned. ### **Constraints**: * 0 <= x <= 2^31^ - 1 ## Solution ### sol 1: Time: O(n^1/2^) Space: O(1) #### 說明: > 使用暴力解,從 $n = 1$ 開始找起,利用 while 迴圈進行判斷,若 $n * n$ 小於等於 x ,則 $n = n + 1$,否則回傳 $n - 1$,即為答案。 #### Python: ```python class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ if x <= 1: return x n = 1 while True: if n * n > x: return n - 1 n += 1 ``` ### sol 2: Time: O(logn) Space: O(1) #### 說明: > 使用 binary search,宣告兩個 pointer,分別為 $start$ = 0 和 $end$ = x,接著跑 while 迴圈,令 $pivot = (start + end) / 2$,此時分三個 case: >1. 若 $pivot * pivot$ 大於 x,則搜索範圍為 $start$ 至 $pivot - 1$ 之間,也就是令 $end = pivot - 1$。 >2. 若 $pivot * pivot$ 小於等於 x 且 $(pivot + 1) * (pivot + 1)$ 大於 x,則回傳 $pivot$,此為答案。 >3. 若不為上述兩種情況,則搜索範圍為 $pivot - 1$ 至 $end$ 之間,也就是令 $start = pivot + 1$。 #### Python: ```python class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ start = 0 end = x while True: pivot = (start + end) / 2 if pivot * pivot > x: end = pivot - 1 elif pivot * pivot <= x and (pivot + 1) * (pivot + 1) > x: return pivot else: start = pivot + 1 ``` --- # 169. Majority Element ## Easy ## Description Given an array `nums` of size `n`, return the majority element. The majority element is the element that appears more than `⌊n / 2⌋` times. You may assume that the majority element always exists in the array. ### **Example 1:** Input: nums = [3,2,3] Output: 3 ### **Example 2:** Input: nums = [2,2,1,1,1,2,2] Output: 2 ### **Constraints**: * n == nums.length * 1 <= n <= 5 * 10^4^ * -2^31^ <= nums[i] <= 2^31^ - 1 ## Solution ### sol 1: Time: O(n) Space: O(n) #### 說明: >利用 for 迴圈將所有值跑一遍,並將值的出現次數記錄在 hash table 裡,接著再檢查 hash table 裡的值的出現次數,若出現次數超過 ⌊n / 2⌋,則回傳該值。 #### Python: ```python class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ dic = {} for i in range(len(nums)): if nums[i] not in dic: dic[nums[i]] = 0 dic[nums[i]] += 1 for num in dic: if dic[num] > int(len(nums)/2): return num ``` ### sol 2: Time: $O(n)$ Space: $O(1)$ #### 說明: >因為 nums 當中有值出現次數超過 ⌊n / 2⌋,可利用 Boyer–Moore majority vote algorithm 來找 majority number。 >一開始初始化將 $count$ 及 $majority$ 設為0,利用 for 迴圈對每項值進行判斷,若 $count$ 為 0,則設 $majority$ 為新值,且 $count$ 加上1,代表此新值目前是 $majority$ ,畢竟前面 $count$ 因為非 $majority$ 和 $majority$ 的出現次數互相抵消變為0;若 $count$ 不為 0,則再進行判斷,若新值和 $majority$ 相同,則 $count$ 加上1,否則 $count$ 減掉1。 >最後,回傳 majority 即為答案。 #### Python: ```python class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ majority = 0 count = 0 for i in range(len(nums)): if count == 0: majority = nums[i] count += 1 else: if majority == nums[i]: count += 1 else: count -= 1 return majority ``` --- # 189. Rotate Array ## Medium ## Description Given an array, rotate the array to the right by `k` steps, where `k` is non-negative. ### **Example 1:** Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] ### **Example 2:** Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100] ### **Constraints**: * 1 <= nums.length <= 10^5^ * -2^31^ <= nums[i] <= 2^31^ - 1 * 0 <= k <= 10^5^ ## Solution ### sol 1: Time: O(n) Space: O(n) #### 說明: > 另外宣告一個含有大小為 $len(nums)$ 的一維陣列,去存放第 $i$ 個元素經過 $k$ 步後的位置,也就是第 $(i+k)$ % $len(nums)$ 個位置,完成對每項元素的移動後,即為答案。 #### Python: ```python class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ ans = [0 for i in range(len(nums))] for i in range(len(nums)): ans[(i+k) % len(nums)] = nums[i] for i in range(len(nums)): nums[i] = ans[i] ``` ### sol 2: Time: O(n) Space: O(1) #### 說明: > 首先,定義 $turn$ 為從起點不斷移動 $k$ 步到起點需要經過 $n$ 個點的迴圈,因為一個 $turn$ 需要經過 $n$ 個點,所以每個點移動 $k$ 步需要的 $turn$ 數量為 $len(nums) / n$,Ex: 1,2,3,4,5,6,$k$ = 2,則一個 $turn$ 需經過 3 個點,總共需要的 $turn$ 數量為 6/3 = 2。 >接著,利用 for 迴圈跑 $turn$ 次,對每個 $turn$ 的起點開始,對經過的點往右挪動 $k$ 步至起點,最後可將所有點移動 $k$ 步。 #### Python: ```python= class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ if k == 0 or k == len(nums): return i = -1 turns = 0 while i != 0: if i == -1: i = 0 j = (i - k + len(nums)) % len(nums) turns += 1 i = j turns = len(nums) / turns for i in range(turns): m = -1 temp = nums[i] while m != i: if m == -1: m = i j = (m - k + len(nums)) % len(nums) nums[m] = nums[j] m = j nums[(m+k) % len(nums)] = temp ``` --- # 136. Single Number ## Easy ## Description Given a **non-empty** array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space. ### **Example 1:** Input: nums = [2,2,1] Output: 1 ### **Example 2:** Input: nums = [4,1,2,1,2] Output: 4 ### **Example 3:** Input: nums = [1] Output: 1 ### **Constraints**: * 1 <= nums.length <= 3 * 10^4^ * -3 * 10^4^ <= nums[i] <= 3 * 10^4^ * Each element in the array appears twice except for one element which appears only once. ## Solution ### sol 1: Time: O(n) Space: O(n) #### 說明: >先利用 for 迴圈跑完所有值,並使用 hash table 記錄各值出現的次數,若某值出現的次數為1,則回傳該值。 #### Python: ```python= class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ dic = {} for i in range(len(nums)): if nums[i] not in dic: dic[nums[i]] = 0 dic[nums[i]] += 1 for num in dic: if dic[num] == 1: return num ``` ### sol 2: Time: O(n) Space: O(1) #### 說明: >根據 Xor 的原理,兩個相同數字轉成二進制後,經過 Xor 結果為 0,Ex: 5 ^ 5 = 101 ^ 101 = 0。此外,任意數字 Xor 0,結果為該任意數字,Ex: 5 ^ 0 = 101 ^ 000 = 101 = 5。因此,利用 for 迴圈將所有數字經過 Xor,結果可得只有出現 1 次的數字。 #### Python: ```python= class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ single = 0 for i in range(len(nums)): single = single ^ nums[i] return single ``` --- # 268. Missing Number ## Easy ## Description Given an array nums containing `n` distinct numbers in the range `[0, n]`, return the only number in the range that is missing from the array. ### **Example 1:** Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums. ### **Example 2:** Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums. ### **Example 3:** Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums. ### **Example 4:** Input: nums = [0] Output: 1 Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums. ### **Constraints**: * n == nums.length * 1 <= n <= 10^4^ * 0 <= nums[i] <= n * All the numbers of nums are **unique**. ## Solution ### sol 1: Time: O(n) Space: O(n) #### 說明: >建立一維陣列 $checklist$,此陣列記錄出現過的值,裡面包含 $len(nums)+1$ 個元素,也就是 0 至 n,預設全部元素值為 True,接著利用 for 迴圈,若 $nums$ 裡的值 $num$ 存在於 $checklist$,則將 $checklist[num]$ 設為 False,最後檢查 $checklist$,若 $checklist[i]$ 值為 True,則回傳 $i$。 #### Python: ```python= class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ checklist = [True for i in range(len(nums)+1)] for num in nums: checklist[num] = False for i in range(len(nums)+1): if checklist[i]: return i ``` ### sol 2: Time: O(n) Space: O(1) #### 說明: >利用梯形公式可得知所有數之總和 $total$ = (1 + $len(nums)$) * $len(nums)$ / 2 ,因此利用 for 迴圈將 $nums$ 出現過的數從 $total$ 中扣除,最後剩餘的數即為 missing number。 #### Python: ```python= class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ ans = (1 + len(nums)) * len(nums) / 2 for i in range(len(nums)): ans -= nums[i] return ans ``` --- # 75. Sort Colors [17:43](https://youtu.be/ITeqSw_BIFk?t=1063) ## Medium ## Description Given an array `nums` with `n` objects colored red, white, or blue, sort them **in-place** so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers `0`, `1`, and `2` to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function. ### **Example 1:** Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] ### **Example 2:** Input: nums = [2,0,1] Output: [0,1,2] ### **Example 3:** Input: nums = [0] Output: [0] ### **Example 4:** Input: nums = [1] Output: [1] ### **Constraints**: * n == nums.length * 1 <= n <= 300 * nums[i] is 0, 1, or 2. ## Solution ### sol 1: Time: O(n) Space: O(1) Two-pass #### 說明: >宣告一個大小為 3 的一維陣列 $counting$,此陣列用來儲存 0, 1, 2 的出現次數,最後利用 for 迴圈,依照 0, 1, 2 的順序將各數出現次數分別儲存在 $nums$,也就是 $i$ 會出現 $counting[i]$ 次,其中 $i \in$ {0, 1, 2}。 #### Python: ```python= class Solution(object): def sortColors(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ counting = [0, 0, 0] for i in range(len(nums)): counting[nums[i]] += 1 for i in range(len(nums)): if i < counting[0]: nums[i] = 0 elif i >= counting[0] and i < counting[0] + counting[1]: nums[i] = 1 else: nums[i] = 2 ``` ### sol 2: Time: O(n) Space: O(1) One-pass #### 說明: >先宣告三個指標 $i$ = 0, $point0$ = 0 和 $point2$ = $len(nums)$ - 1,$point0$ 代表 0 的位置,而 $point2$ 代表 2 的位置,再利用 while 迴圈跑遍 $nums$ 的值,根據 $nums[i]$ 的值有三個判斷條件: >若 $nums[i]$ 為 0,代表此值必須與 $point0$ 的位置交換,接著更新 $i$ = $i$ + 1 及 $point0$ = $point0$ + 1 值;若 $nums[i]$ 為 2,代表此值必須與 $point2$ 的位置交換,接著更新 $point2$ = $point2$ - 1 值,注意這邊 $i$ 值不需要再加 1,因為有可能交換來的值為 0;若$nums[i]$ 為 1,則無視此值並更新 $i$ = $i$ + 1 。 >此 while 迴圈的中止條件為 $i$ > $point2$,代表所有值已尋過一遍,並且 $nums$ 已完成排列。 #### Python: ```python= class Solution(object): def sortColors(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ def swap(nums, a, b): temp = nums[a] nums[a] = nums[b] nums[b] = temp i = 0 point0 = 0 point2 = len(nums) - 1 while i <= point2: if nums[i] == 0: swap(nums, i, point0) i += 1 point0 += 1 elif nums[i] == 2: swap(nums, i, point2) point2 -= 1 else: i += 1 ``` --- # 229. Majority Element II ## Medium ## Description Given an integer array of size `n`, find all elements that appear more than `⌊ n/3 ⌋` times. ### **Example 1:** Input: nums = [3,2,3] Output: [3] ### **Example 2:** Input: nums = [1] Output: [1] ### **Example 2:** Input: nums = [1,2] Output: [1,2] ### **Constraints**: * 1 <= nums.length <= 5 * 10^4^ * -10^9^ <= nums[i] <= 10^9^ ## Solution Time: O(n) Space: O(1) #### 說明: >使用Boyer–Moore majority vote algorithm 來找 majority number。這次使用兩個變數記錄兩種不同的數字,因為最多有 2 個數字超過 ⌊n / 3⌋ 次,再根據 [169. Majority Element](#說明9) 的概念找最多和次多的數字,再看這兩個數字的出現次數是否超過 ⌊n / 3⌋ 次,把超過的數字加入陣列並回傳,即為答案。 #### Python: ```python= class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: List[int] """ rlist = [] m, n, count_m, count_n = 0, 0, 0, 0 for i in range(len(nums)): if m == nums[i]: count_m += 1 elif n == nums[i]: count_n += 1 elif count_m == 0: m = nums[i] count_m += 1 elif count_n == 0: n = nums[i] count_n += 1 else: count_m -= 1 count_n -= 1 count_m, count_n = 0, 0 for i in range(len(nums)): if nums[i] == m: count_m += 1 if nums[i] == n: count_n += 1 if count_m > int(len(nums)/3): rlist.append(m) if count_n > int(len(nums)/3) and m != n: rlist.append(n) return rlist ``` --- # 41. First Missing Positive ## Hard ## Description Given an unsorted integer array `nums`, return the smallest missing positive integer. You must implement an algorithm that runs in `O(n)` time and uses constant extra space. ### **Example 1:** Input: nums = [1,2,0] Output: 3 ### **Example 2:** Input: nums = [3,4,-1,1] Output: 2 ### **Example 2:** Input: nums = [7,8,9,11,12] Output: 1 ### **Constraints**: * 1 <= nums.length <= 5 * 10^5^ * -2^31^ <= nums[i] <= 2^31^ - 1 ## Solution Time: O(n) Space: O(1) #### 說明: ![](https://i.imgur.com/VZIS8dY.png) >此題需要找最小的 missing positive number,其值必介於 $1$ 至 $len(nums)+1$ 之間,為了使空間複雜度為 O(1),我們可以在原陣列進行標記,當 $nums$ 裡有值 $num$ 介於 $1$ 至 $len(nums)$ 之間,我們將第 $|num|-1$ 個值加上負號(因為陣列編號為 0 開始),負號代表此 $num$ 存在,最後依據負號找最小的 missing positive number。作法如下: >1. 首先初始化,使用 for 迴圈將 $nums$ 裡小於等於 0 或大於 $len(nums)$ 的值改成 $len(nums)+1$。 > >2. 接著,使用 for 迴圈跑 $nums$ 裡的值 $num$,若 $|num|$ 介於 $1$ 至 $len(nums)$ 之間,且第 $|num|-1$ 個值不為負(為負代表此值已存在,不需要加上負號,以免負負為正),我們將第 $|num|-1$ 個值加上負號。 > >3. 最後,使用 for 迴圈跑 $nums$ 裡的值 $nums[i]$,若有值 $num[i]>0$,代表 $i+1$ 為最小的 missing positive number,回傳 $i+1$;若跑完迴圈發現無值 $num[i]>0$,代表 $1$ 至 $len(nums)$ 都存在,代表 $len(nums)+1$ 為最小的 missing positive number,回傳 $len(nums)+1$。 #### Python: ```python= class Solution(object): def firstMissingPositive(self, nums): """ :type nums: List[int] :rtype: int """ n_len = len(nums) for i in range(n_len): if nums[i] <= 0 or nums[i] > n_len: nums[i] = n_len + 1 for i in range(n_len): num = abs(nums[i]) if num <= n_len and nums[num-1] > 0: nums[num-1] *= (-1) for i in range(n_len): if nums[i] > 0: return i + 1 return n_len + 1 ``` # 初步檢討 >1. 在撰寫 code 時,有些 code 是重複的,Ex: for i in range(len(nums)):,為了避免寫code時無聲,應該使用 ctrl+c 和 ctrl+v。 >2. 講英文時卡卡的,應先想好再說明。 >3. 講解範例時,應能一邊在螢幕上打字示意,一邊說明,才能使聽者易於理解題目及講者之意。 ## 第三次作業 - 他評 ### Interviewer #### 可改進 - 應該和interviewee對當前題目有更多的溝通或是改進。 - Interviewer應該更多的和interviewee做一些溝通,而不是像出考題一樣。 ### Interviewee #### 優點 - coding時搭配解釋,使interviewer更了解code的內容。 #### 可改進 - 畫面不清楚,應該放大畫面。 - 在repeat考題的階段,可以向interviewer討論一些題目的限制或是特例,並且在整體應該很多的和interviewer討論。 - 在approach階段應該搭配畫面描述或是搭配範例,否則interviewer無法清楚了解解題方案。 - 一邊解釋一邊coding很不錯,但有時不需每個細節都解釋,以免耗費太多時間。 - 在進行完coding,沒有進一步對code做簡單的驗證。 ## 第三次作業 - 他評2 畫面字體應該再放大。 第一題: 1. Interviewer 直接給題目,容易讓背答案的人直接寫出來。 2. Interviewee 重複題目的時候只要講大概的意思就好,不用完全重複。 3. Interviewer 在對方講出要用暴力解的時候,應可以直接引導給出更好的答案。 4. Interviewer 基本上沒有互動。 第二題: 1. Interviewer 直接給題目,容易讓背答案的人直接寫出來。 2. Interviewee 在給例子的時候可以在螢幕上打出來,而不是只是用念的。 3. Interviewee 應用更嚴謹的說法表達時間複雜度為 O(n) 等級,而不是直接說時間複雜度是 O(n)。應該清楚的表達空間複雜度為 O(n),而不是說用到的 space 是O(n) 4. Interviewee 講解所用的演算法的時候講的不清楚,如何進行抵銷、判斷等步驟,對第一次聽到這個演算法的人來說並沒有辦法從解釋中知道演算法具體如何實現。 第三題: 1. Interviewer 直接給題目,容易讓背答案的人直接寫出來。 2. Interviewee 應該確認移動後的陣列是否是把移出陣列的值填充到陣列開頭。 3. Interviewee 口語上不要講這樣子那樣子,用更明確清晰的方法表達。 4. Interviewee 講解程式的時候應該更多的解釋該行程式的意圖,而不是單純復述一遍寫了什麼東西。 5. Interviewer 在對方寫完之後,沒有講說到底哪裡做得不錯,或者哪裡做得不好。 ## 第三次作業 - 他評3 interviewee [01:20](https://youtu.be/YiiU9Y3CEek?t=80s) 建議將舉例和 approach 都大概寫下讓 interviewer 可以直接看到,不然只用聽的很容易 miss [02:34](https://youtu.be/YiiU9Y3CEek?t=154s) 畫面太小 [03:12]((https://youtu.be/YiiU9Y3CEek?t=192s)) 建議不要用 leetcode,面試沒有測資可以跑,應用自己的舉例測試 [03:44](https://youtu.be/YiiU9Y3CEek?t=224s) 可以先分析自己為什麼用前一個解法、再解釋為什麼選用 bst [04:43](https://youtu.be/YiiU9Y3CEek?t=283s) 應念為 big o [04:49](https://youtu.be/YiiU9Y3CEek?t=289s) 可以解釋為何時間複雜度為 O(logn)、為何空間複雜度為常數。 [10:20](https://youtu.be/YiiU9Y3CEek?t=620s) 這裡真的滿像在背答案,應多和 interviewer 討論 [23:30](https://youtu.be/YiiU9Y3CEek?t=1410s) 要多跟 interviewer 討論 interviewer [00:30](https://youtu.be/YiiU9Y3CEek?t=30s) 建議 interviewer 不要直接問題目 [3:24](https://youtu.be/YiiU9Y3CEek?t=204s) 建議詢問 interviewee 如何加快,而不是直接說時間複雜度是多少 [7:42](https://youtu.be/YiiU9Y3CEek?t=462s) 可以再和 interviewee 多討論是否有其他 corner case [13:30](https://youtu.be/YiiU9Y3CEek?t=810s) 讓 interviewee 自己分析空間複雜度 ## 第三次作業 - 他評4 ### Interviewee #### 優點: * 有做REACTO * 解說自己的code滿清楚且流暢 #### 可改進: * 字有點太小,看不太到 * 舉例時可以把所舉的例子打在螢幕上,會更好理解 ### Interviewer #### 可改進: * 聽到Interviewee所提出的第一種方法時,應該就可以直接問他有沒有更快的方法,並請他說明更快的方法,以解省面試時間 * 看完interviewee的code可能可以給一些commend * 可能可以多問一些延伸性的問題,例如X開3次方或是X開n次方的通解等等,而不是只問有沒有更快的做法