百度2011.10.16校園招聘會筆試題
一、演算法設計
1、設rand(s，t)返回[s,t]之間的隨機小數，利用該函式在一個半徑為R的圓內找隨機n個點，並給出時間複雜度分析。
思路：這個使用數學中的極座標來解決，先呼叫[s1，t1]隨機產生一個數r，歸一化後乘以半徑，得到R*(r-s1)/(t1-s1)，然後在呼叫[s2，t2]隨機產生一個數a，歸一化後得到角度：360*(a-s2)/(t2-s2)
2、為分析使用者行為，系統常需儲存使用者的一些query，但因query非常多，故系 統不能全存，設系統每天只存m個query，現設計一個演算法，對使用者請求的query進行隨機選擇m個，請給一個方案，使得每個query被抽中的概率相 等，並分析之，注意：不到最後一刻，並不知使用者的總請求量。
思路：如果使用者查詢的數量小於m，那麼直接就存起來。 如果使用者查詢的數量大於m，假設為m+i，那麼在1-----m+i之間隨機產生一個數，如果選擇的是前面m條查詢進行存取，那麼概率為m/(m+i)， 如果選擇的是後面i條記錄中的查詢，那麼用這個記錄來替換前面m條查詢記錄的概率為m/(m+i)*(1-1/m)=(m-1)/(m+i)，當查詢記錄 量很大的時候，m/(m+i)== (m-1)/(m+i)，所以每個query被抽中的概率是相等的。
3、C++ STL中vector的相關問題：
(1)、呼叫push_back時，其內部的記憶體分配是如何進行的?
(2)、呼叫clear時，內部是如何具體實現的?若想將其記憶體釋放，該如何操作?
vector的工作原理是系統預先分配一塊CAPACITY大小的空間，當插入的資料超過這個空間的'時候，這塊空間會讓某種方式擴充套件，但是你刪除資料的時候，它卻不會縮小。
vector為了防止大量分配連續記憶體的開銷，保持一塊預設的尺寸的記憶體，clear只是清資料了，未清記憶體，因為vector的capacity容量未變化，系統維護一個的預設值。
有什麼方法可以釋放掉vector中佔用的全部記憶體呢?
標準的解決方法如下
template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
( vt );
}
事實上，vector根本就不管記憶體，它只是負責向記憶體管理框架acquire/release記憶體，記憶體管理框架如果發現記憶體不夠了，就malloc， 但是當vector釋放資源的時候(比如destruct), stl根本就不呼叫free以減少記憶體，因為記憶體分配在stl的底層：stl假定如果你需要更多的資源就代表你以後也可能需要這麼多資源(你的list, hashmap也是用這些記憶體)，所以就沒必要不停地malloc/free。如果是這個邏輯的話這可能是個trade-off
一般的STL記憶體管理器allocator都是用記憶體池來管理記憶體的，所以某個容器申請記憶體或釋放記憶體都只是影響到記憶體池的剩餘記憶體量，而不是真的把記憶體歸還給系統。這樣做一是為了避免記憶體碎片，二是提高了記憶體申請和釋放的效率不用每次都在系統記憶體裡尋找一番。
二、系統設計
正常使用者端每分鐘最多發一個請求至服務端，服務端需做一個異常客戶端行為的過濾系統，設伺服器在某一刻收到客戶端A的一個請求，則1分鐘內的客戶端任何其 它請求都需要被過濾，現知每一客戶端都有一個IPv6地址可作為其ID，客戶端個數太多，以至於無法全部放到單臺伺服器的記憶體hash表中，現需簡單設計 一個系統，使用支援高效的過濾，可使用多臺機器，但要求使用的機器越少越好，請將關鍵的設計和思想用圖表和程式碼表現出來。
三、求一個全排列函式：
如p([1,2,3])輸出：
[123]、[132]、[213]、[231]、[321]、[323]
求一個組合函式
如p([1,2,3])輸出：
[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]
這兩問可以用虛擬碼。
1、程序切換需要注意哪些問題?
儲存處理器PC暫存器的值到被中止程序的私有堆疊; 儲存處理器PSW暫存器的值到被中止程序的私有堆疊; 儲存處理器SP暫存器的值到被中止程序的程序控制塊;
儲存處理器其他暫存器的值到被中止程序的私有堆疊; 自待執行程序的程序控制塊取SP值並存入處理器的暫存器SP; 自待執行程序的私有堆疊恢復處理器各暫存器的值;
自待執行程序的私有堆疊中彈出PSW值並送入處理器的PSW; 自待執行程序的私有堆疊中彈出PC值並送入處理器的PC。
2、輸入一個升序陣列，然後在陣列中快速尋找兩個數字，其和等於一個給定的值。
這個程式設計之美上面有這個題目的，很簡單的，用兩個指標一個指向陣列前面，一個指向陣列的後面，遍歷一遍就可以了。
3、有一個名人和很多平民在一塊，平民都認識這個名人，但是這個名人不認識任何一個平 民，任意兩個平民之間是否認識是未知的，請設計一個演算法，快速找個這個人中的那個名人。 已知已經實現了一個函式 bool know(int a,int b) 這個函式返回true的時候，表明a認識b，返回false的時候表明a不認識b。
思路：首先將n個人分為n/2組，每一組有2個人，然後每個組的兩個人呼叫這個know函式， 假設為know(a，b)，返回true的時候說明a認識b，則a肯定不是名人，a可以排除掉了，依次類推，每個組都呼叫這個函式依次，那麼n個人中就有 n/2個人被排除掉了，資料規模將為n/2。同理在剩下的n/2個人中在使用這個方法，那麼規模就會將為n/4，這樣所有的遍歷次數為n/2+n/4+n /8+........ 這個一個等比數列，時間複雜度為o(n)。
