**一、算法設計** 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都是用內存池來管理內存的，所以某個容器申請內存或釋放內存都只是影響到內存池的剩余內存量，而不是真的把內存歸還給系統。這樣做一是為了避免內存碎片，二是提高了內存申請和釋放的效率——不用每次都在系統內存里尋找一番。 **二、系統設計** 正常用戶端每分鐘最多發一個請求至服務端，服務端需做一個異常客戶端行為的過濾系統，設服務器在某一刻收到客戶端A的一個請求，則1分鐘內的客戶端任何其它請求都需要被過濾，現知每一客戶端都有一個IPv6地址可作為其ID，客戶端個數太多，以至于無法全部放到單臺服務器的內存hash表中，現需簡單設計一個系統，使用支持高效的過濾，可使用多臺機器，但要求使用的機器越少越好，請將關鍵的設計和思想用圖表和代碼表現出來。 **三、求一個全排列函數：** 如p([1,2,3])輸出： [123]、[132]、[213]、[231]、[321]、[312] 求一個組合函數。 方法1：依次從字符串中取出一個字符作為最終排列的第一個字符，對剩余字符組成的字符串生成全排列，最終結果為取出的字符和剩余子串全排列的組合。 ~~~ #include <iostream> #include <string> using namespace std; void permute1(string prefix, string str) { if(str.length() == 0) cout << prefix << endl; else { for(int i = 0; i < str.length(); i++) permute1(prefix+str[i], str.substr(0,i)+str.substr(i+1,str.length())); } } void permute1(string s) { permute1("",s); } int main(void) { //method1, unable to remove duplicate permutations. permute1("abc"); return 0; } ~~~ 優點：該方法易于理解，但無法移除重復的排列，如：s="ABA"，會生成兩個“AAB”。 方法2：利用交換的思想，具體見實例，但該方法不如方法1容易理解。  我們以三個字符abc為例來分析一下求字符串排列的過程。首先我們固定第一個字符a，求后面兩個字符bc的排列。當兩個字符bc的排列求好之后，我們把第一個字符a和后面的b交換，得到bac，接著我們固定第一個字符b，求后面兩個字符ac的排列。現在是把c放到第一位置的時候了。記住前面我們已經把原先的第一個字符a和后面的b做了交換，為了保證這次c仍然是和原先處在第一位置的a交換，我們在拿c和第一個字符交換之前，先要把b和a交換回來。在交換b和a之后，再拿c和處在第一位置的a進行交換，得到cba。我們再次固定第一個字符c，求后面兩個字符b、a的排列。 既然我們已經知道怎么求三個字符的排列，那么固定第一個字符之后求后面兩個字符的排列，就是典型的遞歸思路了。 基于前面的分析，我們可以得到如下的參考代碼： ~~~ void Permutation(char* pStr, char* pBegin) { assert(pStr && pBegin); //if(!pStr || !pBegin) //return ; if(*pBegin == '\0') printf("%s\n",pStr); else { char temp; for(char* pCh = pBegin; *pCh != '\0'; pCh++) { if(pCh != pBegin && *pCh == *pBegin) //為避免生成重復排列，當不同位置的字符相同時不再交換 continue; temp = *pCh; *pCh = *pBegin; *pBegin = temp; Permutation(pStr, pBegin+1); temp = *pCh; *pCh = *pBegin; *pBegin = temp; } } } int main(void) { char str[] = "aba"; Permutation(str,str); return 0; } ~~~ 如p([1,2,3])輸出： [1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3] 這兩問可以用偽代碼。