英國工作 / 打工 YMS ，你不能不知道的工作合約、薪資單權益

(薪資單怎麼看請直接滑到 第二大點)

除了在應徵前用 glassdoor、blind 和打工社團內的 黑名單店家 查過一輪後，之後還要仔細小心的看工作合約和薪資單，雖然英文一堆密密麻麻的，但事關個人權益，務必花時間靜下來心來好好研究。

像我比較過三份合約...果然黑心公司還是不分國家，不然好不容易過了五六關的面試，最後簽一個對自己不利的合約真的很虧。

還有就是如何看 payslip 薪資單，老實說我真的查資料查到懷疑人生，還有包含自己製作圖片，好像寫了快兩個星期才寫完。

一、工作合約怎麼看?

1.1 薪水

英國在談薪水時基本上是以年薪來談，要確保合約上的數字和你當初和公司談的是一樣的；如果當時有提到任何分紅、獎金、簽約獎金、股票等項目，都應該要在合約上明列清楚。

而且合約裡應該要註明每個月的發薪日是哪一天，用什麼方式給予。

面試國外工程師超詳細超過 100 道題目蒐集、分類歸納與準備

要面試工程師的流程真的超級複雜，所以我就詳細蒐集了 

• Technical, behavior questions 蒐集與分類
• Coding, online assessment, assignment, system design interview 的準備

最後也有題庫供大家參考。

一、面試題目蒐集、分類歸納與準備

1.1 面試流程

在蒐集面試題前要先知道歐美軟體工程師的面試流程 : 

• Initial phone call：recruiter 或 head hunter 會和求職者約時間 phone call，通常會問位置、簽證狀態、薪資期望、自我介紹。 有的公司在這步就會問技術相關問題或是需要解題。
• Technical interview : 沒有 coding，直接問技術相關問題
• Coding interview : 面試官出題，你講解思路和解題
• Online assessment / Online test : 給你一個線上連結，限制時間內要寫完
• Assignment : 線上測試或是帶回家的作業，通常也有限制時間
• System design : 通常 senior engineer 才會遇到，考對於系統的規劃和設計
• Behavior questions : 問各種情況下面試者會怎麼處理，主要想知道面試者的處事態度和個性

那工程師面試時可能會遇到這些關卡交錯，但不一定每關都會遇到；有公司沒有 technical interview，或是有兩次 coding interview。

1.2 蒐集面試題

首先先蒐集變化度夠豐富的題目，包括 technical questions (依照你要應徵的職缺而定) 和 behavior questions。

不比中文面試，因為英文面試是使用自己不熟的語言；

我自己的個性是 : 如果能事先做好足夠的準備，面試時就比較不容易緊張，

就算遇到沒準備的問題，也會比較有自信也是能答得出來。

我用特定 skills + interview questions, behavior questions 等關鍵字 google 搜尋後大約翻 15 ~ 20 幾頁，還有上 youtube 看影片搜集問題，還能順便練聽力。

需不需要做到這樣，就看個人的個性和時間安排，但至少遇到 common questions 要可以回答得很熟練。

相關面試題目我整理成了題庫，可以下滑到 第三大點面試題庫資源參考。

如何讓 FAANG 的人資一眼看上你 - Github、Blog、互動式履歷網站篇

除了一般履歷外，工程師求職大多會要求附上 github 或是作品集連結。

我自己是另外還寫了網站式履歷，在面試過程中還有一邊寫 blog，

意外的很多面試官看，還特別喜歡互動式網站式履歷 (下面第 2.3 點會提到)，

也很欣賞我在 blog 上堅持分享技術和經驗的態度與精神。

一、Github

1.1 頁面敘述 & Demo

關於這塊平常就需要累積了，不管是 side project，參與 open surces 開發都行。

如果對方有興趣可能會 clone 專案下來看，但如果沒空可能就是頁面掃掃，

所以定期維護自己的頁面很重要，不管怎樣我都會讓對方看到首頁的時候至少可以看到關於每個專案的簡短敘述。

所以專案的 readme.md 我會寫上這個專案的目標、敘述、不會掛掉的展示作品的網址、使用的技術、相關功能的 demo 和說明、參考資料、版本更新紀錄、使用工具。

