github: https://github.com/careercup/CtCI-6th-Edition
my-coding: https://git.coding.net/daydaygo/CTCI.git
date: 2016-03-22 19:45

里面有一張面試流程圖, 只能用 嚇人 和 專業(yè) 來(lái)形容了: 1年以上的面試準(zhǔn)備 + 擴(kuò)充人脈 + 自己的項(xiàng)目展示 + 找一個(gè)友人模擬面試
請(qǐng)準(zhǔn)備紙質(zhì)簡(jiǎn)歷: 我之前的做法是展示自己的blog, 當(dāng)然是有 秀 的成分在里面, 不過紙質(zhì)簡(jiǎn)歷方便面試官寫寫畫畫.

十大常見錯(cuò)誤

1. 只在計(jì)算機(jī)上面coding(我感覺這項(xiàng)沒有錯(cuò), 好的工具更重要)
2. 不做行為面試題
3. 不模擬面試
4. 試圖死記硬背答案
5. 不大聲說出自己的解題思路
6. 過于倉(cāng)促
7. 代碼不夠嚴(yán)謹(jǐn)
8. 不做測(cè)試
9. 修正錯(cuò)誤漫不經(jīng)心
10. 輕言放棄

受期待的面試者

1. 對(duì)技術(shù)充滿熱情
2. 關(guān)注擴(kuò)展性&存儲(chǔ)限制(互聯(lián)網(wǎng)行業(yè))
3. 談?wù)摦a(chǎn)品: 喜歡什么? 有什么值得改進(jìn)?
4. 熱衷創(chuàng)造
5. 系統(tǒng)設(shè)計(jì)(雖然我總是聽到 系統(tǒng)架構(gòu) 不是一天就練成的)

簡(jiǎn)歷

1. 長(zhǎng)度適中, 亮點(diǎn)優(yōu)先級(jí)
2. 工作經(jīng)歷: 要點(diǎn) + 亮點(diǎn)
3. 項(xiàng)目經(jīng)歷
4. 編程語(yǔ)言 + 工具

行測(cè)

項(xiàng)目相關(guān)(濃縮成關(guān)鍵字): 1. 最難的部分; 2. 有什么收獲; 3. 最有意思的部分; 4. 最難解的bug; 5. 最享受的過程; 6. 與團(tuán)隊(duì)成員的沖突
應(yīng)對(duì): 1. 力求具體, 切忌自大; 2. 省略細(xì)枝末節(jié); 3. 條理清晰(主題現(xiàn)行/SAR)

1. 你有哪些缺點(diǎn): 正視不足, 重點(diǎn)突出怎么克服的
2. 項(xiàng)目中最難的問題: 不要泛泛而談, 這樣會(huì)顯得這個(gè)項(xiàng)目沒有什么難度
3. 問面試官的問題: 1. 真實(shí)的問題; 2. 有見地的問題; 3. 富有激情

技術(shù)面試

需要了解的知識(shí)
常見面試問題
關(guān)于 2 的問題

注重 數(shù)據(jù)結(jié)構(gòu) + 算法

解決面試題:

1. 大部分時(shí)候都不能馬上解決問題
2. 提問, 消除歧義
3. 設(shè)計(jì)算法
4. 偽碼
5. 使用數(shù)據(jù)結(jié)構(gòu), 保持結(jié)構(gòu)清晰
6. 測(cè)試: 一般 / 極端情況 / 用戶錯(cuò)誤

算法題解法:

1. 舉例
2. 模式匹配(找相似的例子)
3. 簡(jiǎn)化推廣法(打 單詞 當(dāng)作 單個(gè)字符處理, hash 的原型)
4. 簡(jiǎn)單構(gòu)造(遞歸)
5. 數(shù)據(jù)結(jié)構(gòu)頭腦風(fēng)暴(把能想到的數(shù)據(jù)結(jié)構(gòu)都過一遍試試)

好代碼: 正確 / 簡(jiǎn)潔 / 高效 / 易讀 / 可維護(hù)

1. 多用數(shù)據(jù)結(jié)構(gòu)
2. 適量重用代碼
3. 模塊化
4. 靈活/健壯
5. 錯(cuò)誤檢查: 仔細(xì)驗(yàn)證輸入 / 邊界

其他

薪資考量: 工資 + 獎(jiǎng)勵(lì) + 年終獎(jiǎng)(時(shí)薪會(huì)是一個(gè)比較好的考量)
職業(yè)發(fā)展: 1. 增加履歷; 2. 增長(zhǎng)知識(shí); 3. 升遷(技術(shù)/管理); 4. 是否處于上升期
幸福指數(shù): 1. 產(chǎn)品; 2. 團(tuán)隊(duì); 3. 工作時(shí)長(zhǎng); 4. 企業(yè)文化
錄用談判: 1. 理直氣壯; 2. 手頭還有其他選擇; 3. 提出具體要價(jià); 4. 比預(yù)期稍高; 5. 不要只盯著薪水(待遇是多方面, 薪水是其中的大頭而已); 6. 選擇合適的方法(電話 / 郵件)
入職須知: 1. 制定時(shí)間表; 2. 人際網(wǎng)絡(luò); 3. 尋求經(jīng)理幫助

