如何準備面試中的Technical Questions - Cracking the Coding Interview

如何準備 P.60

記答案沒有用，練習如何解題目才是重中之重

四大步驟

盡量自己解決問題(但這裡我私心覺得如果沒寫過甚麼leetcode的話還是不要糾結太久，因為很多演算法是自己想破頭腦都想不出來的，不如趕快看解答，認識解法，知道怎麼解，等到累積了一定的解法之後再嘗試自己解決問題。不過當然不是一開始就看答案，而是思考個五分鐘十分鐘，沒想法再看)，要考慮空間和時間複雜度
把code寫在紙上
在紙上測試code，要測試general cases, base cases, error cases, and so on.
照著自己寫的code輸進電腦把寫錯的部分記錄下來，面試前當作提醒自己的材料

做越多模擬面試越好，和朋友和家人，都行!

必須具備的知識 P.60

儘管面試不是考驗你的記憶力，但還是會需要有基本知識(不然主考官還要跟你解釋什麼是int也太奇怪了吧)

以下是必備知識!必須要會使用會實作還要會分析時間和空間複雜度

Data Structures	Alogrithms	Concepts
Linked Lists	Breadth-First Search	Bit Manipulation
Tree, Tries, &Graphs	Depth-First Search	Memory (Stack vs. Heap)
Stacks & Queues	Binary Search	Recursion
Heaps	Merge Sort	Dynamic Programming
Vectors/ArrayLists	Quick Sort	Big O Time & Space
Hash Tables

二次方表 P.61

有用的表!當然不用去背

Power of 2	Exact Value (X)	Approx. Value	X Bytes into MB, GB, etc.
7	128
8	256
10	1024	1 thousand	1KB
16	65,536		64KB
20	1,048,576	1 million	1MB
30	1,073,741,824	1 billion	1GB
32	4,294,967,296		4GB
40	1,099,511,627,776	1 trillion	1TB

解決問題的流程 P.62

BUD Optimization

Bottlenecks
Unnecessary Work
Duplicated Work

聽: 注意每個資訊，每一個都可能是想出最優解的關鍵
例子: 大多例子都太小或太特殊，審慎選擇例子
暴力解: 以最快速度想出暴力解，但不需要實作，然後從這基礎上優化
優化:使用上述的BUD方法來優化，或試試以下方法
- 找尋未使用的資訊，通常需要題目所有的資訊來達到最優解
- 手動解決問題，然後反向工程看看是怎麼解的
- 寫錯，然後去想為什麼會行不通，能不能修好
- 要在時間和空間上面做取捨，通常Hash table會很有用
再過一次solution: 有了最優解之後就可以詳細走一遍流程，一定要了解所有細節後再開始Coding
實作: 寫出好看的code
測試: 照以下流程
1. 概念測試: 徹底走一遍流程
2. 不尋常或不標準的程式碼
3. Hot spots，例如運算或null nodes
4. 小的測資，比大的來得更有效率
5. Special cases and edge cases
找到Bug也要謹慎修復

不要忘了講話面試官想聽你怎麼解的

解決問題的流程之詳細解析 P.63

Listen Carefully

抓重點例如:

“Given two arrays that are sorted, find …”

這時候就要記得有兩個陣列然後是已經排序好的

一開始聽到就寫在白板上就不怕忘記了，不然想十分鐘條件就全忘了
通常面試官給的資訊都是有用的，所以一定要認真聽，記下來

Draw an Example P.64

畫出例子會有極大的幫助，不要硬在腦海裡解決問題
切忌例子太小，例如一棵樹，只有三個node就太小了，用該小例子來想解法容易忽略細節，也可能會找不到規律
不要用special case來當例子，應該要general的

State a Brute Force P.64

暴力解也是一個解，一定要說出來讓面試官知道，因為說不定有些面試者連暴力解都沒想出來呢。不說出來反而面試官會懷疑你連最簡單的解都想不出來
初始解效能不重要，解釋完空間和時間複雜度後就可以著手優化了

Optimize P.64

以下幾個技巧可以幫助更快找到優化

找尋任何未使用的資訊，任何題目的設定都可能是最憂解的突破口
用新的例子!
解錯也無所謂，可以想想怎麼處理那些錯誤
在時間和空間之間做取捨，有時多一點空間可以幫助優化整個演算法
預先計算一些需要的資訊可能可以節省一些運算時間
用Hash table!
想想看可能的最佳運算時間

Walk Through P.65

有了優化之後，不要急著寫code