如果他不想看程式，可以靠這方式大致知道我專案的畫面、功能與技術，更進一步的話可能還會點進網站玩玩。

如何讓 FAANG 的人資一眼看上你 - LinkedIn 篇

要找國外工作勢必要用到 LinkedIn，我大概八成的面試邀約都是從這上面來的。

另外還有寫給國外專用的履歷，請見 如何讓 FAANG 的人資一眼看上你 - 履歷篇。

至於工程師必備的 github、作品集，甚至我還自己寫了 互動式履歷網站 和 blog 請見 如何讓 FAANG 的人資一眼看上你 - Github、Blog、互動式履歷網站篇

在介紹怎麼寫 LinkedIn 前，要先要知道 LinkedIn 有提供工具給 recruiter 使用 - recruiter 和 recruiter lite，這兩種都是人資方用來篩選求職者用的工具，那我們先來看一下 官方說明篩選條件 有哪些?

首先左側主要篩選選項有 : 

• Spotlights - open to work, are more likely to respond, past applicants, etc.
• Job titles
• Locations
• Skills
• Companies
• Schools
• Year of graduation
• Industries
• Keywords
• Employment type
• Advanced search

Advanced search 又包括四大項，每一大項裡面又分為多個小項 :

• Candidate details
• Education & experience
• Company
• Recruiting & candidate activity

接下來我們就會用到這些項目了，請往下滑。

 

找國外工作，如何有效率的跟 Head Hunter && Recruiter 打交道 (大量模板)

一、投遞履歷

1.1 投遞履歷前的注意事項

1.1.1 面試冷凍期

再來要注意有些公司有所謂的冷凍期，冷凍期是避免面試者狂面試同家公司，所以如果面試失敗了，就會有半年到一年時間不等 (minimum time you have to wait before re-applying for the same position) 是不能應徵該公司的，如 Google、Meta、Amazon 都是有這規定的。

所以如果要投遞這些有冷凍期的公司，請先確保自己準備到一個程度比較恰當，不過如果連履歷都沒過，是沒有所謂的冷凍期的。

1.2 投遞履歷

1.2.1 求職平台投遞

這一篇 應徵國外工作的前置作業，這些你都做了嗎? 的第四大點蒐集並選定使用平台開放履歷與投遞職缺已經有列出各種求職平台優缺點，可以參考選用。

像是使用 linkedIn 應徵工作，有的公司提供一鍵應徵，頂多再填一些有多少年寫 xx 的經驗? 有多少年使用 yy 的經驗? 等等就可以送出申請。

但很多公司都要求到他們公司的網站上填，有的可以選使用 LinkedIn 應徵，授權後頂多再填填姓名手機號碼就可以送出。

有的是提供 Smartr、myworkdaysite、indeed 等第三方網站授權應徵，但一樣都要先註冊。

有的公司授權完後下面的表格學經歷還要自己再填一次...

有的是授權後幫忙轉如 LinkedIn 的資料到公司網站上，寫得好的轉成功只要調調排版，沒轉好的變成亂碼最後還是要自己填。

有的公司會外加問簽證類型、預期薪水、為什麼想應徵這間公司、你為什麼適合這間公司、別人會用什麼名詞形容你等。

因為問的問題太各式各樣了，建議可以可以開一個文件記錄這些答案，之後再遇到就複製貼上就好。

投遞職缺的歷程實在不是一般的辛苦，在台灣投職缺可能投十幾個就會有面試機會，國外職缺可能要投到上百封才會拿到幾次面試機會，畢竟是非母語者還需要公司贊助簽證，可能還要出資讓你到國外工作，這條路本來就沒那麼容易。

應徵國外工作的前置作業，這些你都做了嗎?

這篇文章關於介紹了關於應徵工作的前置作業 : 

• 工作生活資訊查詢 : 在決定要出國前，先查詢國外生活資訊包括工作規定、福利等，可以幫助自己可以更好的決定要前往哪間國家 (英國推薦粉絲專頁 Greatbuttonhk、英國 360)

