一、算法設計
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;
veTemp.swap( vt );
}
事實上，vector根本就不管內存，它只是負責向內存管理框架acquire/release內存，內存管理框架如果發現內存不夠了，就malloc，但是當vector釋放資源的時候(比如destruct), stl根本就不調用free以減少內存，因為內存分配在stl的底層：stl假定如果你需要更多的資源就代表你以後也可能需要這麼多資源(你的list, hashmap也是用這些內存)，所以就沒必要不停地malloc/free。如果是這個邏輯的話這可能是個trade-off
一般的STL內存管理器allocator都是用內存池來管理內存的，所以某個容器申請內存或釋放內存都只是影響到內存池的剩余內存量，而不是真的把內存歸還給系統。這樣做一是為了避免內存碎片，二是提高了內存申請和釋放的效率——不用每次都在系統內存裡尋找一番。
