終於有時間來還債了。如果想知道自己的市場價值，最好的方法就是: 去面試。

蠻多人覺得刷大量題目是很必要的，但我遇到的面試官，大部分更著重在，過程的提問和分析問題能力。

之前的工作不常碰樹的結構，很巧的是，面試剛好被要求實作相關的東西。當下我很誠實的說: "I’m not quite familiar. I’ll try my best."。

很幸運的是，順利拿到那次的 offer。我覺得我唯一做對的的事，就是盡可能的闡述我知道的，然後和考官討論。

面試官需要的是...之後可以一起合作的同事。所以刷題練習時的，不要局限於做出來，可以透過問自己一些基本的問題、延伸問題，避免見樹不見林。

以下會拿一題 leetcode 作為範例:

簡單翻譯，把陣列中的 "0" 移到最前面，並且必須要以 in-place 的方式來處理。
in-place algorithm 是指不產生額外的記憶體空間下，用時間換取空間。

所以心裡有個底，這限制可能會影響時間複雜度。

既然要處理的是陣列，那這時需要確認基本的問題: 會遇到 null 的 array 嗎? 會遇到負數嗎? 除了 0 之外的 item 需不需要保留原本的順序?

面試時提問可以限縮方向，刷題時提問可以讓自己想得更多。

假設左邊的順序不影響，那麼我會需要一個 int 紀錄交換的位置，然後利用一個 for 迴圈，去進行交換的動作。

到目前為止，都還沒 Coding。先動手的人就輸了~

換個角度想，假設左邊的順序不影響，也不會出現負數，弄個快速排序 (Quick sort) 也行阿! 這時零永遠得在前面，後面的順序沒差~ 不過需要再反轉一次~

這時候你需要知道: 什麼是分而治之 (Divide and conquer) ? 為何比同樣原理、一樣O(n log n)的合併排序還有效率?

跟面試官確認你要用哪個流程，接下來才是寫程式跟測試。

上一下 C# 的 code，如果你不寫 C# 沒關係，我會解釋細節重點在哪:

1. int 紀錄交換位置+ for 迴圈
   (1) 方法的命名、程式碼的排版，也會是加扣分的細節
   (2) 紀錄交換位置的 switchIndex 不一定要從 0 開始。不同題目有不同優勢。

        public void MoveZeroes(int[] arr)
        {
            int switchIndex = arr.Length;
            for (int i = arr.Length-1; i >= 0; i--)
            {
                if (arr[i] == 0) 
                {
                    switchIndex--;

                    // array items 互換
                    int temp = arr[i];
                    arr[i] = arr[switchIndex];
                    arr[switchIndex] = temp;
                }
            }
            return arr;
        }

2. 快速排序(In-place)
   (1) 分而治之(Divide and conquer) 重點在遞迴的設計。找出什麼時候是 base case (最簡單的情況也會是終止條件)，什麼時候是 recursive case (要繼續)。
   (2) 這邊也可以使用 Two-pointer 的技巧，有興趣的人可看這邊。他的系列文章統整得很好。
   (3) 盡可能 Clean code，有時候提出方法會讓可讀性變好。

        public void MoveZeroes(int[] arr)
        {
            QuickSort(arr, 0, arr.Length - 1);
        }
        private void QuickSort(int[] arr, int start, int end)
        {
            int index;
            if (start < end) 
            {
                index = Partition(arr, start, end);
                QuickSort(arr, start, index-1);
                QuickSort(arr, index + 1, end);
            }
        }

        private int Partition(int[] arr, int start, int end)
        {
            // 變數 temp 是交換用，這裡 pivot 取陣列的最右側
            // pointer 紀錄換到哪
            int temp;
            int pivot = arr[end];
            int pointer = start-1;

            for (int i = start; i <= end-1; i++) 
            {
                if (arr[i] < pivot) 
                {
                    pointer++;
                    temp = arr[i];
                    arr[i] = arr[pointer];
                    arr[pointer] = temp;
                }
            }

            temp = arr[pointer+1];
            arr[pointer+1] = arr[end];
            arr[end] = temp;
            return pointer + 1;
        }

最後推薦幾本中文書，真心好用，沒有葉配:

1. 白話演算法
2. 提升程式設計師的面試力：189道面試題目與解答
3. 內行人才知道的系統設計面試指南