---
title: 2022 年資訊科技產業專案設計課程面試範例
tags: INFO2022
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022)」面試
> 貢獻者: 嘟嘟嘟-Doo Du Doo
> ==[video1](https://youtu.be/ioz0WFPuEcc)==
> ==[video2](https://youtu.be/lNBP6somoBs)==
🐱：interviewer 🐶：interviewee
## [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)
> [00:01](https://youtu.be/ioz0WFPuEcc?t=1)
### 模擬面試過程
🐱：題目是算出將一個數字歸零的步數，可用的運算只有，當當前數字為偶數時，可將它除二，若為奇數，則只能減一。Input和output皆為integer。具體步驟可以參考文件範例。
🐶：數字範圍有限制嗎？
🐱：零到正的10的6次方。
🐶：那我想先初始化最後output的步數為0，再開始計算。因為要歸零所以用一個不等於0的while loop。然後用if條件判斷奇偶，若為偶數除二，否則減一，然後加一步。最後return steps.
參考實作:
```cpp
class Solution {
public:
int numberOfSteps(int num) {
int steps = 0;
while (num != 0){
if (n % 2 == 0) num = num / 2;
else num -= 1;
steps += 1;
}
return steps;
}
};
```
🐱：很好。但可以以另一種方式想想看，除二與減一其實在位元運算都有非常明確的動作。可以試試從位元的角度解決。
🐶：好的。我認為input的位元表示中，1的個數代表著減法的次數。而除法的次數我認為可從最左的1距離最右的bit的bit數決定。我們要先知道int資料型態的最大移動bit數，是sizeof(int)乘8減一。用函式得到1的個數是減法的次數，前面的length代表最多執行這麼多次除法，由於input可能最左bit不等於1，因此以函式取得最左1的左邊的0的個數。這樣就算出與前面相同的答案。
```cpp
class Solution {
public:
int numberOfSteps(int num) {
int length = sizeof(int) * 8 - 1;
return __builtin_popcount(num) + (length - __bulitin_clz(num));
}
};
```
### 檢討面試
1. 第二段位元相關的部分，不太確定如何表達，表達時有點卡頓和重複說明的情況發生。
2. 因為此題較單純，加上已經事先理解過，所以容易跳掉REACTO的example的確認步驟。
## [70. Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)
> [05:44](https://youtu.be/ioz0WFPuEcc?t=344)
### 模擬面試過程
🐱：題目是climbing stairs，題目會給予一個n的int，範圍在1到45之間，最後要算出爬完n個階梯有幾種方式
🐶：所以會需要排列，對嗎？像是2-1與1-2是不同的方式。
🐱：是的。
🐶：所以input為3時，總共有1-1-1,1-2,2-1，這三種組合對嗎？
🐱：是的。
🐶：我認為可以從排列組合的方式切入，當我們有2的個數與1的個數時可算出有幾種排列，2的個數減一，1的個數就會加二，再算出這種組合的排列數。以變數two為n最多2的個數，one為此情況的1的個數。由於排列需要用到階乘，所以先定義一個階乘函數。以2的個數遞減做for loop，每一輪算2的個數加1的個數的階乘除以兩個各自的階乘。因為每一輪2的個數減一，1的個數要加二。
```cpp
class Solution {
public:
int factorial(int n){
if (n == 0) return 1;
int sum = 1;
for (int i = 1; i <=n ; i++) sum *= i;
return sum;
};
int climbStairs(int n) {
int two = n / 2, one = n % 2;
int sum = 0;
for (int i = two; i >= 0; i–){
sum += factorial(i + one) / (factorial(i) * factorial(one));
one += 2;
}
return sum;
}
};
```
🐱：很好，但這個方法在數字較大的階乘會產生過大的數值，事實上這題會希望你參考斐波那契數列想想看。
🐶：好的，那我想這個題目可以想成n階會等於n-1階再1階與n-2階再2階。先考慮1階與2階的情形，因為前面沒有參考數值，然後再從3階開始，把n1=1階的數n2=2階的數，再用for loop從3到n，每一輪產生的新數temp是n1+n2，然後讓n1=n2,n2=temp，最後for loop結束回傳n2。
```cpp
class Solution {
int climbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int n1 = 1, n2 = 2;
for (int i = 3; i <= n; i++){
int temp = n1+n2;
n1 = n2;
n2 = temp;
}
return n2;
}
};
```
### 檢討面試
1. 雖然題目有，但interviewer忘了說爬階梯是由1階與2階組成。
2. interviewee提example時，應該一邊用打字表示。
## [2. Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)
> [00:01](https://youtu.be/lNBP6somoBs?t=1)
### 模擬面試過程
🐱：You're gonna solve a problem about adding two numbers.The two numbers, as you see on the document, are represented by linked list and both are non-negative integers.The digits of number are stored in linked list in reverse order so the list in example is 2 to 4 to 3 means number 342, same as the 5 to 6 to 4 means 465.And the number of nodes in linked list is between 1 to 100, and value of each node is between 0 to 9.I want you to plus two number with linked list. And the result is also represented by linked list. So in this example, 342 plus 465 equals 807.So final output will be a linked list with 7 to 0 to 8. Do you have any other questions?
🐶：This is a addition problem but the type of both input and output are linked list?
🐱：Yes.
🐶：I wanna give an another example to confirm whether I understand this problem correctly.One input is 7-9 and 8 just a single node so this means 97 plus 8 equals 105. So 105 will be linked list with 5-0-1, is this correct?
🐱：Yes.
🐶：Ok, I think I will change linked list to integer and plus two integers as sum and then change integer sum to linked list. At first, I think we need one integer l1_sum to store the number of input and one integer l1_length to know the length from the first node to current node. While l1 is non-null, let the value of l1 node multiply 10 to the power of current length. Move l1 to l1->next and l1 length plus 1. Do the same thing to l2. The result sum is l1 sum plus l2 sum. And create a head of new linked list. And use another variable to move forward. I will remove one digit each round, when creation ends result sum will become 0. So I use while loop here. I use a integer reserve to store the digits above tens digits, so value of current node will be result sum substract reserve multiply 10. If both input are 0, then need to create a 0 node. Finally, return next of newhead.
```cpp
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int l1_sum = 0;
int l1_length = 0;
while (l1){
l1_sum += l1->val * pow(10,l1_length);
l1 = l1->next;
l1_length += 1;
}
int l2_sum = 0;
int l2_length = 0;
while (l2){
l2_sum += l2->val * pow(10,l2_length);
l2 = l2->next;
l2_length += 1;
}
int result_sum = l1_sum + l2_sum;
ListNode newHead(0);
ListNode* t = &newHead;
int reserve = 0;
if (result_sum == 0){
t->next = new ListNode(0);
}
while (result_sum != 0){
reserve = result_sum / 10;
t->next = new ListNode(result_sum - reserve * 10);
t = t->next;
result_sum = reserve;
}
return newHead.next;
}
};
(l1與l2的while loop，錄影時將+=打成=)
```
🐱：Ok, this approach can work when length of linked list isn't too big, but, in this problem, the input length is up to 100. So it will overflow for integer data type. Actually, I think you can solve this problem digit by digit, not make linked list to number.
🐶：Same as the previous solution. Create a newhead and pointer. When we do addition, it will generate carry, so use a integer to record it. The output linked list generation will end when l1 and l2 are null and carry is zero. So we use while loop here. Create int l1_val and l2_val. If l1 is non-null l1_val equals value of l1 node otherwise l1_val is zero. Same as l2. Calculate the sum of l1 l2 value and carry. Let sum divide 10. The quotient will be next carry, and remainder will be value of new node. Move t to t->next, l1 to l1->next and l2 to l2->next. After we end while loop return next of newhead.
```cpp
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode newHead, *t = &newHead;
int carry = 0;
while (l1 || l2 || carry){
int l1_val = 0, l2_val = 0;
if (l1){
l1_val = l1->val;
}
if (l2){
l2_val = l2->val;
}
int sum = l1_val + l2_val + carry;
carry = sum / 10;
t->next = new ListNode(sum % 10);
t = t->next;
l1 = l1->next;
l2 = l2->next;
}
return newHead.next;
}
};
```
### 檢討面試
1. 我有貼上ListNode架構的程式碼，但沒讓interviewer提及，應該口語也要說明才比較好。
2. 雖然前面中文也是會有卡頓的情形，但用英文需要同時想程式碼、如何表達及將表達轉換成英文，更容易出現頭腦空白的狀況，覺得因為英文能力不佳，導致英文佔據我一大部分的思考。
3. 發現自己經常主語會用we，感覺好像不太好。
---
Sign in with Wallet
Connect another wallet