• 設定工作條件 : 有個最低能接受的工作條件，在找工作時才會更有彈性，可以依照面試狀況去做相對應的調整
• 職缺平台使用心得 : 十個以上找英國和美國職缺的職缺平台詳細心得，讓你可以選擇適合你的平台使用
• 撰寫 Cover Letter : 針對自己非常想進入的工作，客製化一份 cover letter，讓公司對你加深印象

一、查詢資料

1.1 查詢該國的相關工作規定和福利，以及自己工作的薪資水平

查詢該國的相關工作規定和福利，以及自己工作的薪資水平，在談薪資的時候才不會吃虧，

以下資料以英國為例，是我截止至 2023/01/28 查到的資料，日後或許會有所更新，就請自行查詢啦!

• 基本工資大約是 £14,976 / 年

• 不論行業平均薪資是 £27,756 / 年

• Software engineer 在 London 平均薪資根據 Glassdoor 2023/01/28 最新數據為 £66,984 / 年，indeed 2023/01/28 最新數據為 £50,207 / 年，reed 是 £57,168 / 年

• 一週工時不得超過 40 小時

• 年假不得少於 20 天

• 每年有固定 8 天的國定假日 bank holiday

• 請病假只要連續計算不超過 7 天(含周末) 就不需要醫生開證明，公司也會支付 sick leave pay，一般大公司或公家機關是在一定天數內支付全薪，有些則是支付部分薪水

• 國家保險 NI，每個月一樣由雇主在發薪時直接代扣：12%

• Income Tax，領到薪水前雇主就會先幫你把所得稅代繳給國家，視薪資而定會有不同稅率

• 要申請工作簽，公司需在 tier 2的 sponsor list 上，申請的文件主要是英文能力證明、財力證明，拿到 tier 2 工作 5 年，可直接申請英國綠卡 PR 永居

• 薪資級距相對應之稅率

IELTS 雅斯超超超超超短期準備 10 天考到 6.0

本來網路其實就已經有很多豐富的文章分享，如果可以有充足準備時間當然是最好，會有這篇文章是當初時間很緊湊的只有 10 天要考過 IELTS for UKVI，雖然聽說讀寫各 4 就好，但還是會擔心。

當然 6 不是個高分，但如果真的有人突然需要超超短期就考 IELTS 可以參考看看，希望讓時間不夠的人能夠快速熟悉題型和考試；最後其實聽和說有 6.5，但被寫作拉低了，平常太依靠 autocomplete。

這篇文章主要會是介紹

• IELTS 考試

• 一般組考題介紹和實際上機範例連結

• 短期考試各題型技巧

• 時間太少，網路資源太多的篩選

一、IELTS 雅斯簡單介紹

測驗的四個部分：聽力、閱讀、寫作、口說，每份試卷獨立計算成績，以 0.5 分為一個級距，滿分皆為 9 分，最後總分將會是聽、說、讀、寫四項成績的平均數。

聽力 → 閱讀 → 寫作三項考試之間是沒有休息時間的，加上提早進場的準備時間的話總共至少會有 3 個小時。

IELTS  for UKVI 費用為 £195，考核結果將會於試後 13 日 (紙筆模式) 或 5 - 7日(電腦模式) 公佈。

二、聽力 (30 分鐘)

聽力部份有 40 題，共有 4 段錄音(各 10 題)，每段錄音只播放一次。

這些獨白或對話都是由英文母語人士錄製，考生需根據內容回答一系列的問題。這些問題可以測驗考生是否瞭解錄音內容的重點和詳細資料、講者的看法和立場、談話目的和講者思路。考試錄音題目有不同的口音，包含英國、澳洲、紐西蘭、美國和加拿大等。

• 第一題組 : 以日常生活為主題的兩人對話，例如與旅行社的對話

• 第二題組 : 以日常生活為主題的獨白，例如有關當地設施的演講

• 第三題組 : 以教育或培訓為主題、最多四人的對話，例如大學導師與學生討論作業

• 第四題組 : 學術主題的獨白，例如大學的課堂講課

聽力部分整體技巧

• 有些題目填空有字數限制，如「NO MORE THAN TWO WORDS AND/OR A NUMBER」，字數如果寫超過就是錯，但 don’t 或 police-man 皆算一個單字

• 專有名詞第一個字記得大寫，如人名、路名及建築物名稱等