面試題

array & string

1. 散列表 Hashtable / HashMap: 數(shù)組 -> 鏈表 -> 二叉查找樹

2. 動(dòng)態(tài)數(shù)組 ArrayList: 存滿時(shí)動(dòng)態(tài)擴(kuò)容(一般為2倍)

3. StringBuffer: 處理字符串拼接, 申請(qǐng)一個(gè)可以容納所有字符串的數(shù)組

4. 判斷字符串的所有字符是否相同: 確定編碼( ascll 還是 unicode); ascll -> 256 個(gè)字符; 26個(gè)字母 -> int 變量的每位來(lái)存儲(chǔ)

5. c / c++ void reverse(char* str)

6. 判斷2個(gè)字符串重新排列后能否相等: 使用輔助數(shù)組計(jì)數(shù)

7. 替換字符串中所有空格為 %20: 遍歷出空格的數(shù)量, 算出新字符串的長(zhǎng)度, 從字符串尾部開始操作

8. aabcccccaaa -> a2b1c5a3 實(shí)現(xiàn)字符串壓縮:

i = 0; j =1;
str2 = [];
while(str[i]){
    while(str[i] == str[i+j]) j++;
    str2[] = str[i];
    str2[] = j;
    j = 1;
}
return strlen(str) > strlen(str2) ? str2 : str;

6. N x N 的矩陣旋轉(zhuǎn)90度: 順時(shí)針 a[i][j] -> a[j][n-i-1]; 逆時(shí)針: a[i][j] -> a[n-j-1][i]
7. M x N 的矩陣中, 含0的行和列全部清零: 遍歷, 使用2個(gè)輔助數(shù)組, 存儲(chǔ) 行/列 中0的位置
8. 調(diào)用一次 subString() 判斷 s2 是不是 s1 旋轉(zhuǎn)( s-> xy -> yx )得到: subString(s2, s1s1)

鏈表(LinkedList)

1. 注意是單向鏈表還是雙向鏈表

2. 創(chuàng)建鏈表: appendToTail(), 在結(jié)尾添加節(jié)點(diǎn)

3. 刪除單向鏈表中的節(jié)點(diǎn): prev.next = n.next 即可, 注意 檢查空指針 + 表頭/表尾 指針

4. 快行指針: 同時(shí)2個(gè)指針遍歷鏈表, 其中一個(gè)步速為2倍或固定長(zhǎng)度, 如a1->a2..an->b1->b2..bn => a1->b1..an->bn

5. 遞歸, 但是至少要 O(n)空間, 所有的遞歸都可以轉(zhuǎn)為迭代

6. 移除未排序鏈表中的重復(fù)節(jié)點(diǎn): 使用 Hashtable, 遍歷一次; 使用2個(gè)指針, 相當(dāng)于2個(gè)for循環(huán)

7. [算法]單向鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn): 2個(gè)指針, 一個(gè)先行k步(k大于鏈表長(zhǎng)度的情況也不用擔(dān)心了), 之后2個(gè)指針一起走

8. 刪除一個(gè)節(jié)點(diǎn)(你只能訪問這個(gè)節(jié)點(diǎn)): 使用下個(gè)節(jié)點(diǎn)替換當(dāng)前節(jié)點(diǎn)即可

9. 定值x將鏈表分為2部分: 使用2個(gè)鏈表來(lái)存儲(chǔ), 然后合并

10. 鏈表實(shí)現(xiàn)加法, 和數(shù)組實(shí)現(xiàn)加法類似

11. 有環(huán)鏈表: slow 步長(zhǎng)為1, fast 步長(zhǎng)為2; 當(dāng) slow 步行 k 到環(huán)起點(diǎn), 環(huán) size 為 m, 此時(shí) fast 在 m-k%m 處; 所以 fast/slow 在 m-k%m 處相遇; 再取一個(gè) 指針從 head 開始, 就可以在 環(huán)起點(diǎn) 相遇

12. 檢查回文: 反轉(zhuǎn)鏈表, 只需要比較前半部分; 棧; 遞歸, 每次 length-1, 終止條件 length<2

棧和隊(duì)列

棧 Stack
隊(duì)列 Queue

