百度 2021 軟件開發高級工程師面試題

第1題：

問答題

數據庫以及線程發生死鎖的原理及必要條件，如何避免死鎖

產生死鎖的原因主要是：

（1） 因為系統資源不足。

（2） 進程運行推進的順序不合適。

（3） 資源分配不當等。

產生死鎖的四個必要條件：

（1）互斥條件：一個資源每次只能被一個進程使用。

（2）請求與保持條件：一個進程因請求資源而阻塞時，對已獲得的資源保持不放。

（3）不剝奪條件:進程已獲得的資源，在末使用完之前，不能強行剝奪。

（4）循環等待條件:若干進程之間形成一種頭尾相接的循環等待資源關系。

第2題：

?面向對象的三個基本元素，五個基本原則

?三個基本元素：

封裝

繼承

多態

五個基本原則：

單一職責原則（Single-Resposibility Principle）:一個類，最好只做一件事，只有一個引起它的變化。單一職責原則可以看做是低耦合、高內聚在面向對象原則上的引申，將職責定義為引起變化的原因，以提高內聚性來減少引起變化的原因。

開放封閉原則（Open-Closed principle）:軟件實體應該是可擴展的，而不可修改的。也就是，對擴展開放，對修改封閉的。

Liskov替換原則（Liskov-Substituion Principle）:子類必須能夠替換其基類。這一思想體現為對繼承機制的約束規范，只有子類能夠替換基類時，才能保證系統在運行期內識別子類，這是保證繼承復用的基礎。

依賴倒置原則（Dependecy-Inversion Principle）:依賴于抽象。具體而言就是高層模塊不依賴于底層模塊，二者都同依賴于抽象；抽象不依賴于具體，具體依賴于抽象。

接口隔離原則（Interface-Segregation Principle）:使用多個小的專門的接口，而不要使用一個大的總接口。

第3題：

?公司里面有1001個員工，現在要在公司里面找到最好的羽毛球選手，也就是第一名，每個人都必須參賽，問至少要比賽多少次才能夠找到最好的羽毛球員工。

?兩兩比賽，分成500組剩下一人，類似于歸并排序的方式，比出冠軍后，讓冠軍之間再比，主要是要想想多余的那一個選手如何處理，必然要在第一次決出冠軍后加入比賽組。

第4題：

?現在有100個燈泡，每個燈泡都是關著的，第一趟把所有的燈泡燈泡打開，第二趟把偶數位的燈泡制反（也就是開了的關掉，關了的打開），第三趟讓第3,6,9....的燈泡制反.......第100趟讓第100個燈泡制反，問經過一百趟以后有多少燈泡亮著。

?1．對于每盞燈，拉動的次數是奇數時，燈就是亮著的，拉動的次數是偶數時，燈就是關著的。
2．每盞燈拉動的次數與它的編號所含約數的個數有關，它的編號有幾個約數，這盞燈就被拉動幾次。
3．1——100這100個數中有哪幾個數，約數的個數是奇數。我們知道一個數的約數都是成對出現的，只有完全平方數約數的個數才是奇數個。 所以這100盞燈中有10盞燈是亮著的。 它們的編號分別是： 1、4、9、16、25、36、49、64、81、100。

第5題：

?有20個數組，每個數組有500個元素，并且是有序排列好的，現在在這20*500個數中找出排名前500的數。

?TOP-K問題，用個數為K的最小堆歸并處理

第6題：

?字符串左移:

?

void *pszStringRotate(char *pszString, intnCharsRotate)

? ?

比如ABCDEFG，移3位變DEFGABC，要求空間復雜度O（1），時間復雜度O（n）。

?翻手算法：

設置有個函數為倒序排列：void Rorder(char *pF,char *pE);

void Rorder(char *pF, char *pE)

{

??? char temp;

??? while (pF <= pE)

??? {

??? ? ? temp = *pF;

??? ? ? *pF = *pE;

??? ? ? *pE = temp;

??? }

}

?

void *pszStringRotate(char *pszString, int nCharsRotate)

{

??? char *pR = pszString;

??? int n = 0;

??? while (pszString + n++ ！ = ‘\n’); //得到字符串長度

??? if (n < nCharsRotate) return pR; //入口參數檢測

?

??? Rorder(pszString, pszString + nCharsRotate ); //C B A

??? pszString = pR;//歸位

??? Rorder( pszString + nCharsRotate, pszString + n - 1); //GFED

??? pszString = pR;

??? Rorder(pszString, pszString + n - 1); //DEFGABC

??? return pR;

}

