# Software Engineer 面試 & 刷題心得
[TOC]
## 前言
最近在找工作，陸陸續續有投了幾間公司的履歷，會把自己目前準備的東西等等的記錄下來，希望能幫到自己~~不要再犯一樣的錯~~，也希望能幫到其他可能有要投相關職位的人。
## 整體求職心得
我是本科畢業，必修也都修得不錯，所以大概能說自己有一定的 Coding 能力，對相關的 domain knowledge 也都有基本的了解
在大學和研究所期間，自己最常碰的領域是網頁前後端和遊戲 (課程專案)
求職的時候我大概分幾個階段投履歷：
1. **聽過的外商**
希望工作比較有保障一點
敝系出來大家對業界的想像都會是比較厲害的公司，
~~雖然並不覺得自己有這個能力但~~就會去投
而且剛畢業的新鮮人不懂的東西很多，第一份工作投比較大的公司~~大概會~~比較有保障 (去 Soft_Job 和 Tech_Job 版查黑特可以看到一些鬼故事)
2. **職缺為有興趣的領域**
興趣取向，希望能做本來就喜歡的領域 (不過真的就是想想就好)
3. **要求的技能包含我會的語言**
真的必須寫自己相對沒興趣的開發的時候，至少希望是相對擅長的語言 (這也是想想就好)
我原先認為工作至少要是自己擅長的語言、適合的領域，但其實公司不見得是這樣選人
「真的好的工程師，應該學什麼都會寫」by 友
事實就是自己就算會什麼，進去很多就是要從頭學起 (畢竟你自己寫不太可能會符合業界標準)
所以有些公司 (外商?) 寧願找到聰明的員工進去學，畢竟聰明人學東西也會很快
但也要說有些公司 (團隊) 資源可能就不放在這，他們會希望找到即戰力，對我來說這種公司 (團隊) 就是比較沒有緣分
因此後來面試我對自己的定位就是：
* 我想要做軟體開發
* 但做哪方面的開發我並不侷限
* 期待在工作時學到東西 (軟體架構、專業知識等等)，我就是想練功
整個面下來我覺得找工作真的就是運氣運氣的，最近疫情又變嚴重，我面的職缺很多都是只找一個人
但這種就很競爭，有時候你沒被選上也不是自己不夠好，而是你剛好跟一個比你好的一起面了同個職缺
好幾封感謝信上寫著的或是 HR 轉述的都是
對我的學經歷感到驚艷、印象深刻，也認為我有很不錯的 Coding 實作能力
但就是剛好不適合，或是剛好前面有更厲害的人
(應該不是每封感謝信都會稱讚 Coding 吧www)
雖然自己也失落許久，但希望有誰日後也有要找軟體工程師工作的能夠不~~像我一樣~~那麼懷疑自己
### 履歷
我有一份英文履歷 (拿來投外商或沒在 104 看到的公司)和一份 104 的履歷，大概會包含這些內容：
* 基本資訊 (電話、電子郵件等)
* 學歷 (包含大學和研究所)
* 實習和參與過的專案 (公司、參與的部分、使用了哪些技術 / 語言等等)
* 技能 (語言、框架、其他)
不過上面的履歷吃過非常多無聲卡，我後來思考可能的原因可能有幾點：
* **我的經歷不適合該職缺**
這沒什麼好講的，就是不適合 XD
* **他們現在剛好沒有缺**
我比較前期有幾個履歷都是直接投到公司的招募網站
這邊放的職缺有些可能真的就是~~放好玩的~~，常態性放在那邊但其實已經招到人了，這種就是運氣運氣
* **我沒有放照片**
雖然現在軟體業的標準履歷可能已經不包含照片 (因為這跟你會給公司帶來的價值幾乎沒有關係)，但有些人資看你沒有照片就是會覺得你不好把你刷掉，~~總之在台灣找工作就是需要照片~~
但如果是在求職平台上，我覺得放照片就有其必要性，因為可以找的人會很多，照片還是能為你增加一點印象分
這就是公司在招募的抉擇，那你可能就是看你有多想去這間公司，是不是會為了這間公司妥協
* **我沒有寫自傳**
有些公司就是會希望 Candidate 寫自傳讓他們判斷人格特質 (不過我很想質疑這個能判得多精準)，有聽說過沒有寫自傳所以被刷掉的例子
有些公司會有一個自我推薦信的欄位，至少就是事先讓你知道要投就是得寫
那寫的時候可能就是先看公司的性質、要求的技能來看自己的那些經歷會加分 (大概寫一下)；如果有什麼特別讓你想去那間公司的契機，那就也寫一下
我覺得這就一樣是看雙方的選擇來決定彼此的緣分
履歷這關就是最基本的讓人資決定要不要讓你進面試，所以就是要推銷自己讓自己能夠進面試
「履歷上寫的東西就只是讓你拿到面試的門票」by 友
我其實本來對於寫自我推薦信或在履歷上寫上某些經歷和技能都讓我覺得自己在欺騙公司
因為對我來說這些東西都只是「我有用過 (但寫了簡單的東西)」「我上課學過」的程度，說不上是堪用
但大概大部分公司也不期待新鮮人真的會什麼，誰沒當過學生
~~有多少人學生時期就可以把自己弄得跟大神一樣，真的那麼神怎麼還會去應徵這個公司？~~
他們就只是期待你有用過，知道這是什麼，之後比較不會雞同鴨講
(啊講是這樣講啦，有些真的要即戰力的真的就要會寫啦)
~~不過我覺得要求穩還是請認識的人幫忙內推比較實際，論念好學校的用途~~
### 面試
從之前找實習到現在找工作也陸續面了十多個公司，每個公司在面試著重的點都不太一樣
目前碰到的可能會包含這幾種：
* **聊天**
面試官會跟你聊你的經歷 (實習做的專案、閒暇的小專案之類的)，然後從中再找到他們有興趣的地方繼續深入問，他們同時也比較知道 Candidate 到底有什麼經驗，能不能勝任工作
有些公司真的會問到很細，自己做過的專案還是要熟悉一點比較好ouo
有些會在這邊問一些 behavior 的問題，像是以前合作的經驗、碰過的問題等等的
* **自我介紹**
其實和聊天差不多，聊天通常也是會先聽自介才進行
這部分我覺得自己可能不是那麼擅長，不過我大致上還是有個講的流程：
1. 首先簡單帶過自己的學歷，視情況提及求學階段所修的課程對找工作有什麼幫助
Ex. 程式和演算法的必修課奠定我 Coding 能力的基礎
2. 自己實習時的經驗，大概提一下自己在實習中扮演什麼角色
Ex. 在公司參與了某某 Project，(Project 的目標，)自己負責了某某部分
3. 課餘時間其他有可能有幫助的事情
Ex. 課餘時間有在寫 Side Project，Deploy 後端前端一條龍
* **專業領域的問題**
通常會問和職缺比較相關的領域 (Ex. 網路、系統)
也會用問題來測試你對語言 (Ex. C++、Python) 的掌握度
真的要準備的話應該就是把作業系統、計算機網路之類的複習一下，剩下的就真的是平常因緣際會多獲得知識
Ex. C 裡面的 NULL 只是一行 #define NULL 0
* **白板題**
有些公司的白板題會和上述的一起進行，不過像 Google 前幾關就幾乎是純白板題
我自己面的感覺大概如下：
* **有什麼想法就要講出來**
面試考白板題不是要你腦筋急轉彎，(一般來說) 他們也不期待 Candidate 會直接想到正解 (如果直接想到了當然就是非常 solid 的 hire)，重要的還是你中間的思考過程 (怎麼解一個問題之類的)
所以有什麼看法 (即使可能是錯的或非常不完整) 都可以直接講出來，~~面試官會幫你的~~
* **不要過度相信面試官的提示**
應該大部分時候只要方向錯了，面試官都會馬上把方向拉回來
但自己碰過也有聽過有面試官沒有拉回來，就直接往奇怪的方向前進了
所以如果很確定前往的方向不太對，應該要~~設法不要繼續做下去~~
* **平常可以多刷題目**
我覺得 [leetcode](https://leetcode.com/) 和 [kick start](https://codingcompetitions.withgoogle.com/kickstart/archive) 都不錯，kick start 可以刷前兩題就好 (第三和第四題通常都比較困難)
比較新的 kick start 也可以參考[我的小廢扣](https://github.com/zkelly3/Kick-Start-Code)
## 目前面試過的經驗分享
### Taiwan AI Labs Internship (2018 忘了幾月)
因為已經快三年前了所以應該不太準，履歷階段是讓同學幫我內推的
面試主要考了一題演算法、聊履歷上的經歷和聊天
**結果:Offer Get**
### Skymizer Internship (2019 暑假前)
這個實習性質也比較特殊所以可能幫助也不大
履歷其實投過去蠻久都沒有消息所以本來大概是沒有上
這個實習算是突然有個 backend 的 project 所以才會進面試
面試的時候基本上都在問履歷上的經歷和聊天 (可能他們覺得會寫就好 (no
**結果:Offer Get**
### Plurk Full-time (2020 年底)
算是實質意義上我第一次面試所以 (ry
履歷寄過去後幾天收到了筆試題要求設計某系統，說期限一周
大致上不難~~感覺有點像是大家面試前都會練的東西~~
---
交過去後會約面試，然後有先用電話交流一下跟問希望薪資 (在聊的時候我猜我薪資對他們來說可能有點偏高
---
面試在噗浪的辦公室，先考試後 (應該是技技負責) 再跟總監聊一下天，可以看出人真的蠻少的 QQ
考的是 python 相關的演算法和一些比較實務上可能會用到的寫法，可上網但 code 要能執行
**結果: 面試後吃感謝信**
### Google Full-time (2021 3~4月)
算是畢業後第一次面試，履歷階段是請人內推的
之前也有投過 Intern 但沒有進面試，只能說 Google ~~有內推進度真的是推進的一個飛快，不到一星期就收到信~~
第一階段是 Phone Interview，似乎是會有一場技術的 Interview
基本上就是考演算法 (其實信上都會說有哪些東西是有可能會考到的都可以自行準備一下)
然後會在 Google 自己的協作文件上寫 Code (好像聽說也有可能直接用 google doc 考)
---
面完 Phone 之後過幾天收到 On Site 的信
這階段原本應該是要到 Google 那邊去直接寫白板題的，但由於疫情因素其實做起來和 Phone 差不多
這階段聽說是有五場，不過現在有可能是拆成上下，上兩場下三場
我在這階段是面了兩場，兩場都是考演算法，第二場是全英文然後前面有聊一小段履歷上的經歷
**結果: On Site 前兩關後吃感謝信**
### Fourdesire Full Time (2021 4~5月)
我是投他們的行動工程師 (在官網上直接投的)，需要寫自薦信~~差點沒逼死我~~
履歷寄過去後幾天收到面試邀請，是用 Skype 和 HR 做自我介紹和讓她問問題 (官網上的招募指南都有寫得很清楚可以準備什麼)
---
面試後約一周通知進到第三階段，考的是 Client 開發實作，共五題
可能受到疫情影響，筆試是在家進行 (原本要去他們公司)
他們會用 Skype 傳試題過來，花十分鐘大致解釋題目要求，實際作答時間為 120 分鐘
120 分鐘五題其實很趕，而且最後一題 (正常來說) 要花很多時間，最好自己斟酌一下
不過其他四題就不難，不用太緊張~~請多花時間在最後一題~~
前幾天去的時候有問 HR，她說之前沒疫情的時候會到公司關網路考，但考題也會有所調整
而且就如前面所說的，他們主要比較看你寫 Code 的思路和解題的方式，所以不用太緊張自己有什麼語法想不起來 (
由於其他公司也差不多快進結果了 (希望啦) 所以我有跟他們表達希望能加快面試進程
在筆試後隔天就收到信，準備第四階段
-----
第四階段是到他們公司 (在北車 Y17，要走一下) 面談，我是跟 HR、CTO、CEO (Taco) 進行面試
他們會先讓你做個詳細的自我介紹，然後問一些事先準備好的問題
(有些問題其實第二階段就有問過，如果有需要去面的人可以準備一下...)，全部結束大約一小時
**結果：第四階段後吃感謝信**
### 趨勢科技 Full Time (2021 4~5月)
因為前面投了幾間~~被無聲卡讓我很失落~~開始在 104 上找自己覺得還不錯的公司投起來
履歷投過去後收到筆試邀請信，是用 Codility 平台進行，會先問你擅長的語言和有空的時間，那之後才會把筆試連結寄過來 (應該是在它連結過期前寫掉就好)
我考的是 C++，覺得難度以兩個小時三題來說並沒有太難 (二面得知為滿分)，而且是讓你自由自在寫~~所以不排除找槍手的可能性~~：
* 給一個數字的字串，問如果最多能改其中一位為任何數字，能夠改出幾種為 3 的倍數的字串
* 給一個數字的陣列，問陣列中連續最大偶數和為多少
* 給你手上有的骰子數、骰子點數平均和你記得的點數們，問剩下的骰子有可能是多少 (給出一組解或回傳不可能即可)
不過和 Leetcode 比較不一樣的是自己生的測資它只會幫你跑 (不會跟你說對不對)，但一樣需要自己多檢查 Corner Case
-----
考完過幾天後收到面試邀請，這邊有一點~~讓我蠻困惑的~~
在收到筆試邀請時他們會在郵件上寫說我是應徵一般的 RD 和 QA，不過收到面試邀請的時候完全不是這兩個職位而是三個 Sr. 的職位
HR說筆試邀請那邊是一般對外的 general 職缺，面試邀請這邊則是主管看完我的測驗成績有興趣才會邀約
然後就是跟我問有空的時間約面試，~~然後約面試的當下不知道為什麼又從三個職位長到五個職位~~
公司離我家挺近的所以我是直接走過去，面試是在一個小房間進行，我大概從下午三點一路面到快六點
五個職位大概分成三組跟我面試。第一個是在新竹的主管 (遠端)，其他兩組都是台北的主管
整個面試大致上都是聊天，有詢問我的過去經驗和寫過的 Project，碰到什麼問題和怎麼解決
還有大量的「你知道OO是什麼嗎」、「有沒有用過/聽過OO」、「OO和XX的差別是什麼」類似這樣的問題
~~這方面我經驗非常不足有很多都只能老實的說不知道~~
其中一場有考白板題，不過非常簡單，也不需要實際寫 (直接講想法就好了)
全部面完後有另一個 HR 進來請我對剛剛面完的 Team 的喜好度做一個排序
我最有好感的 Team 好像是說想要即戰力所以沒有辦法，不過另一個 Team 好像可以，所以就有加排這個 Team 的 HR 面試
我猜可能就是看雙方的接受度來排面試吧 (
-----
二面其實基本上就是 HR 面試，但因為上次面的 Team 的主管希望能讓組員跟我多解釋工作內容所以提前了一小時 (早上十點...) 到公司
面試過程大概都在聊天，也有問我一些比較系統相關的東西和有沒有碰過 Windows 的 OS 等等的
HR 面試就也是先自介，然後問我還有投那些公司、期望薪資等等的，這個階段 HR 也有跟我加 line 好友，這樣溝通也比較順暢 (個人感受)
---
幾天後接到 HR 電話確定薪資和可決定的日期，後續也有用 line 繼續詢問相關的福利等等問題
**結果：Offer Get**
### Appier Full Time (2021 4~5月)
我投履歷到 Appier 的時間剛好抓的有點微妙，是請我同學幫我內推的，但內推的時間沒有抓好~~剛好在他們校園徵才開始前幾天~~，所以那時候是直接在官網上找自己可能有機會的就投了沒有特別看
過了一兩周後收到 HR 的信約了打電話的時間，然後獲知我投的 Team 他們希望是比較有經驗的人 (所以可能不行)，但還有另一個 Machine Learning 的 Team 要找 Software Engineer，也跟我大概講了一下這個時期進去可能會負責什麼
確認了細節之後就約面試
面試是在他們辦公室的會議室，只有一個面試官
一開始先跟我討論了履歷上有寫到的經歷 (主要都是在討論實作的細節，是否有和其他人合作，有沒有發 PR 等等的)
然後考了兩題白板題，難度不算太高 (我一題用 C++ 寫，一題用 Python 寫)
那之後又稍微聊了一下職涯規劃和興趣等等的就結束
一星期後他們表達有找到比我更適合這個職位的人了 QQ
**結果：一面後吃感謝信**
### 新思科技 Full Time (2021 4月)
投職缺過去幾個小時後，新竹廠的 HR 就有打電話過來跟我確認我的狀況以及說明職缺
他們的職缺大部分是在新竹廠，不過台北廠也有一些職缺
他們公司的作法是我先提供履歷給 HR，他幫我 forward 給公司的其他人，每個 Team 的主管再自己跟我排面試和決定是否進公司
但有件有趣的事情是在我跟新竹的 HR 通完電話沒多久，台北的 HR 也打來 (看來是重複致電的部分)
~~我：我剛跟你們新竹的 HR 講完~~
履歷投遞過去後幾天我收到台北某個 Team 的主管 (?) 的遠端面試邀請，是用 Zoom
這場面試主要就也是聊天。她先了解我碩班研究的內容，然後稍微介紹台北廠目前在做什麼樣的事情，中間也有問幾個資料結構的問題~~確認我是個正常的資工系學生~~
然後說正式的面試會是由台北端這邊安排 (因為她好像是上海遠端來工作的)
過了幾天我有收到台北端的邀請，但由於太爆炸加上討論後發現相對沒那麼有興趣，後來寄信婉拒
**結果：婉拒**
### 訊連科技 Full Time (2021 4~5月)
這間也是從 104 投履歷過去，履歷投過去後過幾個小時接到 HR 的電話安排面試 (含筆試)
面試前要先填工作申請表 (~~我覺得這是整個面試程序中最降 san 的一步~~)
然後會要求你帶成績單和得意程式碼 300 行 up (這個程式碼其實就是給主管參考的，我是印了一題 kick start 和之前修資訊編碼的期中作業)
去之後會先考筆試 (C/C++、性向測驗、英文，如果不是面工程師或設計師還會再多考中翻英)
程式筆試的部分好像也可以選 Java，不過我是考 C/C++
講是這樣講，考題本身寫法還是比較偏 C，考的內容也和網路上講的沒差多少 (幾題演算法、一題實作現有 function、兩題判斷程式輸出、一題找錯)
~~對 C++ 大概只需要複(預)習 class 的 new 和繼承~~
性向測驗包含語文、數學、邏輯三個部分，寫題速度要很快
~~我自認寫題目算超快了但邏輯還是有兩題沒寫完~~
英文的部分包含聽力和閱讀測驗，其實好像就是有點模擬多益
但聽力的部分可以隨自己聽到爽~~所以其實沒有很難~~
---
考完筆試後和主管面談，大概就是聊我碩班的研究內容、對工作內容的期待等等的，也有介紹這個職位進去後是做哪個產品，大概會是做哪個部分之類的
面完後 HR 進來問我大概面試會面到什麼時候，到時候再聯絡
---
兩周後他們幫我排了和公司 RD 副總的面試，剛好碰到台北防疫升三級所以馬上改成線上
覺得比較~~奇怪~~的是這階段依然要準備得意程式碼給副總，我因為在面 Fourdesire 的時候剛好有用寫到比較物件導向的 code，就把其中一份換成這個
說是面試其實比較像面談，副總和我研究所的教授是師兄弟 (?) 的關係，所以我們都在亂聊
他就大概問我延畢的半年、整個碩二在做些什麼 (我就大概說了研究的心路歷程)，然後問一些我給的 Code 上面的 coding style 和很簡單的 C++ 相關的問題
然後他對我介紹公司營運狀況、研發部的組織架構、我如果進去會加入的 Team 的工作內容，還有一些工時等等的問題都有再討論過
---
隔天一面的主管打電話過來和我確認薪資和可決定的日期，我自己之後又有和 HR 用 e-mail 聯絡詢問福利的細節
**結果：口頭 Offer Get**
### Amazon Full Time (2021 4~5月)
我大概確定 Google 無望後就直接丟履歷，不過上禮拜才收到筆試通知 (約間隔一個月)，~~奉勸大家想投的可能要早點投~~
筆試是在家用電腦遠端筆試，不過規定有點多，前一天最好上去系統測試攝影機鏡頭
他們用的系統~~很可疑~~功能基本上和其他系統一致，但嚴格要求不能快捷鍵也不能切畫面
這讓我考得蠻不舒適的，我平常就蠻習慣會複製貼上一些懶得寫的 function 名稱
然後我考試中途家裡網路一度斷線，所以我有戳開連線設定看網路情況，**然後就吃警告** (第二次再犯就會直接掰掰)
就真的考得不是很舒適
題目總共三題考 90 分鐘，我的感覺是其中兩題不難 (不過測資應該是蠻刁鑽的，我其中一題看測試的結果有一筆錯我猜是爆 int 來不及改...)
但有一題特別難~~並且讓我覺得沒什麼鑑別度~~
分享給大家→[這裡](https://en.wikipedia.org/wiki/Josephus_problem) (但知道是什麼問題跟會寫又是兩回事啦)
我是覺得沒什麼希望但姑且留著 :)
---
然後很黑人問號的是收到了面試邀請...
HR 說會有兩關。一關是 RD，會考白板題測驗我的解題能力；另一關是經理，也會考白板題，不過還會加問一些 soft (?) 的部分，我猜可能是比較偏 behavior 的關
然後一個禮拜後才收到 Schedule 通知...
目前是打算就繼續面 (當經驗也好，但他們真的好慢喔)
---
當天就是有面兩關，有考 coding 和 behavior。
coding 的部分意外的沒有很難，是~~Leetcode 上也會看到的東西~~，有什麼問題也都可以和面試官討論。解完題後會問說如果你要對這份 code 做測試，會給那些測資。
behavior 的部分就是會問假設性問題和一些曾有過的經驗，不過因為還沒有實質的工作經驗所以可能答得不太好 (
**結果：面試結束後收到感謝信**
### 群暉科技 Full Time (2021 4~5月)
群暉也是我蠻早就透過 104 投遞履歷的公司，但他們排要面試的人好像很多，所以直接排到兩周後
因為印象深刻所以講一下，群暉真的是我面那麼多間來建築給人觀感最好的 (可能只有 Appier 跟它差不多)，終於有 UI 正常的電梯
群暉在 PTT 版上被許多人喻為白板大魔王，但我大概是還沒到那個階段...
我投遞的是網路應用相關，當天面了兩關
兩關的流程都大同小異，都是先請你自介，接著討論你在自介中提到的專案 (建議真的要對自己的專案很熟，他們都會一直往內挖 XDDD)
像是我提到最近 Side Project 在做~~小破站~~，他們就會問
「為什麼選擇 Flask」「為什麼選擇 mysql 而不是 Nosql」「為什麼選擇 Vue」「如果我想巴拉巴拉巴拉 SQL 怎麼下」
之類的，會問到很深入ouo
兩關的白板題在邏輯上都不難，但可能會抓 memory leak XD
面試官：你現在的 Code 有一些小問題
我：...?
面試官：你看你這個巴拉巴拉巴拉
我：啊，就被我丟在那了 XDDD (然後多摳幾次就會 memory leak)
除了白板題和經歷之外還會考一些語言、系統、網路相關的問題，像我當天就有被考到一些 python 語法、C/C++ 語法之類的問題 (就有點硬啦，python 有些語法我真的是不熟完全無法)
面完兩關後 HR 進來說如果有後續一周內會通知 (會用 104 的信件通知)
**結果：一面後吃感謝信**
### 湛研科技 Full Time (2021 5月)
這間是在我還沒面訊連前~~因為一時心灰意冷手賤~~投的，是個新創公司
我們就直接約在網路上用 Google Meet 面試
他們大概是做影片相關的產品 (據說目前有個產品是幫影片剪精華)
面試開始後他先對我介紹公司在做什麼內容，然後就直接問我在求學階段和實習有碰過什麼困難 (~~自介的部分就這樣被跳過了~~)
接著問了一兩個設計 function 的問題後面試很迅速地就結束了
然後有特別跟我強調雖然我投的是後端但有可能會需要去支援前端和 App XD
---
一周後收到希望二面的邀請，不過當時已經幾乎確定有 Offer 了
~~考慮到去的機率真的是不高~~就婉拒了
**結果：婉拒**
## 可能可以準備 (熟悉) 的資料結構和演算法
### 資料結構
#### Array
一般在 C++ 用 vector 實作
優點應該是可以動態加大 vector 的大小，而且在實作上似乎會把資料放在 heap，所以可以開到很大
```C++=
vector<int> arr; // 空的
arr.push_back(val); // 把 val 加進 arr 尾端
vector<int> arr(N); // 在這裡 N 是你希望的 arr 的容量
vector<vector<int>> arr2(N, vector<int>(M));
// 初始化一個 NxM 的二維 vector
```
#### String
在 C++ 裡面是用 string 實作
和 vector 一樣都可以用 for 來跑過
可以在整個 string 後面加入新的字元，也可以把兩個 string 組合起來
```C++=
string str;
str.push_back('A'); // 在尾端加入新的字元 A
str += "B"; // 在尾端接上一個內容為 B 的 string
```
#### Queue
一般來說似乎更常用 deque (彈性更大)，在 C++ 是用 queue 實作
碰到 BFS 的題目很好用
```C++=
queue<int> q;
q.push(0);
q.push(1);
printf("%d\n", q.front()); // 0
q.pop();
printf("%d\n", q.front()); // 1
q.pop();
if (q.empty()) printf("yes\n"); // yes
```
#### Stack
不是特別需要的話可以用 vector 代替 (彈性更大)，在 C++ 是用 stack 實作 (不過底層仍是 vector)，面試碰到的話其實面試官可能也會直接提醒說不用特別用 stack 寫
可以用在非遞迴的 DFS，需要維護某個單調性等等的題目上
```C++=
stack<int> s;
s.push(0);
s.push(1);
printf("%d\n", s.top()); // 1
s.pop();
printf("%d\n", s.top()); // 0
s.pop();
if (s.empty()) printf("yes\n"); // yes
```
#### Heap
在 C++ 是用 priority_queue 實作
可以用在需要動態得知當前情況下的最大 / 最小物的題目上
```C++=
// 可以自行傳入比較基準但比其他時候 (sort之類的) 略麻煩
class Comp {
public:
const bool operator()(Some& a, Some& b) const {
// 定義如何比較 a 和 b
// 注意絕對不可以讓 a < b 和 b < a 有機會同時為 true
}
};
priority_queue<Some, vector<Some>, Comp> q;
Some a; // 某個 a
q.push(a);
q.top(); // 當前最大 / 最小值
q.pop(); // 丟掉當前最大 / 最小值
```
#### Tree
比較常見的有 Binary Tree 和 N-ary Tree，在 C++ 一般是~~自幹~~
和他相關的題目可能都能從子樹的結果獲得一些資訊
* Binary Tree:
```C++=
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
```
在 leetcode 蠻常看到，不過通常題目會幫忙實作好這個 struct
* N-ary Tree
```C++=
struct TreeNode {
int val;
vector<TreeNode*> children;
};
```
#### Graph
跟 Tree 有點像的東西，在 C++ 一般是~~自幹~~
根據題目不同有幾個不同的自幹法
```
(0)->(1)->(2)->(3)->(4)
```
* 開一個二維陣列記某兩個點之間有沒有邊
```C++=
vector<vector<bool>> mp(5, vector<bool>(5));
mp[0][1] = true;
mp[1][2] = true;
mp[2][3] = true;
mp[3][4] = true;
```
* 開一個二維陣列記每個點可以連去哪些點
```C++=
vector<vector<int>> mp(5, vector<int>());
mp[0].push_back(1);
mp[1].push_back(2);
mp[2].push_back(3);
mp[3].push_back(4);
```
* 實作出這張圖，在點上記可以連去哪些點
```C++=
struct Node {
int val; // 也許會有
vector<Node*> to;
};
vector<Node*> &nodes; // 假設已經做好了
nodes[0]->to.push_back(nodes[1]);
nodes[1]->to.push_back(nodes[2]);
nodes[2]->to.push_back(nodes[3]);
nodes[3]->to.push_back(nodes[4]);
```
#### Map
有點類似其他語言的 Dictionary，在 C++ 是用 unordered_map 或 map 實作
unordered_map 的實作是用 hashmap，複雜度是 O(1)，但常數項大；map 的實作是用 binary search tree，複雜度是 O(logn)
實際使用的時候可以取捨一下，map 有另個好處是可以 iterate 過所有值，而且因為 map 是 binary search tree，裡面的所有東西其實有順序，所以也可以用 lower_bound 或 upper_bound 來做二分搜
有時候如果可能的值很小可能也可以直接開 array 記就好
```C++=
unordered_map<int, int> mp;
mp[0] = 1;
map<int, int> mp2;
for (auto i=mp2.begin(); i!=mp2.end(); i++) {
// 做事
}
```
#### Set
在C++ 是用 set 或 unordered_set 實作，更底層的實作和上面的 map 有點類似
Set 可以用來查某一個值是否出現過，不過只能知道是否有出現而不能知道個數
想知道個數的話可以用 multiset
```C++=
set<int> s;
printf("%d\n", s.count(1)); // 0
s.insert(1);
printf("%d\n", s.count(1)); // 1
```
### 演算法
#### Sort
如果不是他要你寫都直接用 std:sort 比較保險，時間複雜度是 nlogn
#### Greedy
腦筋急轉彎式演算法，真的碰到~~多燒香~~
想猜這個題目是不是 Greedy 基本上就是想辦法證明不走這步去走別步結果是不是一定不會比較好
#### DP
如果我們要的答案很可能是由很多子問題湊出來的，那就有可能是 DP
通常先把數學式寫出來對寫 code 會很有幫助
#### 遞迴
DP 也算是一種遞迴 (只是會把結果存起來)，所以遞迴其實就是把問題變小，到最後變成一個可以直接解掉的小問題
關鍵字: divide and conquer
#### 二分搜
如果我們要找的東西是在某個具有單調性的序列 (Ex. 嚴格遞增)，那就可以用二分搜
最近很常看到的另一個有趣的二分搜是對答案作二分搜，當題目出現什麼**最大的最小值**或**最小的最大值**，有可能就可以用二分搜
```C++=
// 寫起來都會大概長這樣
int head = 0;
int tail = N;
while (head + 1 < tail) {
int mid = (head + tail) / 2;
if (mid 符合我們要找的條件) head = mid;
else tail = mid;
}
// 最後有時候需要特判一下 head 或 tail
```
#### DFS (Depth First Search)
Iterate 地圖或樹的好幫手，比較直觀的作法就是用遞迴做
如果因為某些原因不方便遞迴的話也可以用 stack 做
#### BFS (Breadth First Search)
可以用在類似在地圖上走到某個點的最短距離的題目上，或是單純要 Iterate 地圖
實作的時候可以用 queue，不過特別注意在把下個點丟進 queue 前要先去把點的狀態改掉 (不然可能那個點會被丟很多次)
```C++=
vector<bool> mp; //記錄這些點被走過了沒
queue<Point> q;
q.push(初始點);
mp[初始點的 index] = true;
while (!q.empty()) {
Point tmp = q.front(); // 這輪要處理的點
q.pop();
// 也許先做點事
for (可能會被丟進去的點們) {
if (點符合條件而且沒被走過) {
q.push(點);
mp[點的 index] = true;
}
}
}
```
#### 爬行法
如果這個題目可能是要找尋某個最大值，然後可以透過一直往後增加看的範圍和縮減最前面要看的範圍來獲得答案 (已經沒在範圍內的之後也不會在範圍內)，那有可能就可以用爬的
實作上基本上是準備兩個指針 head 跟 tail，然後一路把這兩個指針慢慢往後挪
#### 線段樹、BST (binary segment tree)
比較困難的資料結構 + 演算法，當你需要知道任何區間的某個性質 (Ex. 最大值、prefix sum、最大公因數等等的) 可能就可以用
BST 可能比較多用在 prefix sum
大致上會需要實作這幾個部分：
* 建樹 (把初始值設定進去)
* Set (修改某個值，然後把和他相關的節點的值也改掉)
* Get (拿到某個區間的那個性質)
#### Disjoint Set
在需要把一些資料分成很多組去比較的時候可以用
這個演算法會開一個 Array 來記每個點的 root 是誰
最開始大家的 root 都是自己，在做了一些運算之後可能會把不同組別合成同一個 (合起來就分不開了)，root 就會改變
大致上要實作兩個部分：
* findRoot(某個點) 回傳這個點的 root
* merge(組a, 組b) 通常會以那一組的 root 來代表這個組
```C++=
vector<int> ds(N);
for (int i=0; i<N; i++) ds[i] = i; // 一開始 root 都是自己
int findRoot(vector<int>& ds, int a) {
if (ds[a] != a) ds[a] = findRoot(ds, ds[a]);
return ds[a];
}
void merge(vector<int>& ds, int a, int b) {// 在這邊要傳入兩組的 root 不然可能會出錯
ds[a] = findRoot(ds, b);
return;
}
```
#### 最短路徑
比較常見大概就幾種演算法：
* Dijkstra
邊的權重 >= 0，求從起點到任何點的最短距離
* Bellman-Ford
有邊的權重 < 0，求從起點到任何點的最短距離
* Floyd
從任何點到任何點的最短距離，複雜度O(N^3)
Sign in with Wallet
Connect another wallet