• 注意單複數，不然聽對拼對單複數卻錯了很可惜

• 注意填空格前有沒有 a, an，可以幫助你聽到正確的詞

• 通常空格前後的字比較有可能是關鍵字

• 注意答案關鍵字來聽題目，但要小心替換陷阱

PTE 送給我的台幣三萬五的經驗

相比雅斯 (IELTS) 和托福 (TOEFL)，

PTE/PTEA (Pearson Test of English Academic) 應該算是不常聽到的考試，

但其實也可以用做全球 32 個國家 (如英國、美國、澳洲、加拿大等) 國家的移民或工簽的考試檢定；最大的特色就是聽說讀寫皆採用機器評分、聽說讀寫項目交叉評分、且分數出來相當快。

很多文章說如果 IELTS 分數卡住了，可以改考 PTE 拿高分，因為 PTE 靠的是考試技巧，如果真的短期急需高分的人也許可以試試。

但我以一個當時沒別的選擇，兩次血淋淋的 PTE 考試經驗 (還前一天搭車先去考試的城鎮住，隔天直接參加考試) 分享給大家；如果能考 IELTS 還是考 IELTS 吧，不用準備那麼多題型、環境設備優良、考試同步開始、而且口說還是真人評分。

一、複雜的題型

首先題型很複雜需要好好查資料，因為題目太長大家還會用簡寫，剛開始真的超不習慣，考個試還要記這些沒什麼意義的事情。

準備時當然也要練習各種項目，像是口說就要練五種不同的考試類型，寫作要練兩種、閱讀五種、聽力八種，有些種類有重複，但其實還是看得出來很多。

考試的時候還需要快速辨識目前在考哪種題型，不然不小心就會漏掉了，

但這件事相比其他問題還算是小事情。

這邊講一些題型評分 "很有趣" 的地方。

轉職工程師 :: 從打包行李準備回台灣，到拿到英國工簽軟體工程師之路 (3)

達成用美金打組長的成就

「待業就好像你人生上所有的齒輪都被卡死了，你不能規劃未來，你不被允許開心、不配覺得幸福，所有的路都被這個障礙給擋住了。」

本來的公司是有贊助簽證的，但我們有些狀況，

所以最後是先辭職後再找有贊助簽證的公司。

可是當我準備一段時間開始投履歷時，

剛好遇到很大型的人事凍結，各公司不是凍結就是在裁員，

也看到很多人分享心得拿到好幾家 offer 最後卻都說 headcount freeze。

請人內推和投了 200, 300 封履歷，好像只有收到 3 家左右的回覆，

和之前封城時比算是少相當多，

還有好不容易收到面試邀約，得到的回覆卻是 unfortunately, we don't support visa

嘗試轉職工程師時我待業了約一年，
曾經想放棄當工程師時待業了約半年，

拿到打工簽找英國工作時待業了約半年，

但這時候的待業是壓力最大最大的，因為不但負債、簽證快到期還可能要打包回台灣。

轉職工程師 :: 從放棄當工程師，到在英國就職的軟體工程師之路 (2)

達成整主管的成就

找工作 - 放棄當工程師去應徵文書

在新創公司那時候除了平日常常加班到凌晨 12 點、1 點外，星期六、日也可能被叫去加班，有次還掛完急診又回來繼續加班；

沒有學習到新事物和解決問題的能力，一直重複搬磚的行為，天天被業務壓得喘不過氣來，對自己未來一點幫助都沒有；

另一個 team 更可憐，尾牙喝酒後去卡拉 OK 唱歌，唱到凌晨五點被公司 call 回去修 bug。

我不想要生活品質不好、但薪水高的生活，寧願薪水低一點卻可以準時上下班，那時候反省時覺得是不是自己不適合當工程師，辭職後曾經跑去應徵文書。

但當時面試文書時，面試官了解我心路歷程和我在公司做的事情後，苦口婆心勸我繼續當工程師，覺得放棄很可惜。

而我也感謝當時那個面試官拒絕我，因為讓我後來有機會進大公司，讓我理解到原來也是有可以兼顧生活品質和薪水的公司。

--

那時候也了解到當主管 / PM / 客戶提出的需求或時限，你評估過後覺得不可行、執行上有困難、花費很多時間但效益不高、時間太趕等等。