1. 一個(gè)數(shù)組實(shí)現(xiàn)3個(gè)棧: 固定分配, 只允許每個(gè)棧使用固定的數(shù)組空間; 不固定分配, 需要考慮數(shù)組回繞
2. 棧中添加一個(gè) min(): 節(jié)點(diǎn)增加 min 值; 使用輔助棧存儲(chǔ) min
3. 棧滿時(shí)新建棧 + popAt(int index): 使用數(shù)組棧來(lái)維護(hù)棧的數(shù)量, pop() / push() / empty() 等方法都要考慮是否需要維護(hù)這個(gè) 數(shù)組棧
4. 用棧實(shí)現(xiàn)漢諾塔: An = 2*An-1 + 1
5. 2個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
6. 升序棧: 一次彈出原棧的元素, 和新棧進(jìn)行比較, 彈出新棧的元素到原棧, 直到找到元素適合的位置
7. 維護(hù) queueDog + queueCat

樹&圖

潛在問題: 二叉樹&二叉查找樹; 平衡&不平衡(需要衡量算法的 最好/最壞 情況); 完滿&完整
二叉樹遍歷: 前/中/后/層次
樹的平衡: 紅黑樹 / 平衡二叉樹
單詞查找數(shù)(trie): 每個(gè)節(jié)點(diǎn)存儲(chǔ)字符, 每條路徑表示一個(gè)單詞
圖的遍歷: DFS / BFS

1. 判斷是否為平衡二叉樹: 從根節(jié)點(diǎn)開始遞歸判斷; 保存每個(gè)樹的高度

2. 判斷有向圖2點(diǎn)之間是否存在路徑: dfs / bfs 都可

3. 將有序數(shù)組構(gòu)建成高度最小的二叉查找數(shù): 依次使用數(shù)組中間節(jié)點(diǎn)作為根節(jié)點(diǎn), 構(gòu)建左右子樹
   無(wú)序數(shù)組構(gòu)建二叉查找數(shù): 依次插入元素到現(xiàn)有二叉樹, O(N*logN)

// 構(gòu)建子樹, 返回子樹根節(jié)點(diǎn)
TreeNode createMinimalBST(int arr[], int start, int end){
    if(end < start) return NULL;

    int mid = (start+end)>>1;
    TreeNode n = new TreeNode(arr[mid]);
    n.left = createMinimalBST(arr, start, mid-1);
    n.right = createMinimalBST(arr, mid+1, end);
    return n;
}
// 使用
createMinimalBST(arr,0,n-1);

4. 給定二叉樹, 創(chuàng)建某一深度上的所有節(jié)點(diǎn)的鏈表
   方法一: 前序遍歷, 遍歷過程中傳遞當(dāng)前層數(shù), 并把節(jié)點(diǎn)加入相應(yīng)鏈表中
   方法二: 層次遍歷

5. 檢查一個(gè)樹是否為 二叉查找樹
   二叉查找樹: 根節(jié)點(diǎn) >= 所有左子樹節(jié)點(diǎn), <= 所有右子樹節(jié)點(diǎn)
   最大最小值: 中序遍歷結(jié)果的時(shí)候, 不斷更新最大最小值, 如果不符合條件直接停止遍歷

6. 找出指定節(jié)點(diǎn)的中序后繼
   問題很簡(jiǎn)單, 但是邊界條件很多: null; 右子樹為null; 右子樹的最左邊節(jié)點(diǎn)

7. 找出二叉樹中某2個(gè)結(jié)點(diǎn)的第一個(gè)公共祖先
   遞歸訪問當(dāng)前節(jié)點(diǎn)的子樹, 看看是否包含 2 個(gè)結(jié)點(diǎn)

8. 判斷 T2(數(shù)據(jù)量比較小) 是不是 T1 的子樹(數(shù)據(jù)很大)
   遍歷 T1, 當(dāng)出現(xiàn)節(jié)點(diǎn)和 T2 根節(jié)點(diǎn)相同時(shí), 進(jìn)行比較

9. 樹中結(jié)點(diǎn)和為固定值的路徑

位操作

掩碼清零
小數(shù)的十進(jìn)制和二進(jìn)制: 依次乘 2 然后和 1 對(duì)比; 依次減去 1/2, 1/4, 1/8
n&(n-1): 清除 n 中最右邊的 1
n&(n-1)==0: n 是 2^k
a^b

3. 一個(gè)正整數(shù)二進(jìn)制表示中 1 的個(gè)數(shù)相同且大小最接近的 2 個(gè)數(shù)
4. 交換奇數(shù)和偶數(shù)位: 掩碼 -> 光 奇數(shù)位/偶數(shù)位 -> 移位 + 相加
5. 通過二進(jìn)制找出 0-n 中缺少的一個(gè)數(shù)

智力題

