2021年百度公司大數據云計算研發面試題

小編:管理員 497閱讀 2021.06.15

第1題:


請簡要描述一下Hadoop, Spark, MPI三種計算框架的特點以及分別適用于什么樣的場景



a)     Hadoop
基于分布式文件系統HDFS的分布式批處理計算框架。適用于數據量大,SPMD(單程序多數據)的應用。
b)     Spark
基于內存計算的并行計算框架。適用于需要迭代多輪計算的應用。
c)      MPI
基于消息傳遞的并行計算框架。適用各種復雜應用的并行計算。支持MPMD( 多程序多數據) ,開發復雜度高


第2題:


請解釋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,不參與連接建立的過程。



第3題:


給定一個整數的數組,相鄰的數不能同時選,求從該數組選取若干整數,使得他們的和最大,要求只能使用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;
}


第4題:


二分查找是常用的編程方法,請用完整代碼實現該函數(不許調用庫函數)
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;
}



第5題:


有編號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)的時間復雜度解決該問題。 



第6題:


打長沙麻將在一開始,只有莊家可得到十四張牌,其余的人十三張,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(牌出現的次數)



關聯標簽:
最近中文字幕2018_最近中文字幕完整版2019_最近更新中文字幕第1