---
title: 2021 年資訊科技產業專案設計課程面試範例
tags: INFO2021
---
# 2021 年「資訊科技產業專案設計」
>貢獻者 ：享辨薔
> ==[video](https://youtu.be/oE8Fk2EsU-U)==
### 9 . [Palindrome Number](https://leetcode.com/problems/palindrome-number/)(Easy)
```
Given an integer x, return true if x is palindrome integer.
An integer is a palindrome when it reads the same backward as forward.
For example, 121 is palindrome while 123 is not.
```
Example 1:
Input: x = 121
Output: true
Example 2:
Input: x = -121
Output: false
Explanation:
From left to right, it reads -121.
From right to left, it becomes 121-.
Therefore it is not a palindrome.
#### 初步解題
這應該是接觸程式題目，簡單的判斷輸入的內容是否滿足**迴文**的條件有趣的是這邊輸入的是**數字**而不是單純的字串想法就是先將數字轉成字串在進行條件判斷
```csharp=
public class Solution {
public bool IsPalindrome(int x) {
string x_tmp = x.ToString();
int length = x_tmp.Length;
bool result = true;
int last_indice = length-1;
for(int i=0 ; i<length/2 ; i++){
if (x_tmp[i] != x_tmp[last_indice]){
result = false;
break;
}
last_indice-=1;
}
Console.WriteLine(x_tmp[0]);
return result;
}
}
```
邏輯的部分非常簡單，只是先將數字用c#內建的函式轉換成字串再從頭尾一一判斷是否有不同，一有不同就直接結束迴圈。
缺點是效能部分有點差，再來思考怎麼樣能增加效能
#### 改善
從題目的敘述大概可以想到只要是**小於0**，因為必須將**負號**也要考慮進去，因此轉換成字串形式整個字串的開頭一定為 **-** 由此可判定 **小於0** 的數字一定不符合。
```csharp=
public class Solution {
public bool IsPalindrome(int x) {
if(x < 0) return false;
string x_tmp = x.ToString();
int length = x_tmp.Length;
bool result = true;
int last_indice = length-1;
for(int i=0 ; i<length/2 ; i++){
if (x_tmp[i] != x_tmp[last_indice]){
result = false;
break;
}
last_indice-=1;
}
Console.WriteLine(x_tmp[0]);
return result;
}
}
```
利用餘數的特性例如以數字**1221**來舉例取餘數之後可以得到**1** 再次取餘數之後可以得到**2** 因此可以利用餘數的特性來將字串做分割與處理
```csharp=
public class Solution {
public bool IsPalindrome(int x) {
//for x<0 and x end with 0
if(x < 0 || (x % 10 == 0 && x != 0)) {
return false;
}
int reverse_num = 0;
while(x > reverse_num) {
reverse_num = reverse_num * 10 + x % 10;
x /= 10;
}
//for odd number
return x == revertedNumber || x == revertedNumber/10;
}
}
```
### 35. [Search Insert Position](https://leetcode.com/problems/search-insert-position/)(Easy)
Given a sorted array of distinct integers and a target value, return the index if the target is found.
If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
#### 初步解題
從題目的敘述可以大概猜得出來，要找出**target**應該插入的位置，第一個想法就是使用一個迴圈將所有內容看過一次。以時間複雜度上來說需要看過整個陣列才可以做判斷，因此會是**O(n)**
```csharp=
public class Solution {
public int SearchInsert(int[] nums, int target) {
for(int i=0 ; i<=nums.Length-1 ; i++){
if(nums[i]>=target){
return i;
}
}
return nums.Length;
}
}
```
#### 改善
初步的想法會用**Binary Search**去做，但是前提是陣列內容必須已經排序過，所幸在題目的假設下已經將輸入的陣列做好排序。再已排序的陣列下可以直接進行二元搜尋。這樣可以改善原本**O(n)**的時間複雜度成**O(logN)**。
```csharp=
public class Solution {
public int SearchInsert(int[] nums, int target) {
int arr_length = nums.Length;
int start_indice = 0;
int end_indice = arr_length-1;
while(start_indice <= end_indice){
int middle = end_indice + (start_indice - end_indice)/2;
if(nums[middle]==target){
return middle;
}
else if (nums[middle]<target){
start_indice = middle + 1;
}
else{
end_indice = middle -1;
}
}
return start_indice;
}
}
```
假設說輸入的陣列沒有被排序過，就沒有辦法直接使用**Binary Search** 來進行搜尋，必須要先將整個陣列先排序過。 因此如果是沒有排序過的陣列整體的時間複雜度還會再上升。 以**Quick Sort** 來排序在進行搜尋，整體的時間複雜度會變成**O(logN)* O(NlogN)**
### 58. [Length of Last Word](https://leetcode.com/problems/length-of-last-word/) (Easy)
```
Given a string s consisting of some words separated by some number of spaces, return the length of the last word in the string.
A word is a maximal substring consisting of non-space characters only.
```
Example 1:
Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.
#### 初步解題
想法很明確，看到題目敘述字串中只會出現**小寫**的**英文字母**跟**空白**可以直接從最後一個字元開始讀，用一個全域的變數只要一碰到空白就歸零，紀錄從後面數來第一個連續字元的大小
```csharp=
public class Solution {
public int LengthOfLastWord(string s) {
int length = s.Length;
int str_length = 0;
for(int i=length-1 ; i>=0 ; i--){
if(s[i] == ' '){
if(str_length == 0) continue;
else return str_length;
}
str_length++;
}
return str_length;
}
}
```
#### 改善
假設說題目改成以大小寫混用的話其實也不太需要修改，假設說改成要求成紀錄**長度最長的字子串**的話，需要把整個字串都走一次，
### 66. [Two Sum](https://leetcode.com/problems/two-sum/)
```
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
```
#### 初步解題
這應該算是所有leetcode人的的新手村，算是系列裡面的基本題目，題目已經設計好只會剛好有一個解，一開始的想法是用兩個迴圈然後去分別看哪兩個數值加起來剛好跟目標一樣
```csharp=
public class Solution {
public int[] TwoSum(int[] nums, int target) {
int nums_length = nums.Length;
for(int i=0 ; i<=nums_length-1 ; i++){
for(int j=i+1 ; j<=nums_length-1 ; j++){
if((nums[i] + nums[j]) == target)
{
return new int[2]{i, j};
}
}
}
return new int[2];
}
}
```
#### 改善
看到其他人的[分享](https://leetcode.com/problems/two-sum/discuss/17/Here-is-a-Python-solution-in-O(n)-time)可以利用map的方式因為題目已經假設
### 8. [String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/) (Medium)
```
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++'s atoi function).
The algorithm for myAtoi(string s) is as follows:
Read in and ignore any leading whitespace.
Check if the next character (if not already at the end of the string) is '-' or '+'. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
Read in next the characters until the next non-digit charcter or the end of the input is reached. The rest of the string is ignored.
Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -231 should be clamped to -231, and integers greater than 231 - 1 should be clamped to 231 - 1.
Return the integer as the final result.
```
#### 初步解題
題目的意思算是蠻清楚的，就是要實作將字串轉成數字的功能。前面的題目我們都可以用語言內建的函式來做這件事，這次我們要實作這個功能，想法不外乎從頭開始讀取每一個字元尤其是**正負號**
需要注意的部分是有可能出現**int**範圍以外的數字要以**int能表達的最大最小值**來表示因此要多一個區塊去判斷數字是否超越範圍
```csharp=
public class Solution {
public int MyAtoi(string s) {
int i = 0;
int sign = 1;
int result = 0;
int str_length = s.Length;
while(i < str_length && s[i] == ' '){
i++;
}
if(i < str_length && (s[i]=='-' || s[i]=='+'))
if(s[i++]=='-'){
sign = -1;
}
else{
sign = 1;
}
while (i < str_length && s[i]>='0' && s[i]<='9' ){
if(( result > Int32.MaxValue /10 )||(result== Int32.MaxValue/10 && s[i]-'0'>Int32.MaxValue%10)){
return (sign==1)? Int32.MaxValue : Int32.MinValue;
}
result = result*10 + (s[i++]-'0');
}
return result*sign;
}
}
```
#### 改善
### 11. [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) (Medium)
```
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai).
n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0).
Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.
```
```
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].
In this case, the max area of water (blue section) the container can contain is 49.
```
#### 初步解題
題目的敘述如果用圖像去想像的話會比較容易，從最左跟最右一一比較，把所以有任兩個所形成的區域的水量用一個變數紀錄下來，
```csharp=
public class Solution {
public int MaxArea(int[] height) {
int max_area = 0;
int n = height.Length;
int length = n-1;
int right = length;
int left = 0;
while(left<right){
max_area = Math.Max(max_area,Math.Min(height[left],height[right])*length);
if(height[left] < height[right]){
left = left+1;
}
else{
right = right-1;
}
length = length-1;
}
return max_area;
}
}
```
#### 改善
:::info
:information_source: **初步檢討**
1. 在回答問題時有時太過冗長，可能是基於想把問題敘述回答完整。但超過35秒的回答範疇。
2. 在英語回答時有些不通順，聽起來像是結巴，因此拖延到整體的回答時間。
3. 在問答的攻防上沒有辦法像影片中不斷來回討論，可能是對問題還沒有完整的了解。
:::
# Week3
:information_source: **漢語**
### 9 . [Palindrome Number](https://leetcode.com/problems/palindrome-number/)(Easy)
1. 如果是針對字串怎麼做?
2. 如果不用內建函數怎麼做?(No answer)
3. 如何利用數字的特性(利用餘數)
### 58. [Length of Last Word](https://leetcode.com/problems/length-of-last-word/) (Easy)
1. 假設說我今天要找整個最大的子字串怎麼做?
2. 假設說char包含大小寫要多考量什麼?
3. 除了O(n)還有更快的方法嗎?
:information_source: **英語**
### 66. [Two Sum](https://leetcode.com/problems/two-sum/)
1. 假設說不只一個解要回傳所有解怎麼做?
2. 題目如果改成3 sum做法一樣嗎
3. 增加效率
### 35. [Search Insert Position](https://leetcode.com/problems/search-insert-position/)(Easy)
1. 假設字串沒有排序過應該怎麼做?
2. 如果沒有排序過時間複雜度會是?
## 改善
在製作影片的過程中發現自己常常誤把面試當成考試，覺得只要快狠準的答題便可無往不利。在老師提到"你的同事會是你一天相處最久的人" 才恍然大悟，應該把它當成找夥伴更為合適。
:::info
:information_source: **檢討**
:+1: Good
1. 比起第一次作業比較有完整的攻防。
2. 除了寫程式之外還有舉例說明整體架構較為完整。
3. 有提出更多如延伸問題等等
4. Interviewee在撰寫程式之前有先討論想法等等，而非埋頭寫程式
:::
:::danger
:-1: Bad
1. Interviewer回答語意較為含糊不清 如:"不錯" "感覺可以"
2. 針對概念簡單的題目Interviewee可能花過多時間在舉例
3. 寫程式的過程中比較缺乏互動，容易被判斷是死背
4. Interviewer應該詢問更有技巧而非像是考試般問答
:::
----
## 第三次作業 - 他評
### Interviewer
#### 優點
- 講解題目跟引導面試流程很像真實的面試 :smile:
- follow up 的延伸也很符合真實情況
- 給予 interviewee 提示引導，而不是直接講改進方法 :+1:
#### 可改進
- follow up 時， interviewee 沒有講完 approach 就直接開始寫 code，如突然冒出 reverse_num 的部分就該打斷並提問是怎麼想到這的
- interviewee 在 edge case 討論太快可以打斷並且深入討論
- 沒有提問 complexity
- 可以提出讓 interviewee 用 example 簡單 test 他的 solution
### Interviewee
#### 優點
- 善用 pseudo code 輔助解釋 approach
#### 可改進
- 一開始沒有重複問題，這步驟可以避免自己和 interviewer 之間的認知落差
- 沒有確認 input 限制，如 input 有小數點之情況
- 沒有用 example 幫助自己了解題目，這步驟可以讓自己儘早發現 edge case
- function signature 可以先和 interviewer 確認
- 很明顯在看旁邊的答案或參考 XD，真實面試時應避免這種明顯的視線移動
- 背/抄答案的感覺有點重
- 寫程式過程太安靜，可以簡單口述現在在寫的內容
- 可以使用 "early return" 讓程式更 clean 如
```cpp=
bool isPalindrome(string str) {
int n = str.size();
int left = 0, right = n-1;
while(left < right) {
if(str[left] != str[right])
return false; // early return
left ++;
right --;
}
return true;
}
```
- follow up 沒有講完 approach 再開始寫 code，舉例說 interviewee 在 5:18 突然說要用 reverse_num，完全不知道哪來的想法，很像在背答案
- edge case 可以再加以描述
- 就算 interviewer 沒有主動提 complexity，身為 interviewee 也該主動描述一下
- 第二題和第一題一樣缺少了 REACTO 裡的很多步驟
- 第二題的程式碼有錯
- 整體來說背/抄答案的感覺真的很重 XDD
## 第三次作業 - 他評 02
### Interviewer
#### 優點
- 題目講述很清楚，要求與輸出都說的很明白。
- 遇到interviee回答不出來的時候會適時給提示，很像真實面試的情況。
#### 可改進的地方
- 可能需要帶個麥克風或是用麥的耳機錄音，不然聲音太小了，還有很多回音，沒辦法聽清楚。
### Interviewee
#### 優點
- 舉例算很清楚而且簡潔。
- 方法有用pseudo code說明。
#### 可改進的地方
- 看答案的偷喵有點明顯，視線偏移可以改善一下。
- 撰寫程式時，感覺是在參考答案，像是一層一層寫下來。
- 有時撰寫程式碼時，需要口述自己在寫的部分，讓interviewer知道你現在正在做什麼。
## 第三次作業 - 他評 03
### Interviewer
#### 優點
- 會在對方解題卡住時給予引導，影片後半段也會根據題型做一些題目的變化
- 在說明題目的同時也會順便給予一些例子，可以幫助對方了解問題
#### 可改進的地方
- 在題目的敘述上很容易讓對方知道是leetcode的哪一種題型
- 提示餘數給得有點明顯XD，講到數字的特性應該就可以了
### Interviewee
#### 優點
- 錄影畫面可以很清晰看到程式碼與撰寫時的動作
- 會使用一些虛擬程式碼來協助雙方理解解題的順序與邏輯
#### 可改進的地方
- 轉寫程式過程中可以適當的穿插話語，解釋目前的動作，也可以避免長時間的沉默讓對方失去注意力
- 撰寫程式碼的順序過於順暢，看來不太像是在邊寫邊思考的情境下寫出來的。可以先寫好主要的功能如迴圈之後，再回到上方寫考慮例外或可以減少運算成本的判別式
## 第三次作業 - 他評 04
### Interviewer
#### 優點
* 提問時有用一些例子協助理解。
#### 可改進的地方
* [0:07](https://youtu.be/oE8Fk2EsU-U?t=7) 既然做工程的，我們的目的就是要去解決問題，問問題時要避免像「數字」這樣模糊的詞彙，你可以說 0 ~ 9 是「數字」，也可以說一個浮點數是「數字」，這樣無助於溝通。
* Interviewee 在 coding 時可以多參與討論。
* [4:28](https://youtu.be/oE8Fk2EsU-U?t=268) 避免直接說我給你提示。如果最後 interviewee 進來你的單位，你變成他的主管，當他遇到問題時，你不可能說我給你一個提示，應該善用討論，順便檢測你們之間溝通有沒有什麼障礙。
### Interviewee
#### 優點
* 應答得很順暢。
#### 可改進的地方
* 邊打字邊講話可以再多加練習。
* [11:13](https://youtu.be/oE8Fk2EsU-U?t=673) `char` 唸 "character" 比較好。此外，只有回答到 interviewer 的第二個問題。
* [11:33](https://youtu.be/oE8Fk2EsU-U?t=693) Interviewer follow up 詢問有沒有更好的時間複雜度作法，想不到時不要只是說目前沒想到，應該跟 interviewer 討論是不是有比 O(n) 還要好的方法，很顯然這題光是尋訪這個 string 的所有字元就要 O(n) 的時間複雜度，應該要跟 interviewer 討論。
Sign in with Wallet
Connect another wallet