不需要勉強自己一定要達成對方的要求，然後加班或用自己時間去趕出來，有第一次就會有第二次，然後就會有第三第四五六次，有可能最後趕出來還是不是對方要的，卻花了很多自己的時間。

把為什麼不可行的原因、疑慮的點和對方討論、說明，

如果對方還是不接受，常常要你加班或用自主時間做出來，請快逃。

轉職工程師 :: 撞牆撞得亂七八糟，從睡廁所到睡公司的軟體工程師之路 (1)

達成在主管辦公室玻璃上畫畫的成就

大學 & 研究所 & 交換學生 - 所有階段都不務正業

大學的時候念工業工程，但非常的不務正業，

除了大一必修計算機概論寫 C++。

大二必修網路資訊應用 ASP.NET C# 架網站和資料庫管理系統，

選修系統分析與設計學畫 UML 和資訊安全與規範學密碼學。

大三選修3D 互動內容製作用 unity 寫 JavaScript。

大四畢業專題大家都在寫生產管理、供應鏈等，我跑去寫 AR；

那時候展出時外來的評審委員看了後大為驚艷，還遞名片給我說希望我過去他們那邊就讀，其實是挺開心的，但還沒有真的想到要往資訊這方面發展，所以就沒有考慮。

再來就是以前想念的科系想做的事情都被家裡限制，想念醫學想念美術想念哲學想念建築，

所以大學快畢業時期時還是不知道自己想做什麼或是我能做什麼，本來還考慮考高普考，後來卻誤打誤撞申請了研究所。

--
碩一時進了 AR/VR | AutoCAD 實驗室，選修 3D 視覺模擬和虛擬實境，用 unity、cinema 4D 結合 kinect 做手機遊戲寫 JavaScript。

接國科會計劃時和機械、化學系合作，用 dreamweaver 架宣傳網站，

那是第一次一個人架網站而且不是只是作業，是要公開出去的，

那時候還被 TPCA 台灣電路板協會把網站連結放在首頁，又覺得更有成就感；

後來化學系會長也想委託我幫忙架站，只是那時候沒有接受。

論文時則是用 C++ 寫 PSO 演算法解問題。

--

那時候念碩士時到處聽校內的演講，意外知道有交換學生這件事，

那時候我直接鎖定要去德國，直接不填備取選項，如果沒上我就不去交換了

除了德國我都不要! 就是對於德國有種莫名憧憬。

而德國又是全校最熱門的交換學校，所以一定要面試，

那因為我是系上頭一個申請交換學生的人，準備和查詢起資料特別辛苦。

於是碩班時白天寫論文、和教授 meeting、當兩門課助教批改考卷上課、當實驗室管理員、辦理實驗室聚餐、接國科會計劃、和機械化材系開會等；

晚上則是準備第一階段校內初審 : 純粹是交換申請、校內成績等基本資料；

還有第二階段校內面試 : 準備 PPT 上台報告包括自我介紹、申請動機、學習計劃等。

那時候收到面試通知的時候，是在我論文提案的前兩天，提案前就已經熬夜熬得天翻地覆不知白天黑夜了，提案完才休息一晚上馬上就開始準備面試資料。再來因為我想出國交換前把論文寫好，所以非常拚，那時候一到日都是早上起來忙到半夜。

面試通過後要再提供相關資料給德國校方審查 : 自傳、動機信、推薦信、校內成績、英文檢定、學習計劃、選修課程學分及採計表、其他有利審查等，

審查過了再能再去德國在台協會辦簽證、後續訂機票等。

而準備資料相關，認識的管院同學蓋章都是秘書蓋一蓋就好很快，

但我就必須要自己跑，找系主任與工學院院長簽名時之類，

因為是系上第一個，每次找對方簽名都會有個小面試吧，

系主任與院長都會問問相關的事情，所以會花點時間。

後來在德國選經濟系，因為覺得大學研究所都是工科，想修點經濟財金相關的課程，但我跑去選修了資訊相關課程寫 SAP，

那時候開始真的覺得我真的對寫程式有興趣，想要做相關工作，

然後那時候看到 ROR 很熱門薪水很高，就開始學 Ruby。

