2021年百度公司大數據云計算研發面試題
小編:管理員 497閱讀 2021.06.15
請簡要描述一下Hadoop, Spark, MPI三種計算框架的特點以及分別適用于什么樣的場景
a) Hadoop
基于分布式文件系統HDFS的分布式批處理計算框架。適用于數據量大,SPMD(單程序多數據)的應用。
b) Spark
基于內存計算的并行計算框架。適用于需要迭代多輪計算的應用。
c) MPI
基于消息傳遞的并行計算框架。適用各種復雜應用的并行計算。支持MPMD( 多程序多數據) ,開發復雜度高
請解釋tcp連接建立過程,如果可能,請結合相應系統調用函數解釋交互過程。
第一次握手:建立連接時,客戶端調用發送syn包(syn=j)到服務器,并進入SYN_SEND狀態,等待服務器確認;
第二次握手:服務器端收到syn包,必須確認客戶的SYN(ack=j+1),同時自己也發送一個SYN包(syn=k),即SYN+ACK包,此時服務器進入SYN_RECV狀態;
第三次握手:客戶端收到服務器的SYN+ACK包,向服務器發送確認包ACK(ack=k+1),此包發送完畢,客戶端和服務器進入ESTABLISHED狀態,完成三次握手。
完成三次握手,客戶端與服務器開始傳送數據;
相關系統調用:client端調用connect()開始建立連接,連接建立好后退出
服務器端調用完listen()后就可以響應連接請求,連接請求建立好后調用accept()把連接拿出開始通信
注意:accept()跟server建立連接沒有關系,它只是取出建立好連接的socket,不參與連接建立的過程。
給定一個整數的數組,相鄰的數不能同時選,求從該數組選取若干整數,使得他們的和最大,要求只能使用o(1)的空間復雜度。要求給出偽碼。
int getMax(int a[],int len)
{
int max1 = a[0];//表示maxSum(n-2);
int max2 = a[0]>a[1]? a[0]:a[1]; //表示maxSum(n-1);
int max3 = 0; // n
for(int i =2; i<len; i++){
max3 = Max(a[i],Max(max1+a[i],max2));
// max3 = a[i]+max1> max2 ? a[i]+max1:max2; // 全部是負數也需要考慮的,這個沒有
max1 = max2;
max2 = max3;
}
return max3;
}
int Max(int a,int b){
if(a>b)
return a;else
return b;
}
二分查找是常用的編程方法,請用完整代碼實現該函數(不許調用庫函數)
void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*compar) (const void *, const void *));
二分查找完整代碼:
#include<iostream>
using namespace std;
void * bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)){
void *mid = NULL;
int sign;
while (nel > 0) {
mid = (char *)base + width*(nel/2);
sign = cmp(key, mid);
if (sign == 0) return mid;//找到
if (nel == 1) break;
else if (sign < 0)
nel /= 2;//下取整
else {
base = mid;
nel -= nel/2;//上取整
}
}
return NULL;
}
int compare(const void *val1, const void *val2) {
int iVal1 = *(int*)val1;
int iVal2 = *(int*)val2;
if (iVal1 > iVal2) {
return 1;
}
else if (iVal1 == iVal2) {
return 0;
}
return -1;
}
測試用例:
int main(){
int a[10]={1, 2, 5, 8, 10, 11,12,13,14,15};
int key = 5;
void* res = bsearch(&key, a, 10, sizeof(int), compare);
if(res != NULL){
cout << "索引位置:" << (int *)res - a;
}
return 0;
}
有編號1~100個燈泡,起初所有的燈都是滅的。有100個同學來按燈泡開關,如果燈是亮的,那么按過開關之后,燈會滅掉。如果燈是滅的,按過開關之后燈會亮。
現在開始按開關。
第1個同學,把所有的燈泡開關都按一次(按開關燈的編號: 1,2,3,......100)。
第2個同學,隔一個燈按一次(按開關燈的編號: 2,4,6,......,100)。
第3個同學,隔兩個燈按一次(按開關燈的編號: 3,6,9,......,99)。
......
問題是,在第100個同學按過之后,有多少盞燈是亮著的?這些燈的編號是多少?要求給出解題思路或給出偽碼。
10盞,1,4,9,16,25,36,49,64,81,100
按照同學來看,每個同學只會按是自己的倍數的燈。
那么我們轉換成燈來看的話,每個燈只會被是自己的因子的同學按。
那么一個初始化為滅的燈,如何最后變成一盞亮的燈呢?
很明顯,只有它有奇數個因子的時候,才有可能。
那么什么時候一個數可以有奇數個因子呢?
對于任意一個數N ,都可以分解成 N = a * b的乘積,即任意一個數都可以分解成 M個(a * b) 的乘積。
所以若想滿足存在奇數個因子,a 必須等于 b.
即 N = a2,所以只有平方數最后才滿足要求,故可以在0(n)的時間復雜度解決該問題。
打長沙麻將在一開始,只有莊家可得到十四張牌,其余的人十三張,F在莊家手里拿到十四張牌,他想請你寫個程序幫忙判斷一下,莊家是否已經胡牌。
如果你會打麻將,請忽略以下背景,如果不會,簡單了解一下背景有助于理解本題:
長沙麻將打法簡單、節奏快速,極易胡牌。長沙麻將共一百零八張牌:包括筒、索、萬;不帶東、南、西、北風、中、發、白。:
1、萬子牌:從一萬至九萬,各4張,共36張。
2、筒子牌:從一筒至九筒,各4張,共36張。也有的地方稱為餅,從一餅到九餅。
3、束子牌:從一束至九束,各4張,共36張。也有的地方稱為條,從一條到九條。
組牌規則:
1,對子:兩張一樣花色,一樣大小的牌,組成對子。
2,順子:三張相同花色,連續的牌,組成順子。
3,刻子:三張一樣花色,一樣大小的牌,組成刻子。
胡牌規則:每人有十四張牌,如果這十四張牌可以組成:一個對子,若干個順子和刻子,則表示胡牌。比如以下牌型已經胡牌:
一萬,一萬,二萬,三萬,四萬,二條,三條,四條,四條,四條,四條,五筒,六筒,七筒。
1:請描述你對這個問題的理解,并寫出你的解題思路。
1.1, 按花色細分處理,必須是一個花色的牌個數 3的倍數余2(留對子),其它花色的個數都是3的倍數。否則不能胡牌
1.2, 從3的倍數余2的花色中選出一對,剩下的牌的處理和其它花色一樣。如果沒有對子,則不能胡牌。
1.3, 對于某一個花色的牌,由于個數為3的倍數,判斷其是否可以組成若干個順子或刻子,否則不能胡牌。
1.4, 對相同花色的牌進行排序和計數,判斷第一張牌能否和其它牌組成順子或刻子,若不能,則回溯。若能,由繼續處理剩下的牌。
1.5, 最后判斷是否可以胡牌
2.請設計解決問題需要的數據結構。
需要設計一個花色的數據結構,包括type(花色), id(牌的大。,count(牌出現的次數)
相關推薦
- 百度 2021 商業市場調研面試題 第1題: 關于屌絲的購物習慣和潛在購物需求的研究:第2題: 網購習慣和潛在需求調研第3題: 你媽是個廣場舞愛好者,喜歡收集教學視頻,要你買個移動硬盤,你說云端硬盤比較好,像你媽簡述云端硬盤的概念以及優勢第4題: 百度要開發高校版百度地圖,設計核心功…
- 百度 2021 硬件開發面試題 第1題: 阻塞與非阻塞區別第2題: 畫出D觸發器結構,解釋建立時間和保持時間第3題: 名詞解釋:SIMD、VLIM第4題: CPU的5級流水是什么?流水線優缺點?第5題: 1——16循環計數器,用Verilog或VHDL第6題: SRAM設計FIFO,不要求程序,給出結構圖及設計思路第7題…
- 2021年蜂鳥眾包回爐考試題大全,附上答案 想做蜂鳥眾包外賣員的朋友,在入職之前一定有面臨著這樣的問題,那就是面試官叫你考試。而在掃描之后,面對眾包回爐考試的題目時,你可能會頓時蒙圈,也許考了幾天了,就是過不了。為此,小編為你送上2021年眾包回爐考試大全25道題以及真實答案,以下就是:湛江…