百度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)。
相關文章
-
2016平安銀行校園招聘筆試
法院工作效率的提高來自管理和決策水平的提高,而高水平的管理和戰略決策都離不開快速、準確、豐富的信息。下面是本站小編整理的一些關於法院公務員轉正工作總結,供您參考。法院公務員轉正工作總結範文一為了便於局領導 -
關於農行2010校園招聘筆試類別問題
本人申請的是農行天津分行的職位,在已申請職位狀態中顯示報名成功,目前還沒準考號。但在簡歷預覽中只顯示個人編號與志願,筆試類別後面為空。請問這樣算不算已報名成功。 -
「09校園招聘」百度筆試題
【10.13技術筆經】第一題:簡要説明樹的深度優先、廣度優先遍歷算法的特點第二題:一個複數相加的編碼挑錯題 。程序如下:1 typedef {2 int num;3 int imag;4 }Complex_t;56 int alloc(Complext_t * a,int num){7 a=new Co -
百度校園招聘會工程師筆試題
一,簡答題(30分)1,當前計算機系統一般會採用層次結構存儲數據,請介紹下典型計算機存儲系統一般分為哪幾個層次,為什麼採用分層存儲數據能有效提高程序的執行效率?10分2,Unix/Linux系統中殭屍進程是如何產生的?有什麼危害? -
近期最新校園招聘會安排(11月27日上午10:00發佈)
1、重慶市渝北區教育委員會將於11月28日(週日)上午9:00在我校大學生活動中心403舉行校園招聘宣講會!2、黑龍江省大慶市肇州二中將於11月28日(週日)上午9:00在我校理科教學樓9103教室舉行校園招聘宣講會!3、廣東省惠州 -
2017百度銷售體系管理培訓生校園招聘
世界那麼大,大牛那麼多少年,從優秀到卓越你需要最好的同行者走得越遠,只會離自己越近而夢想,也會變得更大百度搜索校招季遇見壹百分的自己我們的使命 讓人們最平等便捷地獲取信息,找到所求我們的核心價值觀 簡單可依賴我們 -
阿爾卡特朗訊(青島)2015校園招聘筆試題
阿爾卡特朗訊(青島)2015書面考試在海洋大學參加完書面考試,考場的人真是多,小400號人,考完以後由於收到了別的公司的offer,以後就沒管朗訊的了。如今有時間在這裏分享一下書面考試題,期望對來年有意向的師弟師妹們有協助。 -
百度校園招聘筆試題
一:簡答題(30)1:數據庫以及線程發生死鎖的原理及必要條件,如何避免死鎖(操作系統書上有)2:面向對象的三個基本元素,五個基本原則(繼承,封裝,多態,基本原則沒答上)3:windows內存管理的機制以及優缺點(分頁,分段,虛擬內存管理. -
奇虎360今晚(11月19號)是否有校園招聘宣講會?
360校園宣講會行程安排上寫的.是今晚19:00-21:00到清水河校區開宣講會,但是上次在南京的宣講會就取消了,想問下今晚是否有? -
2012.12.6 廣中醫醫藥專場校園招聘會
第二次去校園招聘會,去年,和軒軒去了城市職業學院的時候,我們還是隻是去看看,去領略,感歎着。。。 我們508的幾個都寄居於510,像是入侵了她們的宿舍,爺直接到醫院去了,把牀讓給了軒軒;小穎穎直接就呆家了,這樣的好處是我可以舒