2023年「資訊科技產業專案設計」面試範例

# 2023 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2023)」作業1 #### 查理-Charlie #### :rabbit: : 我 #### :koala: : 面試官 [影片連結1](https://www.youtube.com/watch?v=1nnOhOPQjjo) [影片連結2](https://www.youtube.com/watch?v=BJ07ibbmG_4) [影片連結3](https://www.youtube.com/watch?v=3UpdAWzoE0A) ## **704. Binary Saerch** ### **模擬面試過程** #### :koala: : 題目會給你一組數列，和一個目標數字，希望你能從數列中找出目標數字並回傳他的索引。若是目標數字不在這組數列中，則回傳-1。 #### :koala: : 請問你對題目有疑問嗎？ #### :rabbit: : 有，我想請問輸入的數列有經過排序嗎？ #### :koala: : 有的，題目輸入的數列經過升冪排序。 #### :rabbit: : 好的，爲了確認我對題目的理解，我想用一個例子説明 :::info 輸入： [-1,0,3,4,9,10] 目標數 : 9 輸出： 4 ::: #### :rabbit: : 請問我的理解正確嗎？ #### :koala: : 正確，你可以開始寫你的程式了。 #### :rabbit: : 在寫程式之前，我想先講一下我的想法。 #### :rabbit: : 這題最直觀的作法是從第一個數開始遍歷整個數列，找到目標值或者大於目標值時停止。 ```C++= int search(vector<int>& nums, int target) { for (int i = 0; i < nums.size();i++){ if (nums[i] == target){ return i; } else if (nums[i]> target){ return -1; } } return -1; } ``` #### :rabbit: : 這個方法很直觀，但是當資料很多筆時，因為時間複雜度是O(n)可能會造成運算時間太長。 #### :koala: : 沒錯，那若是時間複雜度限制為O(log n)，你會如何優化? #### :rabbit: : 若是有時間複雜度的限制條件下，我會使用二分搜尋法做這道題，在左右各設一個邊界，將邊界值相加除以二後的中間值和目標做比較，若中間值大於目標值則將右邊界往內，若中間值小於目標值則將左邊界往內，反覆測試得到和目標相同的數值。 ```C++= int search(vector<int>& nums, int target) { int left = 0; int right = nums.size()-1; while(left <=right){ int mid = (left + right)/2; if (nums[mid] > target){ right = mid-1; } else if (nums[mid] < target ){ left = mid+1; } else { return mid;} } return -1; } ``` --- ## **11. Container With Most Water** ### **模擬面試過程** #### :koala: : 題目給你一組整數數列，有 n 條垂直線被繪製，每條線的兩個端點分別是 (i, 0) 和 (i, height[i])。找到兩條線使其與x軸形成的面積最大。 #### :koala: : 請問你對題目有疑問嗎？ #### :rabbit: : 有，我想請問輸入的數列有經過排序嗎？ #### :koala: : 沒有，題目預設輸入的數列為隨機分配。 #### :rabbit: : 好的，爲了確認我對題目的理解，我想用一個例子説明 ![](https://hackmd.io/_uploads/HJjMh_ryT.png) :::info 輸入 : [1,8,6,2,5,4,8,3,7] 輸出 : 49 ::: #### :rabbit: : 請問我的理解正確嗎？ #### :koala: : 正確，你可以開始寫你的程式了。 #### :rabbit: : 在寫程式之前，我想先講一下我的想法。 #### :rabbit: : 這題最直觀的作法是窮舉法，列舉出所有的面積，再比較出最大的面積。我會使用兩個迴圈來做。 ```C++= int maxArea(vector<int>& height) { int res = 0; int n = height.size(); for(int i=0; i<n; i++) { for(int j=i+1; j<n; j++) { int tmp = (j-i)*min(height[i], height[j]); res = max(res, tmp); } } return res; } ``` #### :koala: :這麼做雖然能達成題目要求，但是有很大的改進空間，你能使用其他方法優化嗎? #### :rabbit: : 另一種方法我會使用two pointer 的方法來做。在寫程式之前，我想先講一下我的想法。首先在頭尾各放一個指標，指標指著兩個最高的柱子有可能形成更大的面積，然而將指標內縮時可能會造成面積變小，因此我們期待內縮後的柱子是更高的，才能機會得到更大的面積，所以我會移動高度較小的一邊。 ```C++= int maxArea(vector<int>& height) { int i = 0; int j = height.size() - 1; int max_area = 0; while (i < j) { int cur_area = min(height[i], height[j]) * (j - i); max_area = max(max_area, cur_area); if (height[i] < height[j]) { i++; } else { j--; } } return max_area; } ``` #### :rabbit: :這麼做的時間複雜度為O(n)，運行效率比第一種方法好很多。 --- ## **136. Single Number** ### **模擬面試過程** #### :koala: : In this question, you are given a non-empty array of integers nums, every element appears twice except for one. Find that single one. #### :koala: : Do you have any questions ? #### :rabbit: : Yes. Has the array been sorted? #### :koala: : No,they aren’t. Is there any questions? #### :rabbit: : I think no. I would like to use one example to check my understanding about this question. :::info input ： [3,1,5,5,3] output ： 1 ::: #### :rabbit: : Am I correct about this question? #### :koala: : Yes. You can start codding now. #### :rabbit: : I want to explain my thoughts about this problem first. #### :rabbit: : I will start at organize the array into a ascending series, then I'll compare the first and the second numbers. If they're not equal then it means the first number is single, s I find the single number. #### :rabbit: : If they're equal then I'll skip to the fourth number and compare it to the third. This is because the numbers either appear twice or once. If all the elements except the last one are pairs, then the single number is the last one. ```C++= int singleNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i =1;i<nums.size();i+=2){ if (nums[i]!= nums[i-1]) return nums[i-1]; } return nums[(nums.size()-1)]; } ``` #### :koala: : So your first approach is to compare all the numbers in the array. Can you use more effective methods? #### :rabbit: :Yes, I can use bit operator to solve this question. #### :rabbit: : We all know that XOR comply with commutative laws and distributive law. And most importantly ,any number XOR with 0 will become itself. So by the very nature of XOR, I can solve the problem quickly. ``` int singleNumber(vector<int>& nums) { int A = nums[0]; for(int i =1;i<nums.size();i++){ A = nums[i] ^ A; } return A; } ``` --- ### **模擬面試檢討** ### **自評** 704. Binary Saerch interviewer: 1. [0:34](https://www.youtube.com/watch?v=1nnOhOPQjjo#t=0m34s) 可以加入一些肢體動作，不應該只是呆坐著。 2. [5:07](https://www.youtube.com/watch?v=1nnOhOPQjjo#t=5m07s) 不該直接問「時間複雜度為...的時候該怎麼做」，避免interviewee背誦或猜測。 3. 沒有後續的問題和程式碼討論，interviewer 沒有表現出有鑑別interviewee能力的行為。 interviewee: 1. 整體口齒可以更清晰。 2. 一邊打程式一邊解說時，聲音會越來越小。 3. [2:58](https://www.youtube.com/watch?v=1nnOhOPQjjo#t=2m58s) 打程式時發生打錯字，或者漏打，應該多練習打程式的速度和正確率 4. [5:58](https://www.youtube.com/watch?v=1nnOhOPQjjo#t=5m58s) 說話聲音有時會忽大忽小。 --- ### **自評** 11. Container With Most Water interviewer: 1. [0:49](https://www.youtube.com/watch?v=BJ07ibbmG_4#t=0m49s) interviewer應該清楚說明關於輸入的數值範圍等等限制，過多的停頓顯得沒有自信。 interviewee: 1. [1:25](https://www.youtube.com/watch?v=BJ07ibbmG_4#t=1m25s) 拿滑鼠的聲音太大聲了。 2. 整體口齒可以更清晰。 3. [3:30](https://www.youtube.com/watch?v=BJ07ibbmG_4#t=3m30s) 多練習打程式的正確率，避免在小地方發生錯誤。 4. [4:26](https://www.youtube.com/watch?v=BJ07ibbmG_4#t=4m26s) 說話聲音有時會忽大忽小。 5. [5:10](https://www.youtube.com/watch?v=BJ07ibbmG_4#t=5m10s) [8:32](https://www.youtube.com/watch?v=BJ07ibbmG_4#t=8m32s) 不該太依賴手勢去解釋思路。 7. 一邊打程式一邊解說時，聲音會越來越小。 --- ### **自評** 136. Single Number interviewer: 1. [0:05](https://www.youtube.com/watch?v=3UpdAWzoE0A#t=0m5s) array 念錯了 2. 聲音太小 interviewee: 1. [1:05](https://www.youtube.com/watch?v=3UpdAWzoE0A#t=1m5s) 避免不必要的手勢。 2. [1:45](https://www.youtube.com/watch?v=3UpdAWzoE0A#t=1m45s) 聲音太小，而且講話不清楚。 3. [2:20](https://www.youtube.com/watch?v=3UpdAWzoE0A#t=2m20s) 不應該只是唸出程式碼。 4. [2:50](https://www.youtube.com/watch?v=3UpdAWzoE0A#t=2m50s) 程式碼打錯，要多練習正確率。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.