---
title: 2022 年「資訊科技產業專案設計」第 1 次作業
tags: 資訊科技產業專案設計
---
# 2022 年「[資訊科技產業專案設計](https://hackmd.io/@sysprog/info2022/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FBJLSJ3ggi)」第 1 次作業
> 貢獻者：瓈文琳 Lorian
>[影片(漢)](https://youtu.be/avhZwrz0pP8) 、[video(EN)](https://youtu.be/_8tvuVsV-ys)
😎：interviewer 🤔：interviewee
## [REACTO](https://www.youtube.com/watch?v=DIR_rxusO8Q&t=5s)
* Repeat:
重複提問，確認自己理解原本的要求
* Examples:
針對題目條件，舉出符合的案例，不限於特例
可以舉例input跟output，確認有沒有理解正確
* Approach:
說明自己打算採用的方案
講述自己的邏輯，用哪種approach
* Code:
撰寫程式，展現自己寫的東西的confidence level
可以寫pseudo code，他們想看到的是你的邏輯、你的想法
* Test:
若不能實際測試，那說明驗證程式的方案
可以用別的顏色的筆將例子自己跑一遍看最後跑出來的結果對不對
* Optimization:
對於大量資料的表現如何 Big O等等
* keep talking 就算不會也不要卡在那裏
## [66. Plus One](https://leetcode.com/problems/plus-one/)(漢1)
😎：瓈文琳同學你好，歡迎來面試，面試總共有兩題，等等請你先開啟給你的google文件，有分題號，希望你在上面作答。
🤔：你好，好的，我打開了。
😎：好的，第一題，給你一個很大的整數，以array的形式表示，陣列由左至右為最高有效位到最低有效位，將這個數字加上１之後回傳陣列答案。
🤔：好，所以這題是給一個用陣列表示的整數，希望回傳一個加１後的整數。如果input是[1,2,3,4]的話，加一會是[1,2,3,5]沒錯嗎?
😎：沒錯。
🤔：那想問一下如果遇到進位的情況，像是[9,9,9,9]，回傳會是[1,0,0,0,0]嗎?
😎：對。
🤔：好，那我想我會需要先得到這個陣列的大小，並從最後一個數字開始加上１，如果等於10的話表示這裡要放0，並且設定carry bit 為1，接著往前跑for迴圈將整個陣列跑過一遍加上carry bit，若是跑完還有carry bit沒加完的話，最後要在整個陣列前面insert 1。
### for迴圈每位跑加法
```cpp
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size();
int carry = 0;
if(digits[n-1] + carry + 1 >= 10){
digits[n-1] = (digits[n-1] + carry + 1) % 10;
carry = 1;
}else{
digits[n-1] = digits[n-1] + carry + 1;
carry = 0;
}
for(int i = n-2;i >= 0;i--){
if(digits[i] + carry >= 10){
digits[i] = (digits[i] + carry) % 10;
carry = 1;
}else{
digits[i] = digits[i] + carry;
carry = 0;
}
}
if(carry == 1){
digits.insert(digits.begin(),1);
}
return digits;
}
};
```
😎：這個作法是沒有問題，那你知道這樣的時間複雜度嗎？
🤔：因為每個數字都跑一遍所以是O(n)。
😎：下界呢?
🤔：是Ω(n)。
😎：有沒有可以讓下界變小的方法?
🤔：我想可以設定一些即時停止的條件，像是如果個位數字沒有大於10就可以回傳了。
### 及時停止
```cpp
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int i = digits.size()-1;
digits[i] += 1;
while(i >= 0) {
if (digits[i] != 10) return digits;
digits[i] = 0;
if (i > 0) digits[i - 1] += 1;
else digits.insert(digits.begin(), 1);
i--;
}
return digits;
}
};
```
## [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)(漢2)
😎：好的那現在是第二題，給你一個字串，找到長度最大的子字串，而這個子字串不可以有重複的字元
🤔：好，所以我現在會有一個字串s，然後我要找到裡面最長的子字串，其中那些字串不可以有重複的字元，然後要回傳字串的長度
🤔：假設s是abcdas，最長的子字串就是bcdas，所以要回傳5。
🤔：那我覺得可以用iterator跑一遍字串，記錄下目前子字串的字母，所以跑到a的時候會發現有重複，紀錄現在的長度，記錄下現在最大的值，然後繼續往後面做
😎：你說的繼續往下做是指直接從遇到重複的後面開始做嗎？
🤔：噢不是，當遇到重複時，會先記錄下目前子字串的開頭跟結尾，所以當重複時，應該要從上一次子字串的開頭下一個開始檢查
### iterator 逐步比對
```cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
string curr = "";
int max = 0;
int n = 0;
string::iterator start = s.begin();
for (string::iterator it=s.begin(); it!=s.end(); ++it){
string::size_type idx = curr.find(*it);
if(idx != string::npos){
n = curr.size();
if(n > max){
max = n;
}
++start;
it = start;
curr = *it;
}else{
curr = curr + *it;
}
}
n = curr.size();
if(n > max){
max = n;
}
return max;
}
};
```
😎：但這樣似乎會重複檢查很多次，有更快的做法嗎？
🤔：我想可以記錄一下每個字元在字串中的所在位置和字串的左界右界，遇到重複時應該要從他的重複字元的下一個，或是目前最左界的位置開始
🤔：因為有可能遇到abcdbas的情況，檢查到第二次的a時就不可以再從第一個a的下一個開始檢查，這個時候左界已經因為前面重複b時跑到c的位子了
### Sliding Window Optimized
```cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = int(s.length());
int Max = 0;
unordered_map<char, int> mp;
for (int r = 0, l = 0; r < n; r++){
if(mp[s[r]] > 0) {
l = max(l,mp[s[r]]);
}
mp[s[r]] = r + 1;
Max = max(Max, r - l + 1);
}
return Max;
}
};
```
## 漢語影片檢討
* interviewee：
* 第一題說給一個「很大」的整數，卻沒有講清楚到底多大
* 題目的限制應該都要再講更清楚一點
* 互動有點偏少，應該再多問點問題才能了解面試者
* 比較被動，應更掌握面試主導權
* 用了「似乎」的說法，讓人感覺沒很專業
* interviewer：
* 提問者沒有講題目限制，應主動發問多了解題目
* 回答時會有點冗言贅字，或有時候講話有點繞(筆記上有用比較通順的寫法沒有完全照口語打)
* 測試時間有點冗長與卡頓，第一題最主要的digits應該一開始就列在旁邊並更新變動，比較清楚表示。不過有檢查出程式碼沒寫好的地方還不錯。
* 第二題可以直接說用sliding window就好，一下有講左界右界一下沒講會有點聽不懂
## [67. Add Binary](https://leetcode.com/problems/add-binary/)(英)
😎：Hello Lorian, welcome to the interview. Please open the google doc for the question.
🤔：Hello. Okay, I have opened it.
😎：Okay. The question for you is that you will be given two binary strings a and b, and you have to return a binary string of their sum.
😎：If a is 11 and b is 1, then return 100.
😎：a and b will always be 0 or 1. and the length of these strings will be shorter than 105.
🤔：Okay I got it. I think I have to add two strings that represent binary numbers together and return the sum of them.
🤔：So if I get 101 and 11, I have to return 1000.
😎：Right.
🤔：Okay. I think I should first get the length of the strings and add them from the end of the two strings with a carry bit.
🤔：If the sum of the three numbers is bigger than 1, then the next carry bit is 1.
🤔：I also have to divide 2 by sum, and add the remainder of sum to the beginning of the answer.
😎：So how do you add the string together like an integer?
🤔：I think the character minus 0 as a character, like this(c - ‘0’),will make the character to be an integer. Then I can use it to do the calculation.
```cpp
class Solution {
public:
string addBinary(string a, string b){
int i = a.length() - 1;
int j = b.length() - 1;
string ans;
int carry = 0;
while(i>=0 || j>=0 || carry){
int sum = carry;
if(i>=0) sum += (a[i--] - '0');
if(j>=0) sum += (b[j--] - '0');
if(sum>1) carry = 1;
else carry = 0;
ans = to_string(sum%2) + ans;
}
//if(carry) ans = to_string(carry) +ans;
return ans;
}
};
```
## 英語影片檢討
* interviewee：
* 英文發音有怪的地方，例如最後的That's it就沒講好
* 和面試者的互動可以再多一點
* 最後提點修改的地方有點太直接
* interviewer：
* 沒有提到複雜度、空間相關問題，可以自己提一下
* 有些英文發音或用法有點怪怪的可以再修正，例如OK I'm done就是一個很怪的用法，應該是要說I have done.
Sign in with Wallet
Connect another wallet