聯想到的問題有:
a. 給一個都是正整數的數組,是否存在兩個數的和為某個給定的sum? 三個數呢?
針對兩個數的情況,可以先排序,然后一個指針front指向第一個元素(最小),一個指針tail指向最后一個元素(最大),如果*front + *tail < sum, ++front, 如果*front + *tail > sum, --tail;
如果三個數,或者N個數,該如何做?
動態規劃,類似于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的子數列,那么有:
f[i][v] = 1, only if f[i-1][v]=1 or f[i-1][v-array[i]]=1
3:兩個有大量id的集合A和B,數量上億級,如何求出兩個集合的交集,A中有的B中沒有的,和B中有的A中沒有的集合。
涉及海量數據處理: 二分搜索、位圖Bitmap、哈希Hash、字典樹、分成若干小文件+多路歸并...
4:設計實現一個管理內存的小模塊,接口為void* checkout(size_t size), void checkin(void* ptr)。
5: 設計一個數據結構,存儲一副象棋子的擺放,盡量壓縮空間,使得方便通過傳輸到另外一臺機子上然后恢復棋盤。
6:數組的眾數問題,最長遞增子序列問題。找大量數據中前k個大的數。找大量數據中第k大的數。
7:一個平面中有很多點,用最快的算法找出相隔最近的兩個點。
8:select/poll和epoll,基本互聯網公司都會提到這個東西。
9:給敏感詞列表,和一大段文本,考慮一個敏感詞過濾的算法。
10:海量數據問題,很多,一般方法就為分治、hash、位圖。
很多沒有標準答案,面試過程中的探討很重要。找工作不難,找份好工作還是難的,基礎知識很重要,數據結構和算法、操作系統、編程語言的掌握,數據庫和網絡。可以根據自己的喜好,偏向于某個方向。