百度2011.10.16校園招聘會筆試題

一、算法設(shè)計

1、設(shè)rand(s，t)返回[s,t]之間的隨機小數(shù)，利用該函數(shù)在一個半徑為R的圓內(nèi)找隨機n個點，并給出時間復雜度分析。

思路：這個使用數(shù)學中的極坐標來解決，先調(diào)用[s1，t1]隨機產(chǎn)生一個數(shù)r，歸一化后乘以半徑，得到R*(r-s1)/(t1-s1)，然后在調(diào)用[s2，t2]隨機產(chǎn)生一個數(shù)a，歸一化后得到角度：360*(a-s2)/(t2-s2)

2、為分析用戶行為，系統(tǒng)常需存儲用戶的一些query，但因query非常多，故系 統(tǒng)不能全存，設(shè)系統(tǒng)每天只存m個query，現(xiàn)設(shè)計一個算法，對用戶請求的query進行隨機選擇m個，請給一個方案，使得每個query被抽中的概率相 等，并分析之，注意：不到最后一刻，并不知用戶的總請求量。

思路：如果用戶查詢的數(shù)量小于m，那么直接就存起來。 如果用戶查詢的數(shù)量大于m，假設(shè)為m+i，那么在1-----m+i之間隨機產(chǎn)生一個數(shù)，如果選擇的是前面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的相關(guān)問題：

(1)、調(diào)用push_back時，其內(nèi)部的內(nèi)存分配是如何進行的?

(2)、調(diào)用clear時，內(nèi)部是如何具體實現(xiàn)的?若想將其內(nèi)存釋放，該如何操作?

vector的工作原理是系統(tǒng)預(yù)先分配一塊CAPACITY大小的空間，當插入的數(shù)據(jù)超過這個空間的時候，這塊空間會讓某種方式擴展，但是你刪除數(shù)據(jù)的時候，它卻不會縮小。

vector為了防止大量分配連續(xù)內(nèi)存的開銷，保持一塊默認的尺寸的內(nèi)存，clear只是清數(shù)據(jù)了，未清內(nèi)存，因為vector的capacity容量未變化，系統(tǒng)維護一個的默認值。

有什么方法可以釋放掉vector中占用的全部內(nèi)存呢?

標準的解決方法如下

template < class T >

void ClearVector( vector< T >& vt )

{

vector< T > vtTemp;

veTemp.swap( vt );

}

事實上，vector根本就不管內(nèi)存，它只是負責向內(nèi)存管理框架acquire/release內(nèi)存，內(nèi)存管理框架如果發(fā)現(xiàn)內(nèi)存不夠了，就malloc， 但是當vector釋放資源的時候(比如destruct), stl根本就不調(diào)用free以減少內(nèi)存，因為內(nèi)存分配在stl的底層：stl假定如果你需要更多的資源就代表你以后也可能需要這么多資源(你的list, hashmap也是用這些內(nèi)存)，所以就沒必要不停地malloc/free。如果是這個邏輯的話這可能是個trade-off

一般的STL內(nèi)存管理器allocator都是用內(nèi)存池來管理內(nèi)存的，所以某個容器申請內(nèi)存或釋放內(nèi)存都只是影響到內(nèi)存池的剩余內(nèi)存量，而不是真的把內(nèi)存歸還給系統(tǒng)。這樣做一是為了避免內(nèi)存碎片，二是提高了內(nèi)存申請和釋放的效率不用每次都在系統(tǒng)內(nèi)存里尋找一番。

二、系統(tǒng)設(shè)計

正常用戶端每分鐘最多發(fā)一個請求至服務(wù)端，服務(wù)端需做一個異常客戶端行為的過濾系統(tǒng)，設(shè)服務(wù)器在某一刻收到客戶端A的一個請求，則1分鐘內(nèi)的客戶端任何其 它請求都需要被過濾，現(xiàn)知每一客戶端都有一個IPv6地址可作為其ID，客戶端個數(shù)太多，以至于無法全部放到單臺服務(wù)器的內(nèi)存hash表中，現(xiàn)需簡單設(shè)計 一個系統(tǒng)，使用支持高效的過濾，可使用多臺機器，但要求使用的機器越少越好，請將關(guān)鍵的設(shè)計和思想用圖表和代碼表現(xiàn)出來。

三、求一個全排列函數(shù)：

如p([1,2,3])輸出：

[123]、[132]、[213]、[231]、[321]、[323]

求一個組合函數(shù)

如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、輸入一個升序數(shù)組，然后在數(shù)組中快速尋找兩個數(shù)字，其和等于一個給定的值。

這個編程之美上面有這個題目的，很簡單的，用兩個指針一個指向數(shù)組前面，一個指向數(shù)組的后面，遍歷一遍就可以了。

3、有一個名人和很多平民在一塊，平民都認識這個名人，但是這個名人不認識任何一個平 民，任意兩個平民之間是否認識是未知的，請設(shè)計一個算法，快速找個這個人中的那個名人。 已知已經(jīng)實現(xiàn)了一個函數(shù) bool know(int a,int b) 這個函數(shù)返回true的時候，表明a認識b，返回false的時候表明a不認識b。

思路：首先將n個人分為n/2組，每一組有2個人，然后每個組的兩個人調(diào)用這個know函數(shù)， 假設(shè)為know(a，b)，返回true的時候說明a認識b，則a肯定不是名人，a可以排除掉了，依次類推，每個組都調(diào)用這個函數(shù)依次，那么n個人中就有 n/2個人被排除掉了，數(shù)據(jù)規(guī)模將為n/2。同理在剩下的n/2個人中在使用這個方法，那么規(guī)模就會將為n/4，這樣所有的遍歷次數(shù)為n/2+n/4+n /8+........ 這個一個等比數(shù)列，時間復雜度為o(n)。