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

題目：

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

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

上一篇末，我們得到了一個優化過後的演算法

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

5. 再次檢視 (Walk Through)

在實際動手寫 Code 前，再次檢視一下演算法。

首先要確認這個演算法出來的結果的確有符合問題的描述，並且是否過程中用到了所有可用的線索或是資訊

再來要確認一下之前優化的過程中打亂一些原本的順序或是邏輯（在這個例子中是沒有）

再來就是確認一下具體的 input / output 的型態/格式，以及適合用什麼具體的資料結構比較適合

比方說，在這個例子中，用來記錄每年人口的 populationRecord 是否真的還有必要？

是否能在尋找 MAX_POPULATION 的過程中，就只紀錄符合 MAX_POPULATION 的年份就好？

所以這部分可以在實作的時候進一步改善！

6. 實作 (Implement)

接下來就是真正的動手寫 Code！這部分的要點就是

結果要符合演算法
盡可能在結構單純 / 易讀 / 彈性
針對一些低階，常見的錯誤（比方說 Null Pointer Exception 檢查）盡可能的盡善盡美，Corner case / special case 的檢查之類的

以下就是一個 Sample 的 code (使用 Kotlin 實作)

// define Human data structure first
data class Human(
    var birthYear: Int,
    var deathYear: Int
)

fun findMaxPopulation(list: List<Human>): List<Int> {
    var resultYearList = ArrayList<Int>()
    var MAX_POPULATION = -1

    for(h: Human in list){
        // filter invalid data
        if(h.birthYear > h.deathYear) continue
        if(h.birthYear < 0) continue
        if(h.deathYear < 0) continue

        var population = findPopulation(h.birthYear, list)

        // find the next MAX value
        if(MAX_POPULATION < population){
            MAX_POPULATION = population

            // clear the previous saved data
            resultYearList.clear()
            resultYearList.add(h.birthYear)
        }
        // Some other year that matches the same MAX POPULATION
        else if(MAX_POPULATION == population)
            resultYearList.add(h.birthYear)
    }

    return resultYearList;
}

// find the population for specific year
private fun findPopulation(year: Int, list: List<Human>): Int {
    var birth = 0
    var death = 0
    for(h: Human in list){
        // Num of person birth earlier than this
        if(h.birthYear <= year)
            birth++
        // Num of person died earlier than this
        if(h.deathYear <= year)
            death++
    }

    return (birth - death)
}

7. 測試/驗證 (Test)

最後其實就是做一些測試，一來用最早列舉出的實例，再來可以用一些 Special case 來測試

無效數據（出生年份大於死亡年份 / 出生、死亡年份為負值）
Corner case 最高人口只有一年，或是最高人口出現在多個年份（甚至每一年）

另外還有一個情況是有人出生死亡同一年，這個可能最初要跟面試者確認，這樣的 case 在當年的人口要不要計算。
在這個例子裡面是假設人口計算於年尾，所以同年出生死亡的人口不會被計入（birth++ & death++ 所以最後會抵消）

其實這個最後結果還有一些可以優化的地方，比方說目前這個時間複雜度是 O(n²)，應該可以用一些空間換取時間讓他變成 O(n)

不過這裡單純是透過這個例子，還有整個思考流程來 Demo 這個技巧。

這裡就簡單回顧一下問題解決的思路順序：

確認問題（Listen）

列舉 (Example)

暴力破解 (Brute Force)

優化 (Optimize)

再次檢視 (Walk Through)

實作 (Implement)

測試/驗證 (Test)

希望對於在準備 Coding interview 的人有所幫助。

MF99 coding 💻

keep learning; keep coding;

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

題目：

5. 再次檢視 (Walk Through)

6. 實作 (Implement)

7. 測試/驗證 (Test)