2021年百度公司測試開發面試題

C++STL中Vector相關問題

（1）調用成員函數push_back，其內部內存分配如何進行。

（2）調用成員函數clear時，內部如何具體實現，若想將其內存釋放，該如何操作。

指出C語言foo函數的問題，此函數想統計字符串中的字母a~z分別出現的個數。
void foo(char a[100],int cnt[256]){
? ?? ? memset(cnt,0,izeof(cnt));
? ?? ? while(*a !='\0'){
? ?? ?? ?? ?++cnt[*a];
? ?? ?? ?? ?++a;
? ?? ?? ?? ??}
? ?? ???for(char c='a';c<='z';++c){
? ?? ?? ?? ? printf("%c:%d\n",c,cnt[c]);
? ?? ?? ?? ?}
??}
int main(){
? ?? ?char a[100]="百度abc"
? ?? ?int cnt[256];
? ?? ?foo(a,cnt);
? ?? ?return 0;
}

算法與程序設計：

設有rand(s,t)函數，可返回(s,t)間的隨機小數，如何利用該函數在一個半徑為R的圓內隨機找n個點，并給出相應的時間復雜度的分析。

算法與程序設計：

為了分析用戶行為，系統往往需存儲用戶的一些query。但是因為query非常多，所以系統不能存下每一條。設系統每天只能存儲m個query，現需設計一個算法，對用戶時時請求的query進行隨機選擇n個，給出一個方案使得每一個query被抽中的概率盡量相等，也請附加相應分析，請注意，不到最后一刻，你并不知道用戶的總請求量是多少。

系統設計題：

現有一個“服務器—客戶端”的實際系統，正?？蛻舳嗣恳环昼娮疃喟l送一條請求到服務器，服務器需要做一個異?？蛻舳诵袨榈倪^濾系統。設服務器在某一時刻收到A的一條請求，那么一分鐘內的客戶端的任何其他請求都要被過濾，現知每一個客戶端都有一個IPV6地址可以作為其ID，客戶端個數太多，以至于無法全部放到單臺服務器的內存hash表中，現需要設計一套系統，使得支持高效過濾，可以使用多臺機器，但要求使用機器越少越好，請把關鍵設計和思想用圖表和代碼方式表現出來。