緣起：Code interview：Coding 面試與思考訓練 - 💻 MF99 coding

Code interview：Coding 面試與思考訓練 - 實戰演練 part 1 - 💻 MF99 coding

題目：

給定一組人的列表，列表當中有記錄著他們每個人的出生以及死亡年份

問題﹔請找出人口數量最多的年份

在上一篇，我們已經列舉出了一組相對看起來客觀且具代表性的實例，接著就是試著在邏輯上找出我們的解答。

數據：

人名	出生	死亡
A	1920	1980
B	1974	1998
C	1933	1954
D	1923	1999
E	1902	1958
F	1901	1928
G	1963	2009
H	1938	1979
J	1949	1991
K	1913	1959
L	1975	2010

時間軸參考

f:id:mouseface99:20191202124142p:plain

3. 暴力破解 (Brute Force)

從時間軸來看，似乎我們要找的就是這些線段裡面重疊最多的年份。

但是如何把幾何問題轉換到代數問題呢？

這時候我們可以先試著暴力破解這個問題～

最直覺(笨)的做法，就是我們一年一年的來看，每一年的人口數。

按照時間順序列出來，然後觀察總體人口的變化。

年份	人口	年份	人口
1901	1	1959	4
1902	2	1963	5
1913	3	1974	6
1920	4	1975	7 <- MAX
1923	5	1979	6
1928	4	1980	5
1933	5	1991	4
1938	6	1998	3
1949	7 <- MAX	1999	2
1954	6	2009	1
1958	5	2010	0

所以初步列出來之後，我們就有一個基於這個暴力破解法的演算法

population: int = 0

for(i from startYear to lastYear){
    if (i has someone birth)
        population++

    if (i has someone die)
        population--

    if(population > MAX_POPULATION)
        MAX_POPULATION = population
}

return (the years that population matches MAX_POPULATION)

簡單來說，就是每一年去看當年的人口數，並且從中找出最大值。

最後再針對這個最大值，反查出這是在哪一個年份發生的。

4. 優化 (Optimize)

接下來就是再次檢視整個暴力破解的過程，我們可以發現幾點：

其實不需要每一年都看，因為人口的變化只會出現在有人出生或是死亡的年份。
由於我們關注的只有人口最大值，人口最大值基本上只會出現在有人出生的年份（因為有人去世的年份，人口只會減少不會變多）

所以，與其計算每一年的人口變化，不如

優化 1

只關注在「有人出生」的那一年的人口數

接著，進一步思考，以下這個問題

人口數的定義是什麼？

透過手動計算，與時間軸的觀察。可以發現到人口數的定義：

優化 2

P(Y) 表示第Ｙ年的人口數

P(Y) ＝（比Y早出生的人）-（比Y早去世的人）

透過優化 1+2，看起來我們就有一個可行的優化演算法了

list : List<Human>
populationRecord : Map<year, population>

// Record population for each year
// And also find the MAX_POPULATION
for (Human in list){
    Y = Human.birth
    population = (num of birth years < Y) - (num of death years < Y)

    populationRecord.put( Y, population )

    if (population > MAX_POPULATION)
        MAX_POPULATION = population
}

maxPopulationYears: List<Year>

// Extract the Years that matches MAX_POPULATION
for(Years in populationRecord){
    if( population == MAX_POPULATION)
        maxPopulationYears.add(Year)
}

return maxPopulationYears

下一步就可以準備動手寫 Code 了！

Code interview：Coding 面試與思考訓練 - 實戰演練 part 3 - 💻 MF99 coding

雜記

其實，這篇裡面提到的這兩個步驟，看起來好像很流暢，很順的就可以這樣解出來

但是實際上在實戰中，這兩步驟是最難的，也是花最多時間的。

所以才會需要多一點練習，如何在摸不著頭緒的題目中，先試著用最簡單的暴力破解法來解決（有些題目連暴力破解都還要想一下...）

然後再從暴力破解的過程中找出規律、規則，找出可以用程式寫成邏輯的部分。

所以最好一開始的暴力破解法是用手寫，而不要一開始就試著用程式寫。

另外還有一點很重要的技巧，就是跟 面試官的互動，台灣人常常在解題的過程都是內心戲，毫無動靜的在腦中思考。

當然靜下心思考也是很重要，但是別忘了你現在正在面試！外國公司常常是在面試的過程中，一方面除了看你有沒有能力解決這些問題之外，另外一方面也是在觀察妳的思考邏輯跟思路方向。所以練習在思考的過程，同時也能夠用口述的表達自己目前在思考的方向，思考的策略也是很重要。

因為有時候常常題目過於奇耙，或是有時候剛好就是時間不夠無法完整的解決。但是如果面試官覺得你的思考方向正確，並且思考過程是合乎他們的要求的，在面試分數上基本上也不會太差！（總比過程什麼都不講，面試官也不知道你在想什麼，然後最終題目也沒解出來好太多）

MF99 coding 💻

keep learning; keep coding;

Code interview：Coding 面試與思考訓練 - 實戰演練 part 2

題目：

3. 暴力破解 (Brute Force)

4. 優化 (Optimize)

雜記