A Za, A Za, Fighting...

C瓜同學(xué)一直關(guān)注這個(gè)我這個(gè)小地方，下面是一些我面試中或者和同學(xué)討論的一些不錯(cuò)的面試題，備份一下，也希望對(duì)你有用。

1：C++的多態(tài)是如何實(shí)現(xiàn)的？如果你用C如何來實(shí)現(xiàn)面向?qū)ο蟮亩鄳B(tài)？
解:
C++多態(tài)的實(shí)現(xiàn)主要依賴虛函數(shù)表，以及每個(gè)對(duì)象中指向虛函數(shù)表的指針
至于如何用C來實(shí)現(xiàn)面向?qū)ο蟮亩鄳B(tài)，我覺得比較靠譜的方法是函數(shù)指針，通過賦予函數(shù)指針不同的函數(shù)(地址)來調(diào)用不同的函數(shù)，得到不同的結(jié)果

2：判斷一個(gè)有向圖中是否有環(huán)。上篇文章里面寫的那個(gè)杯子倒水問題。給一個(gè)都是正整數(shù)的數(shù)組，和一個(gè)正整數(shù)sum，求是否存在和為sum的子數(shù)列。
解:
【判斷一個(gè)有向圖是否有環(huán)】

【杯子倒水問題】
把所有可能的操作列出來，寬度優(yōu)先搜索，從初始狀態(tài)到結(jié)束狀態(tài)

聯(lián)想到的問題有：
a. 給一個(gè)都是正整數(shù)的數(shù)組，是否存在兩個(gè)數(shù)的和為某個(gè)給定的sum? 三個(gè)數(shù)呢？
針對(duì)兩個(gè)數(shù)的情況，可以先排序，然后一個(gè)指針front指向第一個(gè)元素(最小)，一個(gè)指針tail指向最后一個(gè)元素(最大)，如果*front + *tail < sum, ++front, 如果*front + *tail > sum, --tail;
如果三個(gè)數(shù)，或者N個(gè)數(shù)，該如何做？

動(dòng)態(tài)規(guī)劃，類似于01背包問題
f[i][k]表示前i個(gè)元素中任意k個(gè)元素的和的集合，那么有:
                 f[i][k] = f[i-1][k] + (f[i-1][k-1] + array[i])
or:
f[i][v]表示前i個(gè)元素中是否存在和的v的子數(shù)列，那么有:
                 f[i][v] = 1, only if f[i-1][v]=1 or f[i-1][v-array[i]]=1

3：兩個(gè)有大量id的集合A和B，數(shù)量上億級(jí)，如何求出兩個(gè)集合的交集，A中有的B中沒有的，和B中有的A中沒有的集合。
涉及海量數(shù)據(jù)處理: 二分搜索、位圖Bitmap、哈希Hash、字典樹、分成若干小文件+多路歸并... 

4：設(shè)計(jì)實(shí)現(xiàn)一個(gè)管理內(nèi)存的小模塊，接口為void* checkout(size_t size), void checkin(void* ptr)。

5： 設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)一副象棋子的擺放，盡量壓縮空間，使得方便通過傳輸?shù)搅硗庖慌_(tái)機(jī)子上然后恢復(fù)棋盤。

6：數(shù)組的眾數(shù)問題，最長遞增子序列問題。找大量數(shù)據(jù)中前k個(gè)大的數(shù)。找大量數(shù)據(jù)中第k大的數(shù)。

7：一個(gè)平面中有很多點(diǎn)，用最快的算法找出相隔最近的兩個(gè)點(diǎn)。

8：select/poll和epoll，基本互聯(lián)網(wǎng)公司都會(huì)提到這個(gè)東西。

9：給敏感詞列表，和一大段文本，考慮一個(gè)敏感詞過濾的算法。

10：海量數(shù)據(jù)問題，很多，一般方法就為分治、hash、位圖。

很多沒有標(biāo)準(zhǔn)答案，面試過程中的探討很重要。找工作不難，找份好工作還是難的，基礎(chǔ)知識(shí)很重要，數(shù)據(jù)結(jié)構(gòu)和算法、操作系統(tǒng)、編程語言的掌握，數(shù)據(jù)庫和網(wǎng)絡(luò)。可以根據(jù)自己的喜好，偏向于某個(gè)方向。