System Design Interview 不是比誰口才比較好

之前在台灣面試時都沒遇過 system design 面試，好像也較少聽聞有 system design 的關卡；

在英國時也不是所有面試時都會考 system design，通常是用來判斷該工程師是不是 senior 時會才比較會遇到。身為一個 senior engineer 除了被要求技術能力外，對於系統的架構設計和溝通能力也都會被期望達到一定的程度，同時也會預期多少具有領導能力。

而面試範圍可以小到設計一個 rate limiter，也可以大到設計一個 Netflix，其中要考慮的深度和廣度也就跟著不同，而且也有可能因為公司需求、軟硬體限制等而有所改變，沒有所謂最佳的解答。

在網路上看文章、影片 mock system design interview 時發現大家面試時，同樣一個問題，面試官的著眼點、流程的進行架構都不太一樣，那究竟什麼樣的內容是 system design inteview 時必須要談到的呢?

這裡用 designing a URL shortener 當範例，盡可能將流程結構化，並列出在設計時會考量的點，希望在面試時自己心中能有個大綱，好跑過一輪必考量的點；不過 system design 可以包含的範圍實在太廣了，可能會有些疏漏，還請見諒。

簡單輕鬆十分鐘學會 Greedy Algorithm (貪婪演算法) 刷 LeetCode

一、Greedy Algorithm

1.1 基本觀念介紹

Greedy Algorithm (貪婪演算法) 是指在對問題求解時，總是做出在當前看起來最好的選擇，所以此種演算法在解問題時，不是所有題型都能得到 global optimization (全域最佳解)，但對於相當多問題能產生整體最佳解或者是近似整體最佳解。

總之貪婪演算法的精神就是 : 短視近利、今朝有酒今朝醉，每一步面臨選擇時，都做眼前最有利的選擇，不考慮對將來是否有不良的影響，與 dynamic programming 不同，不會保留計算結果。

假設現在有個金額 M，有 1、5、10、20、50 元這些幣值種類，要盡可能用最少的錢幣湊到金額 M。根據貪婪演算法，能用 50 的就盡量用 50 的，否則盡量用 20 的...以此類推；在這種策略下，M 若是 15 則等於 10 * 1 + 5 * 1，共使用了 2 種錢幣。

但是如果我們換一組錢幣的種類如 1、5、11，貪婪演算法可能就不是最佳解。

或是我們有一個最多能背重量為 W 的背包，現在有 N 件物品，每件物品只能用一次且價值不相等，求解將哪些物品裝入背包裡物品價值總和最大，這時候因為要同時考慮重量和價值，也沒辦法用貪婪就取得最佳解。

這在下一篇 Dynamic Programming (動態規劃) 會講解到。

簡單輕鬆十分鐘學會 Graph (圖) 刷 LeetCode

一、Graph

1.1 基本觀念介紹

此處談及的 Graph 並不是指圖片或者圖形，而是由數個 vertex (點) 及數條 edgs (邊) 所構成；點與點之間以邊相連，表示這兩點有關聯性。

而一個頂點的 degree (度) 指與該頂點相連的邊的條數。

兩點之間也可以有很多條邊，代表這兩點有很多項關聯；一個點有連到自己的邊，稱之為self-loop (自環)，表示自己和自己有關聯。

1.1.1 Isomorphism / Isomorphic

