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

請簡要描述一下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（牌出現的次數）