百度2011.10.16校園招聘會(huì)筆試題

一、算法設(shè)計(jì)

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

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

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

思路：如果用戶查詢的數(shù)量小于m，那么直接就存起來。 如果用戶查詢的數(shù)量大于m，假設(shè)為m+i，那么在1-----m+i之間隨機(jī)產(chǎn)生一個(gè)數(shù)，如果選擇的是前面m條查詢進(jìn)行存取，那么概率為m/(m+i)， 如果選擇的是后面i條記錄中的查詢，那么用這個(gè)記錄來替換前面m條查詢記錄的概率為m/(m+i)*(1-1/m)=(m-1)/(m+i)，當(dāng)查詢記錄 量很大的時(shí)候，m/(m+i)== (m-1)/(m+i)，所以每個(gè)query被抽中的概率是相等的。

3、C++ STL中vector的相關(guān)問題：

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

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

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

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

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

標(biāo)準(zhǔn)的解決方法如下

template < class T >

void ClearVector( vector< T >& vt )

{

vector< T > vtTemp;

veTemp.swap( vt );

}

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

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

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

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

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

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

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

求一個(gè)組合函數(shù)

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

[1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3]

這兩問可以用偽代碼。

1、進(jìn)程切換需要注意哪些問題?

保存處理器PC寄存器的值到被中止進(jìn)程的私有堆棧; 保存處理器PSW寄存器的值到被中止進(jìn)程的私有堆棧; 保存處理器SP寄存器的值到被中止進(jìn)程的進(jìn)程控制塊;

保存處理器其他寄存器的值到被中止進(jìn)程的私有堆棧; 自待運(yùn)行進(jìn)程的進(jìn)程控制塊取SP值并存入處理器的寄存器SP; 自待運(yùn)行進(jìn)程的私有堆棧恢復(fù)處理器各寄存器的值;

自待運(yùn)行進(jìn)程的私有堆棧中彈出PSW值并送入處理器的PSW; 自待運(yùn)行進(jìn)程的私有堆棧中彈出PC值并送入處理器的PC。

2、輸入一個(gè)升序數(shù)組，然后在數(shù)組中快速尋找兩個(gè)數(shù)字，其和等于一個(gè)給定的值。

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

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

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