(https://web.ntnu.edu.tw/~algo/Graph.html)

如果兩張圖的連接方式一模一樣時，則稱作同構圖。圖上的點可以任意移動位置，不論點的位置如何，都不會改變點與點之間的關聯。

簡單輕鬆十分鐘學會 Heap (堆疊) 刷 LeetCode

一、Heap

1.1 基本觀念介紹

Heap 有兩種分為資料結構和記憶體，都是取累積傾向的意思，而這邊要講的是資料結構的 Heap。

(https://www.geeksforgeeks.org/binary-heap/)

Heap 常見的實作為 Binary Heap，它的樹為 complete binary tree (完全二元樹) 如上圖。一棵依序節點可以從上到下、從左到右的表示為 1, 3, 6, 5, 9, 8。如果刪掉 node 9 那麼這便不是棵完全二元樹；如果拿掉 node 8 仍然是棵完全二元樹，因為整棵樹仍然可以從上到下、從左到右的表示成 1, 3, 6, 5, 9。

• 新增節點時優先從左到右填滿階層後才往下一層
• 概念基於 binary Tree，每個 node 下面最多只會有兩個 child，也有可能是一個或沒有
• 常使用 array 來實作，由左至右、由上到下表示出一個完全二元樹
• 若目前的 node 的 index 是 i，left child node 的 index 就是 i * 2 + 1，right child node 的 index 是 i * 2 + 2

簡單輕鬆十分鐘學會 Tree & Binary tree & Binary search tree 刷 LeetCode

一秒理解資料結構裡的樹

一、Tree & Binary tree & Binary search tree

1.1 基本觀念介紹

1.1.1 Tree

是一種模擬現實生活中樹幹和樹枝的資料結構，分為 :

Root (根節點)：沒有父節點的節點，所以每棵樹只有一個 root，如 A；在根節點之下是樹的樹枝，擁有 0 到 n 個子節點。

Node (節點)：一個個連結點，如 A、B、C ... M 都是結點。

Parent (父節點) : 節點 B 是 I 和 J 的父節點。

Child (子節點) : 節點 I 和 J 是 B 的子節點。

Siblings (兄弟節點) : 擁有共同父節點，如 I 和 J、K 和 L 和 M。

Leaf (葉節點)：節點沒有子節點的節點稱為葉節點，如 I、J、K、L、M、F、G、H。

Ancenstors (祖先節點) : 指某節點到根節點之間所經過的所有節點，都是此節點的祖先節點。

Level (階層) : 如果樹根是階層 1，其子節點即是階層 2，依序可以計算出樹的階層數；如節點A 階層是1，B、C 到 H 是階層 2，I、 J 到 M 是階層 3。

Height (樹高) : 又稱為 Depth (樹深)，指樹的最大階層數，如此圖的樹高是 3。

Dregree (分支度)：指每個節點擁有的子節點數，如節點 B 的分支度是 2，節點 E 的分支度是 3。

--
最廣義的樹對於 node 之 child 數目沒有限制，因此每個 node 可以有多個 child。

Linked list 也可以視作是樹只是每個 node 都只有一個 child。

Coding Interview 就是刷好刷滿刷爆 LeetCode 就會上?

我家可愛貓貓鎮樓，最後她一個都沒選；

畢竟她靠可愛就可以過活了，還是由奴才來好好工作賺罐罐錢吧。

之前在台灣面試時一直都沒怎麼遇過需要 coding interview，

而且我也一直對於在別人面前寫程式感到害羞，

還以為自己可以就這樣逃過 coding interview 的關卡。

殊不知在英國面試時就常常遇到 coding interview，雖然有時候會是 online test, assignment，

但果要進比較大的公司，coding interview 幾乎是必備。

還記得我第一次  coding interview 時，

面試開始時我想說我會寫我會寫欸然後我就直接寫完了，

還以為自己表現不錯題目有解出來 : )

結果得到 feedback 是 "感覺面試者沒有想跟面試官溝通"。

起先覺得困惑，後來才知道原來 coding interview 不是只是解題就好，

部分也是因為我自己這部份沒做好資料查詢。

所以痛定思定後，上網詳盡搜尋了相關資訊包括如何準備、面試時需要從哪些方面下手，並運用範例寫下 coding interview 過程，同時也請 MANGA 經過面試官訓練的朋友幫忙檢查內容。

我試圖把 coding interview 的流程寫成可以以較有結構式的方式執行；

這篇會分為平時練習時、面試前和面試過程中去解釋。

簡單輕鬆十分鐘學會 Stack & Queue (堆疊 & 佇列) 刷 LeetCode

一、Stack & Queue

1.1 基本觀念介紹

這裡講的 stack 和 queue，就是和 event loop 裡會用到的 call stack 和 callback queue 的基礎資料結構。

如果不是很清楚 event loop 是什麼，可以看這篇。

Stack 和 Queue 常常用 array 或 linked list，但沒有限定，只要能實作出該資料結構即可。

1.1.1 Stack

Last in, First out (LIFO)

最後一個進去，第一個出來。

比如書籍堆疊起來，最後一本堆上去的會第一本先被拿走；

最下面 bottom 是第一個被放入的 frame，然後 frame 被一個一個堆起來 (push)，

如果要把 frame 抽走，只能從最上方開始拿 (pop)。

(https://open4tech.com/stacks-vs-queues/)

簡單輕鬆十分鐘學會 Recursion (遞迴) 刷 LeetCode

一、Recursion

1.1 基本觀念介紹

遞迴就是在函式之中呼叫函式自己本身，本質上是將複雜的問題，拆分成具有相同性質的子問題，進而解決問題的方法。

一個基本的遞迴函式一定要有：

• 終止條件 (基本條件)

• 遞迴條件 (呼叫自己的條件)

如果沒有終止條件，就會無限循環直到當掉。

範例 1 : 假設輸入一個正整數 n，求 1 + 2 + … + n 的總和

我們可以很直覺的使用迭代 (迴圈) 的方式，將所有數字累加在一起。

但因為這個問題能拆成有規律的數個小問題，

如輸入正整數 2 → 1 + 2 = 3

輸入正整數 3 → 1 + 2 + 3 = 6

…

所以這時候就可以使用遞迴來計算。

Time complexity 是 O(n)，Space complexity 是 O(1)。

簡單輕鬆十分鐘 Linked List (鍊表) 刷 LeetCode

一、Linked List

1.1 基本觀念介紹

Linked list 是一種常見的資料結構，會包含 head 和 tail 的資訊，以 null 來代表 Linked list 的終點，使用 node 來記錄、表示、儲存資料。

1.1.1 Singly linked list

(https://www.geeksforgeeks.org/types-of-linked-list/)

單向鏈結串列 (單鏈結串列、線性鏈結串列、普通鏈結串列) 是最基本的鏈結串列，其特點是鏈結串列的鏈結方向是單向的，對鏈結串列的存取要通過從頭部開始，依序往下讀取。

每個 node 則會包含 value 和 next (Pointer，指向下一個 node 的位置) 的資訊。

簡單輕鬆十分鐘學會 Hash Map (雜湊表) 刷 LeetCode

先來個地獄梗 emtional damage!

一、Hash Map

1.1 基本觀念介紹

• Hash map 是儲存 (key, value) 這種 mapping 關係的一種資料結構 (當數據儲存在記憶體中時，決定數據的順序和位置的稱之為資料結構)
• 各語言 / library 基本上有其 hash function，如有需要也可以自行建置
• 語言不同名稱也會不同，但基本上 Hash map == Hash table == Hash object == Hash dictionary

(https://vhanda.in/blog/2012/07/shared-memory-hash-table/)

舉例來說，如果我們有 n 個數字要儲存時，通常會用 array 來存。 存好後如果我們拿到另一個數字 37，要判斷這個數字有沒有在 array 裡面，那我們就得跟 array 裡的元素一個個比較，這時 time complexcity 就會是 O(n)；下次再換查另一個數字時， time complexcity 又就會是 O(n)。 但如果已經先建立好 hash table，之後如果要查數字 37 時，建立 hash map 時雖然 time complexcity 會是 O(n)，但查詢的 time complexcity 就只會是 O(1)。 不過 O(1) 還是理論值，insert、search、lookup、delete 都有可能造成 time complexcity 是 O(n) (請看 example 3) 。

簡單輕鬆十分鐘看懂 Time complexity & Space complexity 分析刷 LeetCode

一、前導知識

1.1 演算法評估標準

當同一個問題可以用不同演算法去解決時，需要一個評量的標準去評估哪個演算法比較好，通常會用兩個指標去評量演算法的好壞 :

• Time complexity (時間複雜度)
• Space complexity (空間複雜度)

當然理論上所花費的時間和占用的記憶體是越小越好。

1.2 Time complexity

Time complexity 是電腦執行演算法所需要耗費的時間成本，通常會用 O (Big O notation) 去計算。

Big O notation 是解決一個規模為 n 的問題所花費的時間，或者所需步驟之數目；而演算法多快通常不是以秒而是步驟次數來衡量，因為每個人電腦效能會影響執行速度，若用秒數來衡量會顯得不夠客觀。