1. 找出20瓶藥中份量不同的一瓶: 一瓶有很多粒藥
2. 88 的棋盤切去2個(gè)對(duì)角, 是否還能使用 12 的方塊覆蓋(否, 使用黑白相間證明)
3. 5升水壺+3升水壺 -> 4升水? 數(shù)學(xué)定理: 2個(gè)數(shù)字互質(zhì), 則可以獲得這 1-2個(gè)數(shù)和之間的任意數(shù)
4. 每個(gè)人只能看到其他人的狀態(tài), 狀態(tài)a的人必須離開, 如果有 n 個(gè)人狀態(tài) a, 第幾天離開(n 個(gè)人 -> n 天, 使用數(shù)學(xué)推導(dǎo))
5. 2個(gè)雞蛋, 100層樓, 找出雞蛋扔下不會(huì)碎掉的層數(shù), 并使最差情況下的次數(shù)最少(圍繞 最差情況, 平衡2個(gè)雞蛋扔的負(fù)載)
6. 100個(gè)關(guān)上的柜子, 第i次改變第n*i柜子的狀態(tài), 還有幾個(gè)柜子開著(數(shù) -> 因子 -> 平方和)

數(shù)學(xué)&概率

1. 比較1投命中 & 3投>=2中 的概率
2. n邊行n個(gè)螞蟻相撞的概率(相撞 = 1 - 不相撞)
3. 2條線是否會(huì)相交(線 = 線段 + 射線 + 直線; 二元一次方程)
4. 加法 實(shí)現(xiàn) 減法/乘法/除法
5. 一條直線評(píng)分2個(gè)正方形(過正方形中心的直線就可以平分正方形)
6. 找出平面經(jīng)過點(diǎn)數(shù)最多的直線(使用 斜率+截距 來(lái)表示一條直線, 遍歷所有點(diǎn), 返回出現(xiàn)次數(shù)最多的直線)
7. 找出只有 3,5,7 因子的數(shù)中第k個(gè)數(shù)
   維護(hù)3個(gè)隊(duì)列, 每次判斷新插入數(shù), 然后放入相應(yīng)的隊(duì)列

對(duì)象對(duì)象設(shè)計(jì)

1. 標(biāo)準(zhǔn)52張撲克牌

2. 呼叫中心: call + 三級(jí)處理 員工/主管/經(jīng)理

3. 音樂點(diǎn)唱機(jī): 點(diǎn)唱機(jī)(是否收費(fèi)) + CD(可能是不同媒介) + 歌曲 + 藝術(shù)家 + 播放列表 + 顯示屏

4. 停車場(chǎng): 不同車 + 不同停車位(多層/多排/可停不同車)

5. 在線圖書閱讀系統(tǒng): one time one user one book + 會(huì)員資格和書籍延期 + 圖書搜索 + 書籍閱讀

6. 拼圖程序: 拼圖 = 邊 + 3種狀態(tài) + 位置(絕對(duì)/相對(duì)); 判斷相鄰拼圖是否可以拼在一起

7. 聊天服務(wù)器: 在線離線狀態(tài) + 請(qǐng)求(發(fā)送/接受/拒絕) + 更新狀態(tài) + 私聊/群聊 + 發(fā)送消息
   確定用戶在線: 定時(shí)詢問; 沖突信息; 負(fù)載(多臺(tái)機(jī)器); DOS 攻擊

8. 黑白棋設(shè)計(jì)

9. 內(nèi)存文件系統(tǒng)

10. 散列表, 使用 鏈表處理沖突

遞歸&動(dòng)態(tài)規(guī)劃

位操作: 使用開發(fā)中有遇到, 使用 php 做 socket client, 和 c++ server 通信, 包括 編碼 和 數(shù)據(jù)類型
測(cè)試: 測(cè)試轉(zhuǎn)開發(fā), 溫水煮青蛙; 準(zhǔn)備核心測(cè)試問題
PM: 處理模糊問題; 以客戶為中心(態(tài)度 + 技術(shù)); 多層次交流; 熱愛技術(shù); 團(tuán)隊(duì)/領(lǐng)能力
技術(shù)主管/項(xiàng)目經(jīng)理: 團(tuán)隊(duì)/領(lǐng)能力; 把握輕重緩急; 溝通; '把事情做好'的能力
創(chuàng)業(yè)公司: 個(gè)性契合; 技術(shù)能力(快速上手); 以往經(jīng)驗(yàn)
經(jīng)驗(yàn)積累: 多承擔(dān)編程工作; 善用閑暇時(shí)光
人脈:廣度　+　深度

1. 面試非易事, 姿態(tài)很重要.
   之前感覺自己能力很足, 去面試的時(shí)候把面試官給嗆了, 結(jié)果可想而知. 能力只是是否能夠勝任的前提條件, 最重要的還是與人相處與人合作與人溝通的能力.

2. 完美的解決問題并不是關(guān)鍵, 關(guān)鍵是要比其他面試者回答得更好.