? ?

大致過程如下：
ABCDEFG
第一步：局部翻轉
ABC DEFG == = 》 CBA GFED
第二步：整體翻轉
CBA GFED ? ?== = 》 DEFGABC

第7題：

?現在有一個手機，手機上的鍵盤上有這樣的對應關系，2對應"abc",3對應"def".....手機里面有一個userlist用戶列表，當我們輸入942的時候出來拼音的對應可能是“xia”，“zha”，“xi”，“yi”等，當我們輸入9264的時候出來是yang，可能是“樣”，“楊”，“往”等，現在我們輸入一個字符串數字，比如926等，要在電話簿userlist中查找出對應的用戶名和電話號碼并返回結果。 C++語言: 電話號碼對應的英語單詞(注意此題的非遞歸做法)

?C++語言: 電話號碼對應的英語單詞(注意此題的非遞歸做法)

?

#include#include#define N 4 //電話號碼個數?

??

using namespace std;

??

char c[][10] = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存儲各個數字所能代表的字符?

int number[N] = {2, 4 ,7, 9}; //存儲電話號碼?

int total[10] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; //各個數組所能代表的字符總數?

int answer[N]; //數字目前所代表的字符在其所能代表的字符集中的位置,初始為0?

??

void Search(int *number, int n); //非遞歸的辦法?

void RecursiveSearch(int *number, int cur, char *ps, int n); //遞歸的辦法

int main()

{

????????//Search(number, N);?

????????char ps[N+1] = {0};

????????RecursiveSearch(number, 0, ps, N);

????????return 0;

}

??

??

void Search(int *number, int n)

{

????????int i;

????????while(1)

????????{

????????????????for(i=0; i= 0)

????????????????{

?

??????????????????????????? if(answer[k] < total[number[k]]-1) { ++answer[k]; break; } else { answer[k] = 0; --k; } } if(k < 0) break; } } /*遞歸的解法: number為存儲電話號碼的數組,pos為當前處理的數字在number中的下標,初始為0 *ps為一外部數組,用于存放字母,n代表電話號碼的長度(個數) * 此遞歸的方法好理解,比上面非遞歸的辦法好寫易懂 * */

?

?

?

?

????

void RecursiveSearch(int *number, int pos, char *ps, int n)


	{


	????????int i;


	????????for(i=0; i

	????????{


	????????????????ps[pos] = c[number[pos]][i];


	????????????????if(pos == n-1)


	????????????????????????cout<

	????????????????else


	????????????????????????RecursiveSearch(number, pos+1, ps, n);


	????????}


	}


	?


	?


	?


	?


	?


	

第8題：

???????? windows內存管理的機制以及優缺點

?分頁存儲管理基本思想：

用戶程序的地址空間被劃分成若干固定大小的區域，稱為“頁”，相應地，內存空間分成若干個物理塊，頁和塊的大小相等?？蓪⒂脩舫绦虻娜我豁摲旁趦却娴娜我粔K中，實現了離散分配。

分段存儲管理基本思想：

將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內存中可以不相鄰接，也實現了離散分配。

段頁式存儲管理基本思想：

分頁系統能有效地提高內存的利用率，而分段系統能反映程序的邏輯結構，便于段的共享與保護，將分頁與分段兩種存儲方式結合起來，就形成了段頁式存儲管理方式。

在段頁式存儲管理系統中，作業的地址空間首先被分成若干個邏輯分段，每段都有自己的段號，然后再將每段分成若干個大小相等的頁。對于主存空間也分成大小相等的頁，主存的分配以頁為單位。

段頁式系統中，作業的地址結構包含三部分的內容：段號 ? ? ?頁號 ? ? ?頁內位移量

程序員按照分段系統的地址結構將地址分為段號與段內位移量，地址變換機構將段內位移量分解為頁號和頁內位移量。

為實現段頁式存儲管理，系統應為每個進程設置一個段表，包括每段的段號，該段的頁表始址和頁表長度。每個段有自己的頁表，記錄段中的每一頁的頁號和存放在主存中的物理塊號。