確保沒有問題再寫，因為板上書寫很慢，所以想法越接近完美越好
Psedocode不要寫得像偷懶版的code，如果是那樣那就直接寫code就好了😂

Implement P.65

確保想法OK後，進入實作環節

盡量把code寫得越整齊越好，不然也會造成自己debug困難
有一些繁雜的工作例如生成一個 {\{1, 2, 3}, {4, 5, 6}, ...} 的陣列，不用浪費時間，直接假設有一個method initIncrementalMatrix(int size)就好了
有些面試官很在意檢查錯誤，可以寫個todo然後解釋要測試什麼
必要時可以假設有額外的classes來輔助，最後有時間再把輔助class的實作部分填上
變數名要取好，不要寫無意義的字母
變數名太長的話可以在第二次出現時放上縮寫，並告知面試官
如果卡住了，回去再看一次例子然後再過一遍

Test P.66

手動測試是很緩慢的，與其直接拿最一開始想的測資來測試，不如嘗試以下方法:

從概念開始，意思是再看一遍和分析一遍code，像是解釋給面試官聽一樣，想想程式是否按照自己想的那樣執行
檢查認為理所當然或是奇怪的地方，例如x = length - 2和從i = 1開始的迴圈
檢查容易錯的地方，例如:
- 遞迴的base case
- Integer division
- Null nodes in binary trees
- Linked list的起始和終點
Special cases:
- null
- single element values
- extreme cases
- etc.

發現bug的時候不要急著修，先想想為何，檢查是否是整個邏輯上的問題

優化的技巧1: Look for BUD P.67

Bottlenecks
Unnecessary work
Duplicated word

Bottlenecks

有兩種常見的情況:

例如先sort一個array，然後再找其中的element，這樣第一步需要O(n log n)而第二步需要O(N)。此時就算能夠優化第二步為O(log n)甚至是O(1)，都是沒有太大意義的，因為第一步是瓶頸，演算法依然需要O(n log n)的時間
很多重複的作業

例如:

Bottlenecks Example

這題可以直接暴力解，或是先排序再用binary search找到答案，但這樣的話勢必會需要至少$O(n log n)$，此時sorting就是瓶頸，除非優化sorting的部分，不然沒什麼幫助。除非不排序，那要怎麼快速搜尋沒排序的陣列呢?答案就是用Hash Table

Unncessary Work P.68

例如下題:

Unncessary Work example

暴力解就是四個嵌套循環

int n = 1000;

for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            for (int d = 1; d <= n; d++) {
                if (Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3)) {
                    System.out.println(a + " " + b + " " + c + " " + d);
                }
            }
        }
    }
}

可以簡單優化一下，print了之後就可以break了

int n = 1000;

for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            for (int d = 1; d <= n; d++) {
                if (Math.pow(a, 3) + Math.pow(b, 3) == Math.pow(c, 3) + Math.pow(d, 3)) {
                    System.out.println(a + " " + b + " " + c + " " + d);
                    break;
                }
            }
        }
    }
}

但演算法依舊是$O(N^4)$

此外可以用數學公式優化一下，因為d可以藉由a,b,c算出來: $d = \sqrt[3] {a^3 + b^3 - c^3}$

int n = 1000;

for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            int temp = (int)Math.pow(a * a * a + b * b * b - c * c * c, 1.0 / 3.0);
            int d = (int)Math.round(Math.pow(temp, 3)); // Round to int
            if (a * a * a + b * b * b == c * c * c + d * d * d) { // Validate that the value works
                System.out.println(a + " " + b + " " + c + " " + d);
            }
        }
    }
}

此時就縮減為$O(N^3)$

Duplicated Work P.68

此外可以注意到一直重複為(a, b)計算(c, d)，所以直接建立(c, d)陣列一次就可以了

n = 1000
for c from 1 to n
    for d from 1 to n
        result = c^3 + d^3
        append (c, d) to list at value map[result]

for each result, list in map
    for each pair1 in list
        for each pair2 in list
            print pair1, pair2

此時就可以只算(a, b)，因此降為$O(N^2)$

優化的技巧2: DIY P.69

當題目說設計一個演算法的時候，腦袋就很可能會打結，想不出什麼好方法。但如果給的是一個實際的工作，那就反而有可能想出很好的演算法。例如給一疊紙，每張紙上都有人名，從A排到Z，如果這時候要找Peter，那幾乎無庸置疑的任誰都會從中間隨便抽一張看離P有多近，而不會從頭開始找。

