---
# System prepended metadata

title: 2022 年「資訊科技產業專案設計」第 1 次作業
tags: [資訊科技產業專案設計]

---

---
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.
    
