A Za, A Za, Fighting...

C瓜同學一直關注這個我這個小地方，下面是一些我面試中或者和同學討論的一些不錯的面試題，備份一下，也希望對你有用。

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

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

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

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

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

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

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

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

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

7：一個平面中有很多點，用最快的算法找出相隔最近的兩個點。

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

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

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

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