白板題技巧

Reference

確認問題環節

輸入的長度、輸入的資料型態、甚至是題目本身的一些限制。

跟面試官說大概會如何解

dry run + pseudo code 搭配分析這樣的時間複雜度與空間複雜度各別是多少

pseudo code

// pseudo code
[-2, -3, 0]
let max = -Infinity
let max2 = -Infinity
​
for(i from 0 to n-1)
    if(nums[i] > max){ max = nums[i], max2 = max}
    else if(nums[i] > max2) {max2 = nums[i]}

先把陣列中的第零個元素視為最大值
for 迴圈迭代過陣列:
  比較當前最大值與陣列中的元素
  如果當前值比較大，就更新最大值
回傳最大值

接著跟面試官提說「讓我用幾個實際案例，來確保這個偽代碼的演算法無誤」

以 [5, 2, 9, 1, 7] 的話

dry run

初始最大值 = 5
比較 2 > 5? No → 最大值維持 5
比較 9 > 5? Yes → 最大值變成 9
比較 1 > 9? No → 最大值變維持 9
比較 7 > 9? No → 最大值變維持 9
最終的最大值為 9

不會解先把架構寫出來

• 函式填空法: eg. prime 判斷質數

• 簡化法: 把大問題變小問題, eg: 好多星星

eg 凱薩加密，本來想法是全部搞再一起想

function getCaesarCipher(str, n){
 // str => ['a', 'p', 'l'] 97-122
 // charCodeAt() => [97, xx, xx]
 // +n [100, xx, xx] , if > 122, %122 + 97
 // String.fromCharCode(100,xx,xx)
}

getCaesarCipher('apple') // 全次英文一起解

以下這樣拆會變更簡單

CaesarCipher('a', 3) // 單一英文
/*
a: 0
b: 1
c: 2
*/
function CaesarCipher(str, n){
    let code = str.charCodeAt() - 97
    let newCode = (code + n)%26
    return String.fromCharCode(newCode)
}


function solve(strs, n){
    let result = ''
    for(let i=0; i<strs.length; i++){
        result += CaesarCipher(strs[i], n)
    }
    return result;
}