本文的全部稿件是由我們程式設計藝術室的部分成員：上善若水.qinyu，BigPotato，luuillu，well，July共同完成，共分4個部分，即4道題：
第一部分、從一道題，漫談資料結構、以及壓縮、位圖算法，由上善若水.qinyu完成，
第二部分、周遊n個元素取出等機率随機取出其中之一進制素，由BigPotato完成，
第三部分、提取出某日通路百度次數最多的那個IP，由luuillu完成，
第四部分、回文判斷，由well完成。全文由July統稿完成。
由于本人在這周時間上實在是過于倉促，來不及過多整理，是以我盡量保持上述我的幾位夥伴的原話原文，基本沒做多少改動。是以，标明為初稿，以後會更加詳盡細緻的進行修補完善。
海量資料處理往往會很有趣，有趣在什麼地方呢？
空間，available的記憶體不夠，需要反複交換記憶體
時間，速度太慢不行，畢竟那是海量資料
處理，資料是一次調用還是反複調用，因為針對時間和空間，通常來說，多次調用的話，勢必會增加預處理以減少每次調用的時候的時間代價。
題目如下
7、騰訊面試題：給40億個不重複的unsignedint的整數，沒排過序的，然後再給一個數，如何快速判斷這個數是否在那40億個數當中？
分析：1個unsigned int占用4位元組，40億大約是4G個數不到，那麼一共大約要用16G的記憶體空間，如果記憶體不夠大，反複和硬碟交換資料的話，後果不堪設想。
那麼怎麼儲存這麼多的資料呢？還記得伴随數組麼？還是那種思想，利用記憶體位址代替下标。
先舉例，在記憶體中應該是1個byte=8bit，那麼明顯有
0 = 0000 0000 255 = 1111 1111 69 = 0100 0101
那麼69可以表示0.2.6三個數存在，其餘的7以下的數不存在，0表示0-7都不存在，255表示0-7都存在，這就是位圖算法：通過全部置0，存在置1，這樣一種模式來通過連續的位址存貯資料，和檢驗資料的方法。
那麼1個 unsigned int代表多少個數呢？1個unsigned int 是一個2^32以内的數，那麼也就是這樣的1個數，可以表示32個數是否存在。同理申請一個unsigned int的數組a[n]則可以表示連續的(n+1)*32的數。也就是a[0]表示0-31的數是否存在，a[1]表示32-63的數是否存在，依次類推。
這時候需要用多大的記憶體呢？
16g/32=512M
512M和16G之間的差別，卻是是否一個32位尋址的CPU能否辦得到的事兒了，衆所周知，32位CPU最大尋址不超過4G，固然，你會說，現在都是64位的CPU之類的雲雲，但是，對于底層的設計者來說，尋址範圍越小越好操控的事實是不争的。
問題到這裡，其實基本上已經完事了，判斷本身，在位圖算法這裡就是找到對應的記憶體位置是否為1就可以了。
當資料超出可接受範圍之後…
當然，下面就要開始說一說，當資料超出了可以接受的範圍之後的事情了。比如， 2^66範圍的資料檢索，也會是一個問題
4倍于64位CPU尋址範圍，如果加上CPU本身的偏移寄存器占用的資源，可能應該是6-8個64位U的尋址範圍，如果反複從記憶體到硬碟的讀寫，過程本身就是可怕的。
算法，更多的是用來解決瓶頸的，就想現在，根本不用考慮記憶體超出8M的問題，但是20年前，8086的年代，記憶體4M，或者記憶體8M，你怎麼處理?固然做軟體的不需要完全考慮摩爾定律，但是摩爾定律絕對是影響軟體和算法編寫者得想法的。
再比如，烏克蘭俄羅斯的一批壓縮高手，比如國内有名的R大，為什麼壓縮會出現？就是因為，要麼存不下，要麼傳輸時間過長。網絡再好，64G的高清怎麼的也得下載下傳個一段時間吧。海量資料處理，永遠是考慮超過了目前硬體條件的時候，該怎麼辦？！
那麼我們可以發現一個更加有趣的問題，如果存不下，但是還要存，怎麼辦！
壓縮！這裡簡單的說一嘴，無損壓縮常見的為Huffman算法和LZW(Lenpel-Ziv &Welch)壓縮算法，前者研究不多，後者卻經常使用。
因為上面提到了位圖算法，我就用常見的位圖類的資料舉例：
以下引自我的摘抄出處忘記了，請作者見諒：
“對原始資料ABCCAABCDDAACCDB進行LZW壓縮
原始資料中，隻包括4個字元(Character),A,B,C,D,四個字元可以用一個2bit的數表示，0-A,1-B,2-C,3-D,從最直覺的角度看，原始字元串存在重複字元：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字元串可以替代表示為:45A4CDDAA5DB,這樣是不是就比原資料短了一些呢！
LZW算法的适用範圍
為了差別代表串的值(Code)和原來的單個的資料值(String)，需要使它們的數值域不重合，上面用0-3來代表A-D,那麼AB就必須用大于3的數值來代替，再舉另外一個例子，原來的數值範圍可以用8bit來表示，那麼就認為原始的數的範圍是0～255，壓縮程式生成的标号的範圍就不能為0～255（如果是0-255，就重複了）。隻能從256開始，但是這樣一來就超過了8位的表示範圍了，是以必須要擴充資料的位數，至少擴充一位，但是這樣不是增加了1個字元占用的空間了麼？但是卻可以用一個字元代表幾個字元，比如原來255是8bit,但是現在用256來表示254，255兩個數，還是劃得來的。從這個原理可以看出LZW算法的适用範圍是原始資料串最好是有大量的子串多次重複出現，重複的越多，壓縮效果越好。反之則越差，可能真的不減反增了。
僞代碼如下
1 STRING = get input character
2 WHILE there are still input characters DO
3 CHARACTER = get input character
4 IF STRING+CHARACTER is in the string table then
5 STRING = STRING+character
6 ELSE
7 output the code for STRING
8 add STRING+CHARACTER to the string table
9 STRING = CHARACTER
10 END of IF
11 END of WHILE
12 output the code for STRING
看過上面的适用範圍在聯想本題，資料有多少種，根據同餘模的原理，可以驚人的發現，其實真的非常适合壓縮，但是壓縮之後，盡管存下了，在查找的時候，勢必又需要解碼，那麼又回到了我們當初學習算法時候，的那句經典話，算法本身，就是為了解決時間和空間的均衡問題，要麼時間換空間，要麼空間換時間。
更多的，請讀者自行思考，因為，壓縮本身隻是想引起讀者思考，已經是題外話了~本部分完--上善若水.qinyu。
問題描述
1．一個檔案中含有n個元素，隻能周遊一遍，要求等機率随機取出其中之一。
先講一個例子，5個人抽5個簽，隻有一個簽意味着“中簽”，輪流抽簽，那麼這種情況，估計這5個人都不會有異議，都覺得這種方法是公平的，這确實也是公平的，“抓阄”的方法已經有很長的曆史了，要是不公平的話老祖先們就不幹了。
或許有人覺得先抓的人中簽的機率會大一些，因為要是前面的人中了，後面的中簽機率就是0了，也可能有人會覺得後面抓的人更有優勢，因為前面拿去了不中的簽，後面中簽的機率就大，那麼我們就計算一下吧。
問題分析
第一個人中簽的機率是1/5,
第二個人中簽的情況隻能在第一個人未中時才有可能，是以他中的機率是4/5 X 1/4 = 1/5（4/5表示第一個人未中，1/4表示在剩下的4個簽裡中簽的機率），是以，第二個人最終的中簽機率也是1/5，
同理，第三個人中簽的機率為：第一個人未中的機率X 第二個人未中的機率X第三個人中的機率，即為：4/5 X 3/4 X 1/3 = 1/5，
一樣的可以求出第四和第五個人的機率都為1/5，也就是說先後順序不影響公平性。
說這個問題是要說明這種前後有關聯的事件的機率計算的方式，我們回到第1個問題。前幾天我的一個同學電面百度是被問到這個問題，他想了想回答說，依次周遊，遇到每一個元素都生成一個随機數作為标記，如果目前生成的随機數大于為之前保留的元素生成的随機數就替換，這樣操作直到檔案結束。
但面試官問到：如果生成的随機數和之前保留的元素的随機數一樣大的話，要不要替換呢？
你也許會想，一個double的範圍可以是-1.79E+308 ~ +1.79E+308，要讓兩個随機生成的double相等的機率不是一般的微乎其微啊！但計算機世界裡有條很讓人傷心的“真理”：可能發生的事件，總會發生！
那我們遇到這種情況，是換還是不換？To be or not to be， that’s a question！
就好比，兩個人百米賽跑，測出來的時間一樣，如果隻能有一個人得冠軍的話，對于另一個人始終是不公平的，那麼隻能再跑一次，一決雌雄了！
我的政策
下面，說一個個人認為比較滿足要求的選取政策：
順序周遊，目前周遊的元素為第L個元素，變量e表示之前選取了的某一個元素，此時生成一個随機數r，如果r%L == 0(當然0也可以是0~L-1中的任何一個，機率都是一樣的), 我們将e的值替換為目前值，否則掃描下一個元素直到檔案結束。
你要是給面試官說明了這樣一個政策後，面試官百分之一千會問你這樣做是等機率嗎？那我們來證明一下。
證明
在周遊到第1個元素的時候，即L為1，那麼r%L必然為0，是以e為第一個元素，p=100%，
周遊到第2個元素時，L為2，r%L==0的機率為1/2, 這個時候，第1個元素不被替換的機率為1X(1-1/2)=1/2,
第1個元素被替換，也就是第2個元素被選中的機率為1/2 = 1/2,你可以看到，隻有2時，這兩個元素是等機率的機會被選中的。
繼續，周遊到第3個元素的時候，r%L==0的機率為1/3，前面被選中的元素不被替換的機率為1/2 X (1-1/3)=1/3,前面被選中的元素被替換的機率，即第3個元素被選中的機率為1/3
歸納法證明，這樣走到第L個元素時，這L個元素中任一被選中的機率都是1/L，那麼走到L+1時，第L+1個元素選中的機率為1/(L+1), 之前選中的元素不被替換，即繼續被選中的機率為1/L X ( 1-1/(L+1) ) = 1/(L+1)。證畢。
也就是說，走到檔案最後，每一個元素最終被選出的機率為1/n， n為檔案中元素的總數。好歹我們是一個技術部落格，看不到一丁點代碼多少有點遺憾，給出一個選取政策的僞代碼，如下：
僞代碼
Element RandomPick(file):
Int length = 1;
While( length <= file.size )
If( rand() % length == 0)
Picked = File[length];
Length++;
Return picked
近日，看見我的一些同學在他們的面經裡面常推薦結構之法算法之道這個部落格，感謝東南大學計算機學院即将找工作的同學們對本博的關注，歡迎批評指正！--BigPotato。
問題描述：海量日志資料，提取出某日通路百度次數最多的那個IP。
方法: 計數法
假設一天之内某個IP通路百度的次數不超過40億次,則通路次數可以用unsigned表示.用數組統計出每個IP位址出現的次數, 即可得到通路次數最大的IP位址.
IP位址是32位的二進制數,是以共有N=2^32=4G個不同的IP位址, 建立一個unsigned count[N];的數組,即可統計出每個IP的通路次數,而sizeof(count) == 4G*4=16G, 遠遠超過了32位計算機所支援的記憶體大小,是以不能直接建立這個數組.下面采用劃分法解決這個問題.
假設允許使用的記憶體是512M, 512M/4=128M 即512M記憶體可以統計128M個不同的IP位址的通路次數.而N/128M =4G/128M = 32 ,是以隻要把IP位址劃分成32個不同的區間,分别統計出每個區間中通路次數最大的IP, 然後就可以計算出所有IP位址中通路次數最大的IP了.
因為2^5=32, 是以可以把IP位址的最高5位作為區間編号, 剩下的27為作為區間内的值,建立32個臨時檔案,代表32個區間,把相同區間的IP位址儲存到同一的臨時檔案中.
例如:
ip1=0x1f4e2342
ip1的高5位是id1 = ip1 >>27 = 0x11 = 3
ip1的其餘27位是value1 = ip1 &0x07ffffff = 0x074e2342
是以把 value1 儲存在tmp3檔案中.
由id1和value1可以還原成ip1, 即 ip1 =(id1<<27)|value1
按照上面的方法可以得到32個臨時檔案,每個臨時檔案中的IP位址的取值範圍屬于[0-128M),是以可以統計出每個IP位址的通路次數.進而找到通路次數最大的IP位址
程式源碼:
test.cpp是c++源碼.
#include <fstream>
#include <iostream>
#include <ctime>
using namespace std;
#define N 32 //臨時檔案數
#define ID(x) (x>>27) //x對應的檔案編号
#define VALUE(x) (x&0x07ffffff) //x在檔案中儲存的值
#define MAKE_IP(x,y) ((x<<27)|y) //由檔案編号和值得到IP位址.
#define MEM_SIZE 128*1024*1024 //需配置設定記憶體的大小為 MEM_SIZE*sizeof(unsigned)
char* data_path="D:/test/ip.dat"; //ip資料
//産生n個随機IP位址
void make_data(const int& n)
{
ofstream out(data_path,ios::out|ios::binary);
srand((unsigned)(time(NULL)));
if (out)
{
for (int i=0; i<n; ++i)
{
unsigned val=unsigned(rand());
val = (val<<24)|val; //産生unsigned類型的随機數
out.write((char *)&val,sizeof (unsigned));
}
}
}
//找到通路次數最大的ip位址
int main()
//make_data(100); //
make_data(100000000); //産生測試用的IP資料
fstream arr[N];
for (int i=0; i<N; ++i) //建立N個臨時檔案
char tmp_path[128]; //臨時檔案路徑
sprintf(tmp_path,"D:/test/tmp%d.dat",i);
arr[i].open(tmp_path, ios::trunc|ios::in|ios::out|ios::binary); //打開第i個檔案
if( !arr[i])
cout<<"open file"<<i<<"error"<<endl;
ifstream infile(data_path,ios::in|ios::binary); //讀入測試用的IP資料
unsigned data;
while(infile.read((char*)(&data), sizeof(data)))
unsigned val=VALUE(data);
int key=ID(data);
arr[ID(data)].write((char*)(&val), sizeof(val)); //儲存到臨時檔案件中
for(unsigned i=0; i<N; ++i)
arr[i].seekg(0);
unsigned max_ip = 0; //出現次數最多的ip位址
unsigned max_times = 0; //最大隻出現的次數
//配置設定512M記憶體,用于統計每個數出現的次數
unsigned *count = new unsigned[MEM_SIZE];
for (unsigned i=0; i<N; ++i)
memset(count, 0, sizeof(unsigned)*MEM_SIZE);
//統計每個臨時檔案件中不同數字出現的次數
unsigned data;
while(arr[i].read((char*)(&data), sizeof(unsigned)))
++count[data];
//找出出現次數最多的IP位址
for(unsigned j=0; j<MEM_SIZE; ++j)
if(max_times<count[j])
{
max_times = count[j];
max_ip = MAKE_IP(i,j); // 恢複成原ip位址.
}
delete[] count;
unsigned char *result=(unsigned char *)(&max_ip);
printf("出現次數最多的IP為:%d.%d.%d.%d,共出現%d次",
result[0], result[1], result[2], result[3], max_times);
執行結果.
--luuillu。
（初稿，寫的比較急，請審閱、增補、修改）
回文判斷是一類典型的問題，尤其是與字元串結合後呈現出多姿多彩，在實際中使用也比較廣泛，而且也是面試題中的常客，是以本文就結合幾個典型的例子來體味下回文之趣。
回文，英文palindrome，指一個順着讀和反過來讀都一樣的字元串，比如 madam、我愛我，這樣的短句在智力性、趣味性和藝術性上都頗有特色，中國曆史上還有很多有趣的回文詩呢 ：）
一、回文判斷
那麼，我們的第一個問題就是：判斷一個字串是否是回文
通過對回文字串的考察，最直接的方法顯然是将字元串逆轉，存入另外一個字元串，然後比較原字元串和逆轉後的字元串是否一樣，一樣就是回文，這個方法的時空複雜度都是 O(n)。
我們還很容易想到隻要從兩頭開始同時向中間掃描字串，如果直到相遇兩端的字元都一樣，那麼這個字串就是一個回文。我們隻需要維護頭部和尾部兩個掃描指針即可，代碼如下：
/**
*check weather s is a palindrome, n is the length of string s
*Copyright(C) fairywell 2011
*/
bool IsPalindrome(const char *s, int n)
if (s == 0 || n < 1) return false; // invalid string
char *front, *back;
front = s; back = s + n - 1; // set front and back to the begin and endof the string
while (front < back) {
if (*front != *back) return false; // not a palindrome
++front; --back;
return true; // check over, it's a palindrome
這是一個直白且效率不錯的實作，隻需要附加 2 個額外的指針，在 O(n) 時間内我們可以判斷出字元串是否是回文。
是否還有其他方法？呵呵，聰明的讀者因該想到了不少變種吧，不過時空複雜度因為不會有顯著提升了（為什麼？），下面再介紹一種回文判斷方法，先上代碼：
bool IsPalindrome2(const char *s, int n)
char *first, *second;
int m = ((n>>1) - 1) >= 0 ? (n>>1) - 1 : 0; // m is themiddle point of s
first = s + m; second = s + n - 1 - m;
while (first >= s)
if (s[first--] !=s[second++]) return false; // not equal, so it's not apalindrome
代碼略有些小技巧，不過相信我們聰明的讀者已經看清了意思，這裡就是從中間開始、向兩邊擴充檢視字元是否相等的一種方法，時空複雜度和上一個方法是一模一樣的，既然一樣，那麼我們為什麼還需要這種方法呢？首先，世界的美存在于它的多樣性；其次，我們很快會看到，在某些回文問題裡面，這個方法有着自己的獨到之處，可以友善的解決一類問題。
那麼除了直接用數組，我們還可以采用其他的資料結構來判斷回文嗎呢？請讀者朋友稍作休息想想看。相信我們聰明的讀者肯定想到了不少好方法吧，也一定想到了經典的單連結清單和棧這兩種方法吧，這也是面試中常常出現的兩種回文資料結構類型。
對于單連結清單結構，處理的思想不難想到：用兩個指針從兩端或者中間周遊并判斷對應字元是否相等。是以這裡的關鍵就是如何朝兩個方向周遊。單連結清單是單向的，是以要向兩個方向周遊不太容易。一個簡單的方法是，用經典的快慢指針的方法，定位到連結清單的中間位置，将連結清單的後半逆置，然後用兩個指針同時從連結清單頭部和中間開始同時周遊并比較即可。
對于棧就簡單些，隻需要将字元串全部壓入棧，然後依次将各字元出棧，這樣得到的就是原字元串的逆置串，分别和原字元串各個字元比較，就可以判斷了。
二、回文的應用
我們已經了解了回文的判斷方法，接下來可以來嘗試回文的其他應用了。回文不是很簡單的東西嗎，還有其他應用？是的，比如：查找一個字元串中的最長回文字串
Hum，還是請讀者朋友們先自己想想看看。嗯，有什麼好方法了嗎？枚舉所有的子串，分别判斷其是否為回文？這個思路是正确的，但卻做了很多無用功，如果一個長的子串包含另一個短一些的子串，那麼對子串的回文判斷其實是不需要的。
那麼如何高效的進行判斷呢？既然對短的子串的判斷和包含它的長的子串的判斷重複了，我們何不複用下短的子串的判斷呢（哈，算法裡也跑出軟體工程了），讓短的子串的判斷成為長的子串的判斷的一個部分！想到怎麼做了嗎？Aha，沒錯，擴充法。從一個字元開始，向兩邊擴充，看看最多能到多長，使其保持為回文。這也就是為什麼我們在上一節裡面要提出 IsPalindrome2 的原因。
具體而言，我們可以枚舉中心位置，然後再在該位置上用擴充法，記錄并更新得到的最長的回文長度，即為所求。代碼如下：
*find the longest palindrome in a string, n is the length of string s
int LongestPalindrome(const char *s, int n)
int i, j, max;
if (s == 0 || n < 1) return 0;
max = 0;
for (i = 0; i < n; ++i) { // i is the middle point of the palindrome
for (j = 0; (i-j >= 0) && (i+j < n); ++j) // if the lengthof the palindrome is odd
if (s[i-j] != s[i+j]) break;
if (j*2+1 > max) max = j * 2 + 1;
for (j = 0; (i-j >= 0) && (i+j+1 < n); ++j) // for theeven case
if (s[i-j] != s[i+j+1]) break;
if (j*2+2 > max) max = j * 2 + 2;
return max;
代碼稍微難懂一點的地方就是内層的兩個 for 循環，它們分别對于以 i 為中心的，長度為奇數和偶數的兩種情況，整個代碼周遊中心位置 i 并以之擴充，找出最長的回文。
當然，還有更先進但也更複雜的方法，比如用 s 和逆置 s' 的組合 s$s' 來建立字尾樹的方法也能找到最長回文，但建構的過程比較複雜，是以在實踐中用的比較少，感興趣的朋友可以參考相應資料。
回文的内容還有不少，但主要的部分通過上面的内容相信大家已經掌握，希望大家能抓住實質，在實踐中靈活運用，回文的内容我就暫時介紹到這裡了，謝謝大家--well。
附注：
如果讀者對本文的内容或形式，語言和表達不甚滿意。完全了解。我之前也跟程式設計藝術室内的朋友們開玩笑的說：我暫不做任何修改，題目會标明為初稿。這樣的話，你們才會相信或者知曉，你們的才情隻有通過我的語言和表達才能最大限度的發揮出來，被最廣泛的人輕而易舉的所認同和接受（不過，以上4位兄弟的思維靈活度都在本人之上）。呵呵，開個玩笑。
本文日後會抽取時間再做修補和完善。若有任何問題，歡迎随時不吝指正。謝謝。
完。
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)