應該問什么問題 · 白板編程淺談——Why, What, How

所以，技術面試題目不應該太難，也不應太簡單，不能是腦筋急轉彎，也不能直接來自網絡。前三點并不難滿足：我們可以去?[算法導論](http://www.amazon.cn/gp/product/B00AK7BYJY/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B00AK7BYJY&linkCode=as2&tag=lucida-23)，[編程珠璣](http://www.amazon.cn/gp/product/B00SFZH0DC/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B00SFZH0DC&linkCode=as2&tag=lucida-23)，以及?[計算機程序設計藝術](http://www.amazon.cn/gp/product/B00478TO44/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B00478TO44&linkCode=as2&tag=lucida-23)?這些經典算法書籍中的課后題/練習題挑選合適的題目，也可以自己創造題目。然而，由于?[careercup](http://www.careercup.com/page)?這類網站的存在，沒有什么題目可以做到絕對原創——畢竟沒有人能阻止面試者把題目發到網上，所以任何編程題目都逃脫不了被公開的命運。不過，盡管面試者會把編程題目發到網上，甚至會有一些『好心人』給出答案，但這并不代表面試官不能繼續使用這道題：因為盡管題目被公開，但題目的考察點和延伸問題依然只有面試官才知道。這有點像?[公鑰加密](http://zh.wikipedia.org/wiki/%E5%85%AC%E5%BC%80%E5%AF%86%E9%92%A5%E5%8A%A0%E5%AF%86)，公鑰（面試題）是公開的，但私鑰（解法，考察點，以及延伸問題）只有面試官才知道。這樣即便面試者知道面試題，也不會妨礙面試官考察面試者的技術能力。接下來，讓我們看看什么問題適合白板編程。 ## 不止一種解法良好的編程問題都會有不止一種解法。這樣面試者可以在短時間內給出一個不那么聰明但可實現的『粗糙』算法，然后通過思考（或面試官提示）逐步得到更加優化的解法，面試官可以通過這個過程觀察到面試者的思維方式，從而對面試者進行更客觀的評估。以?[數組最大子序列和](http://en.wikipedia.org/wiki/Maximum_subarray_problem)?為例，它有一個很顯然的 O(n3) 解法，將 O(n3) 解法稍加改動可以得到 O(n2) 解法，利用分治思想，可以得到 O(n*logn) 解法，除此之外它還有一個 o(n) 解法。（[編程珠璣](http://www.amazon.cn/gp/product/B00SFZH0DC/ref=as_li_ss_tl?ie=UTF8&camp=536&tag=lucida-23&creativeASIN=B00SFZH0DC&linkCode=as2&creative=3132)?和?[數據結構與算法分析 C語言描述](http://www.amazon.cn/gp/product/B002WC7NGS/ref=as_li_ss_tl?ie=UTF8&camp=536&creative=3132&creativeASIN=B002WC7NGS&linkCode=as2&tag=lucida-23)?對這道題均有非常精彩的描述，有興趣的朋友可以自行閱讀） ## 考察點明確良好的編程問題應擁有大量考察點，面試官應對這些考察點爛熟于心，從而給出更加客觀量化的面試結果。這里可以參考我之前在?[從武俠小說到程序員面試](http://lucida.me/blog/from-wuxia-to-programmer-interview/)?提到的?`to_upper`。 ## 延伸問題良好的編程問題應擁有延伸問題。延伸問題既可以應對面試者背題的情況，也可以漸進的（Incremental）考察面試者的編程能力，同時還保證了面試的延續性（Continuity）。以?[遍歷二叉樹](http://zh.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86)?為例：面試官可以從非遞歸中序遍歷二叉樹開始提問，面試者有可能會很快的寫（或是背）出一個使用棧的解法。這時面試官可以通過延伸問題來判別面試者是否在背題：使用常量空間中序遍歷**帶有父節點指針**的二叉樹，或是找到二叉搜索樹中第 n 小的元素。下面是中序遍歷二叉樹的一些延伸問題： ~~~ |--中序遍歷二叉樹 | |--非遞歸中序遍歷二叉樹 | |--常量空間，非遞歸遍歷帶父節點的二叉樹 | | | |--在帶父節點的二叉搜索樹尋找第 N 小的元素 | | | |--可否進一步優化時間復雜度？ | |--常量空間，非遞歸遍歷不帶父節點的二叉樹 ~~~ 上面的問題不但可以被正向使用（逐步加強難度），也可以被逆向使用（逐步降低難度）：同樣從非遞歸中序二叉樹遍歷開始提問，如果面試者無法完成這個問題，那么面試官可以降低難度，要求面試者編寫一個遞歸版本的中序遍歷二叉樹。