所以說有時把問題轉換為實際的問題，並嘗試解決的時候就有可能優化了解法

例如:

Example: Given a smaller strings and a bigger string b, design an algorithm to find all permutations of the shorter string within the longer one.Print the location of each permutation

給定:

s: abbc
b: cbabadcbbabbcbabaabccbabc

最暴力解的方法就是窮舉出所有permutation，但這樣會至少需要$O(S! * B)$，極其慢的演算法

但其實如果手動來檢查的話，通常都會抓四個然後看看有沒有都在s裡面，這樣就降到$O(B * S)$

優化的技巧3: 簡化與泛化 P.71

例如:

Example: A ransom note can be formed by cutting words out of a magazine to form a new sentence. How would you figure out if a ransom note (represented as a string) can be formed from a given magazine (string)?

這時可以把問題簡化為cutting characters out of a magazine而非整個詞，很明顯這時就可以建立一個陣列然後數characters，每個陣列中的元素就是一個字母然後數ransom note中各個字母的出現次數

而泛化就是轉化為原本題目的要求，這時也不用array，而是用hash table來映射word和其頻率

總而言之就是從簡化後的題目開始想，可能對於原題就會有頭緒了

優化的技巧4: Base case與建立 P.71

從最基本的case開始，一步一步往更複雜的case，藉以剖析步驟，通常到最後會生出遞迴演算法

Optimize & Solve Tech. #4

優化的技巧5: 資料結構Brainstorm P.72

簡單來說就是列出所有資料結構然後一個一個看是否能在題目中使用

Optimize & Solve Tech. #5

題目做越多越會有該用甚麼演算法的直覺

Best Conceivable Runtime (BCR)

基本上指的是演算法在特定的題目中最快的可能執行速度
例如找出兩個陣列相同的數字，那就不可能比O(A + B)更快，因為一定要看過這兩個陣列

處理錯誤的答案

小錯誤是正常的，面試官不會把誰做對的題數當作評判標準，而是答案的優化度、花了多久時間、需要多少幫助、code的乾淨程度等等的
重要的是怎麼解，解題的邏輯是否合理

如果遇到寫過的題目

要和面試官說，因為題目是拿來測試problem-solving skills，如果遇到已經做過的題目就沒辦法評估了
告訴面試官反而會讓自己加分，如果被發現沒有主動告知很可能誠信會扣分

最適合面試的語言

選擇自己最熟悉的
選擇熱門語言，這樣面試官也比較有可能知道
選擇可讀性佳的語言，例如Java和Python，此外Scala和Objectives C可能就不是那麼適合因為語句比較不同
有些語言會增加潛在的問題，例如C++，除了會有一般程式的bug，還會有記憶體管理以及指針的問題
選擇易用的語言
個人覺得選擇自己最熟悉的語言就對了，除非太冷門

好的程式長什麼樣子

正確: 在正常以及非正常的inputs都可以正確執行
效率: 程式越高效率越好
簡單: 十行能解決的問題就不要用一百行來解決
可讀性: 其他工程師也能輕易看懂
易維護: 讓其他工程師方便維護，也方便自己以後維護；犧牲一點效能增加易維護性是值得的

大方使用資料結構

例如寫一個相加方法，$Ax^a + Bx^b + …$，

//  Bad implementation
// 這種寫法幾次方就array就要都大
int[] sum(double[] expr1, double[] expr2) {  

}

// 稍微差一點的寫法
// 會需要傳很多數值
??? sum(double[] coeffsl, double[] expon1, double[] coeffs2, double[] expon2) {

}

// 好的寫法，直接定義一個新的資料結構，方便提取與儲存
class ExprTerm {
 double coefficient;
 double exponent;
}

ExprTerm[] sum(ExprTerm[] exprl, ExprTerm[] expr2) {

}

適當重用code以及模組化

把演算法不同功能的部分包裝到不同的方法裡有助於提升程式整潔度和易讀性也易於測試
面試官樂見

不要放棄

要保持積極的態度解決問題，即便題目非常困難，畢竟過程更重要

參考

Gayle Laakmann McDowell - Cracking the Coding Interview

面試

#筆記 #Interview

如何準備面試中的Technical Questions - Cracking the Coding Interview

https://f88083.github.io/2024/01/03/如何準備面試中的Technical-Questions-Cracking-the-Coding-Interview/

作者

Simon Lai

發布於

2024年1月3日

許可協議

528. Random Pick with Weight - Medium 上一篇

735. Asteroid Collision - Medium 下一篇