---
title: 2022 年資訊科技產業專案設計課程 HW4
tags: 資訊科技產業專案設計
---
# 2022 年[「[資訊科技產業專案設計 HW4]」](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Finfo2022-homework4)
> 貢獻者: 齊爾 Chill
> [video](https://youtu.be/QaBVCUUw8C8)
🧔：interviewer 👶：interviewee
## Mock interview
### [2. Two Sum](https://leetcode.com/problems/two-sum/)
#### 測驗說明與問答
🧔：My first question is I will give you two parameter. The first parameter is an integer array which is called nums and the second parameter is called target. You need to return the index of two number such that they add up to given variable target. Here is the example.
```cpp!
Input nums = [2,7,11,15]
target = 9
Output = [0,1]
```
The target can be sum up as the first element and second element, so the index of these elements are 0 and 1.
👶：
Can I use C to solve this problem.
🧔：
Yes, you can change prototype by yourself.
👶：
Can I ask if there are duplicate number in array?
🧔：
Yes, you can assume that there are duplicate number. But the answer must be unique.
👶：
So, it's like the numbers in array are [3,3] and the target is 6, I will return [0,1].
👶：
I have another question. Is the array sorting?
🧔：
No.
👶：
I think my first approach would be like using brute force. I will use two loop and iterate check two number in array if the add up to target.
🧔：
Do you have the constant time solution? Or you can just implement your first solution.
👶：
**Code**
```cpp!
int* twoSum(int* nums, int numsSize, int target){
int ans[2];
for(int i=0;i<numsSize-1;i++){
for(int j=i+1;j<numsSize;j++){
if(nums[i]+nums[j]==target){
ans[0]=i;
ans[1]=j;
break;
}
}
}
return ans;
}
```
The time complexity is $O(n^2)$, and the space complexity is $O(1)$.
👶：
I think my another approach can use hash table. I will store the index of every element in array to hash table. The input is like：
```cpp!
Input nums =[2,7,11,15]
target = 9
Output = [0,1]
```
First step is to store the index of every element in array to hash table. Like：
```cpp!
ht[2] = 0
ht[7] = 1
ht[11] = 2
ht[15] = 3
```
Second step is iterate using target minus every element in array. If the leaving number can be found in hash table, then return the index of that element and the value of the leaving number in hash table. Like：first round using target(9) - first element(2) = 7, ht[7] is exist, so [2,7] is the answer, then return their indices.
The initialization of value in hash table is set to -1.
🧔：
How do you know the keys of element in hash table because you set all the value to -1.
👶：
I will fisrt set the hash table value, then store the element in array to hash table.
🧔：
Would you like to implement your approach?
👶：
OK, I can try.
**Code**
```cpp!
int* twoSum(int* nums, int numsSize, int target){
int max = nums[0], min = nums[0];
int ans[2];
for(int i=1; i<numsSize; i++){
max = (max > nums[i])? max: nums[i];
min = (min < nums[i])? min: nums[i];
}
int ht[max - min + 1] = {-1};
for(int i=1; i<numsSize; i++){
HT[nums[i] - min] = i;
}
for(int i=0; i<numsSize; i++){
int value = target - nums[i] - min;
if(HT[value] != -1){
ans[0] = i;
ans[1] = HT[value];
if(ans[0] == ans[1]){
continue;
}
break;
}
}
return ans;
}
```
👶：
The time complexity is $O(n)$, and I need to build the hash table, so the space complexity would be like $O(n)$ too.
🧔：
I think the space complexity suppose to be $O(max - min)$. It's not equal to $O(n)$
👶：
Ok, that's my fault.
🧔：
I think this question is OK now, so we can move on next question.
👶：
OK, thank you.
### [9. Palindrome Number](https://leetcode.com/problems/palindrome-number/)
#### 測驗說明與問答
🧔：
My second is I will give you a integer x and you need to tell whether it is palidrome, so do you know what is palidrome?
🧔：
Let me give you an example：
```cpp!
Input x = -121
Output = false
Input x = 121
Output = true
```
The input is -121, ans the output is false because it is not a palidrome. If you convert the input number to a string, you can find the relative negetive in the head. So it's not a palidrome. 121 is a palidrome number, then return true.
🧔：
You can tell me what you think about to this question?
👶：
How big is the input value?
🧔：
The range of x is -231~231.
👶：
I think the minus number is the one of the edge case. And I think another edge case would be like the number that the last digit is 0, but 0 is a palidrome number.
👶：
My first approach would be like First, I will use an array and store every digit of the input number. For example：
```cpp!
Input x = 121
array[0] = 1
array[1] = 2
array[2] = 1
```
👶：
Second, I will iterate check the if the first digit is equal to the last digit, and check second digit and last-1 digit, and so on. If check all the digits, then return true, else return false.
🧔：
OK, so would you like to implement it.
👶：
OK.
**Code**
```cpp!
bool isPalindrome(int x){
int arr[3], len=0;
if(x<0 || x%10==0 && x!=0)
return false;
while(x>0){
arr[len++]=x%10;
x/=10;
}
for(int i=0;i<len/2;i++){
if(arr[i]!=arr[len-i-1])
return false;
}
return true;
}
```
👶：
I think the time complexity is $O(logn)$ because the loop needs to do the length of the input number round. And I need extra space to store every digit of input number, so the space complexity is O(logn) too.
🧔：
OK, it seems good for me. So if you have other solution or it's the optimal solution?
👶：
I have another approach that it won't use extra space.
👶：
I will reverse the input number and check the reverse number and the input number, so I need a variable named rev. In the end, I need to check the reverse number and the input number. So I need another variable tmp to store input number.
👶：
Every round I will multiply rev by 10, and then add the last digit(tmp%10) to rev. So it can push the backword digit to forword. For example：
```cpp!
Input x = 121
round 1
tmp = 121
^ -> last digit
rev = 0 * 10 = 0
rev = 0 + 1 = 1
tmp = tmp / 10 = 12
round 2
tmp = 12
^ -> last digit
rev = 1 * 10 = 10
rev = 10 + 2 = 12
tmp = tmp / 10 = 1
round 3
tmp = 1
^ -> last digit
rev = 12 * 10 = 120
rev = 120 + 1 = 121
tmp = tmp / 10 = 0
end
```
👶：
It's my second approach.
🧔：
It seems you reduce the space complexity and remain the time complexity. It's good. That's my two question. Thank you.
👶：
OK, Thank you.
## 改進方案
1. 介紹方法時，英文口說還是有點小卡，要加強英文口說能力。
2. 第一個問題，最後在分析複雜度時，沒有考慮清楚實際的大小。
3. 第一個問題，宣告方法時，一開始忘記提出hash table初始值，導致後續在解說方法時，誤導了 interviewer，需再思考清楚，才進入演算法實作。
4. 第一個問題，在 trace code 時，一直上下滑動螢幕，可能會使 interviewer 無法聚焦。
5. 第二個問題，最後在 trace code 時，應該要將每個回合要做的是分開來講解，擠在一起會使整體看起來很混亂。
6. 第二個問題，變數初值未設定就開始講解演算法，應該宣告清楚。
## 檢討學期表現
一開始自己在做面試練習的時候，從未接觸過，因為邊做邊講解，很常腦袋一片空白，更不用說全英文溝通，所以在錄製第一個作業時，都是半背答案的方式在進行，看起來很明顯。但經過整學期不斷的練習，最後的 mock interview 跟第一次作業相比，表現得好很多，可以順暢的表達自己的想法，也能一邊實作一邊講解，雖然有時候還是卡卡的，但跟之前的自己相比已經好很多了。在練習題目時，會不自覺的思考 REACTO 的步驟，不像從前一看到題目就想也不想開始實作，會思考可能的限制、edge case、能用的方法與不同方法間的優劣，也會去學習其他人的程式碼來改進自己。也經由老師及學長、姊的分享來思考自己能做甚麼跟一些實事。順利得完成最後一個作業還蠻有成就感的，也看到自己的進步不是白費了。最後感謝助教抽空時間陪我進行 mock interview，其與自己能越來越進步，朝著自己的路前進，加油！！！
Sign in with Wallet
Connect another wallet