百度 2022 軟件工程師面試題（求職面試回答資料）

1、 百度 2022 軟件工程師面試題第1題： 問(wèn)答題 動(dòng)態(tài)鏈接庫(kù)和靜態(tài)鏈接庫(kù)的優(yōu)缺點(diǎn) 解答：（1）動(dòng)態(tài)鏈接庫(kù)(Dynamic Linked Library)：Windows為應(yīng)用程序供應(yīng)了豐富的函數(shù)調(diào)用，這些函數(shù)調(diào)用都包含在動(dòng)態(tài)鏈接庫(kù)中。其中有3個(gè)最重要的DLL，Kernel32.dll、User32.dll和GDI32.dll。有兩種使用方式：一種是靜態(tài)加載，即在應(yīng)用程序啟動(dòng)時(shí)被加載；一種是動(dòng)態(tài)加載，即是該動(dòng)態(tài)鏈接庫(kù)在被使用時(shí)才被應(yīng)用程序加載。優(yōu)點(diǎn)如下： a. 共享：多個(gè)應(yīng)用程序可以使用同一個(gè)動(dòng)態(tài)庫(kù)，啟動(dòng)多個(gè)應(yīng)用程序的時(shí)候，只需要將動(dòng)態(tài)庫(kù)加載到內(nèi)存一次即可； b. 開發(fā)模塊好：要求設(shè)計(jì)者對(duì)功能

2、劃分的比較好。 缺點(diǎn)是不能解決引用計(jì)數(shù)等問(wèn)題。 （2）靜態(tài)庫(kù)(Static Library)：函數(shù)和數(shù)據(jù)被編譯進(jìn)一個(gè)二進(jìn)制文件(通常擴(kuò)展名為.LIB)。在使用靜態(tài)庫(kù)的狀況下，在編譯鏈接可執(zhí)行文件時(shí)，鏈接器從庫(kù)中復(fù)制這些函數(shù)和數(shù)據(jù)并把它們和應(yīng)用程序的其它模塊組合起來(lái)創(chuàng)建最終的可執(zhí)行文件(.EXE文件)。靜態(tài)鏈接庫(kù)作為代碼的一部分，在編譯時(shí)被鏈接。優(yōu)缺點(diǎn)如下： 代碼的裝載速度快，由于編譯時(shí)它只會(huì)把你需要的那部分鏈接進(jìn)去，應(yīng)用程序相對(duì)比較大。但是假如多個(gè)應(yīng)用程序使用的話，會(huì)被裝載多次，鋪張內(nèi)存。 第2題： 列出數(shù)據(jù)庫(kù)中常用的鎖及其應(yīng)用場(chǎng)景 解答：數(shù)據(jù)庫(kù)中的鎖是網(wǎng)絡(luò)數(shù)據(jù)庫(kù)中的一個(gè)特別重要的概念，它主要

3、用于多用戶環(huán)境下保證數(shù)據(jù)庫(kù)完整性和全都性。各種大型數(shù)據(jù)庫(kù)所采納的鎖的基本理論是全都的，但在詳細(xì)實(shí)現(xiàn)上各有差別。目前，大多數(shù)數(shù)據(jù)庫(kù)管理系統(tǒng)都或多或少具有自我調(diào)整、自我管理的功能，因此許多用戶實(shí)際上不 清晰鎖的理論和所用數(shù)據(jù)庫(kù)中鎖的詳細(xì)實(shí)現(xiàn)。在數(shù)據(jù)庫(kù)中加鎖時(shí)，除了可以對(duì)不同的資源加鎖，還可以使用不同程度的加鎖方式，即鎖有多種模式，SQL Server中鎖模式包括： 1）共享鎖 SQL Server中，共享鎖用于全部的只讀數(shù)據(jù)操作。共享鎖是非獨(dú)占的，允很多個(gè)并發(fā)事務(wù)讀取其鎖定的資源。默認(rèn)狀況下，數(shù)據(jù)被讀取后，SQL Server馬上釋放共享鎖。例如，執(zhí)行查詢“SELECT * FROM my_tab

4、le”時(shí)，首先鎖定第一頁(yè)，讀取之后，釋放對(duì)第一頁(yè)的鎖定，然后鎖定其次頁(yè)。這樣，就允許在讀操作過(guò)程中，修改未被鎖定的第一頁(yè)。但是，事務(wù) 隔離級(jí)別連接選項(xiàng)設(shè)置和SELECT語(yǔ)句中的鎖定設(shè)置都可以轉(zhuǎn)變SQL Server的這種默認(rèn)設(shè)置。例如，“ SELECT * FROM my_table HOLDLOCK”就要求在整個(gè)查詢過(guò)程中，保持對(duì)表的鎖定，直到查詢完成才釋放鎖定。 2）修改鎖 修 改鎖在修改操作的初始化階段用來(lái)鎖定可能要被修改的資源，這樣可以避開使用共享鎖造成的死鎖現(xiàn)象。由于使用共享鎖時(shí)，修改數(shù)據(jù)的操作分為兩步，首先獲得一 個(gè)共享鎖，讀取數(shù)據(jù)，然后將共享鎖升級(jí)為獨(dú)占鎖，然后再執(zhí)行修改操作。這

5、樣假如同時(shí)有兩個(gè)或多個(gè)事務(wù)同時(shí)對(duì)一個(gè)事務(wù)申請(qǐng)了共享鎖，在修改數(shù)據(jù)的時(shí)候，這些 事務(wù)都要將共享鎖升級(jí)為獨(dú)占鎖。這時(shí)，這些事務(wù)都不會(huì)釋放共享鎖而是始終等待對(duì)方釋放，這樣就造成了死鎖。假如一個(gè)數(shù)據(jù)在修改前直接申請(qǐng)修改鎖，在數(shù)據(jù)修 改的時(shí)候再升級(jí)為獨(dú)占鎖，就可以避開死鎖。修改鎖與共享鎖是兼容的，也就是說(shuō)一個(gè)資源用共享鎖鎖定后，允許再用修改鎖鎖定。 3）獨(dú)占鎖 獨(dú)占鎖是為修改數(shù)據(jù)而保留的。它所鎖定的資源，其他事務(wù)不能讀取也不能修改。獨(dú)占鎖不能和其他鎖兼容。 4）結(jié)構(gòu)鎖 結(jié)構(gòu)鎖分為結(jié)構(gòu)修改鎖（Sch-M）和結(jié)構(gòu)穩(wěn)定鎖（Sch-S）。執(zhí)行表定義語(yǔ)言操作時(shí)，SQL Server采納Sch-M鎖，編譯查詢時(shí)，S

6、QL Server采納Sch-S鎖。 5）意向鎖 意 向鎖說(shuō)明SQL Server有在資源的低層獲得共享鎖或獨(dú)占鎖的意向。例如，表級(jí)的共享意向鎖說(shuō)明事務(wù)意圖將獨(dú)占鎖釋放到表中的頁(yè)或者行。意向鎖又可以分為共享意向鎖、 獨(dú)占意向鎖和共享式獨(dú)占意向鎖。共享意向鎖說(shuō)明事務(wù)意圖在共享意向鎖所鎖定的低層資源上放置共享鎖來(lái)讀取數(shù)據(jù)。獨(dú)占意向鎖說(shuō)明事務(wù)意圖在共享意向鎖所鎖定 的低層資源上放置獨(dú)占鎖來(lái)修改數(shù)據(jù)。共享式獨(dú)占鎖說(shuō)明事務(wù)允許其他事務(wù)使用共享鎖來(lái)讀取頂層資源，并意圖在該資源低層上放置獨(dú)占鎖。 6）批量修改鎖 批量復(fù)制數(shù)據(jù)時(shí)使用批量修改鎖?？梢酝ㄟ^(guò)表的TabLock提示或者使用系統(tǒng)存儲(chǔ)過(guò)程sp_table

7、option的“table lock on bulk load”選項(xiàng)設(shè)定批量修改鎖。 第3題： 給定N是一個(gè)正整數(shù)，求比N大的最小“不重復(fù)數(shù)”，這里的不重復(fù)是指沒有兩個(gè)相等的相鄰位，如1102中的11是相等的兩個(gè)相鄰位故不是不重復(fù)數(shù)，而12301是不重復(fù)數(shù)。 算法思想：當(dāng)然最直接的方法是采納暴力法，從N+1開頭逐步加1推斷是否是不重復(fù)數(shù)，是就退出循環(huán)輸出，這種方法一般是不行取的，例如N=11000000，你要一個(gè)個(gè)的加1要加到12022101，一共循環(huán)百萬(wàn)次，每次都要重復(fù)推斷是否是不重復(fù)數(shù)，效率極其低下，因此是不行取的。這里我采納的方法是：從N+1的最高位往右開頭推斷與其次高位是否相等，假如發(fā)

8、覺相等的（即為重復(fù)數(shù)）則將次高位加1，留意這里可能進(jìn)位，如89219021，后面的直接置為010101.形式，如11211201，此時(shí)便完成“不重復(fù)數(shù)”的初步構(gòu)造，但此時(shí)的“不重復(fù)數(shù)”不肯定是真正的不重復(fù)的數(shù)，由于可能進(jìn)位后的次高位變?yōu)?或進(jìn)位后變成00，如992110001，此時(shí)需要再次循環(huán)推斷重新構(gòu)造直至滿意條件即可，這種方法循環(huán)的次數(shù)比較少，可以接受。 SourceCode： / 求比指定數(shù)大且最小的“不重復(fù)數(shù)” #include stdio.hvoid minNotRep(int n) / 需要多次推斷 while(1) int a20, len = 0, i, b = 0; / fl

9、ag為true表示是“重復(fù)數(shù)”，為false表示表示是“不重復(fù)數(shù)” bool flag = false; / 將n的各位上數(shù)字存到數(shù)組a中 while(n) alen+ = n % 10; n = n / 10; / 從高位開頭遍歷是否有重復(fù)位 for(i = len - 1; i 0; i-) / 有重復(fù)位則次高位加1（最高位有可能進(jìn)位但這里不需要額外處理） if(ai = ai - 1 !flag) ai - 1+; flag = true; else if(flag) / 將重復(fù)位后面的位置為0101.形式 ai - 1 = b; b = (b = 0) ? 1 : 0; / 重組各位數(shù)

10、字為n，假如是“不重復(fù)數(shù)”則輸出退出否則連續(xù)推斷 for(i = len - 1; i = 0; i-) n = n * 10 + ai; if(!flag) printf(%dn, n); break; int main() int N; while(scanf(%d, N) minNotRep(N + 1); return 0; /stdio.h 第4題： 輪詢?nèi)蝿?wù)調(diào)度和可搶占式調(diào)度有什么區(qū)分？ 解答：（1）輪詢調(diào)度的原理是每一次把來(lái)自用戶的懇求輪番安排給內(nèi)部中的服務(wù)器，從1開頭，直到N(內(nèi)部服務(wù)器個(gè)數(shù))，然后重新開頭循環(huán)。只有在當(dāng)前任務(wù)主動(dòng)放棄CPU掌握權(quán)的狀況下（比如任務(wù)掛起），才允許

11、其他任務(wù)（包括高優(yōu)先級(jí)的任務(wù)）掌握CPU。其優(yōu)點(diǎn)是其簡(jiǎn)潔性，它無(wú)需記錄當(dāng)前全部連接的狀態(tài)，所以它是一種無(wú)狀態(tài)調(diào)度。但不利于后面的懇求準(zhǔn)時(shí)得到響應(yīng)。 （2）搶占式調(diào)度允許高優(yōu)先級(jí)的任務(wù)打斷當(dāng)前執(zhí)行的任務(wù)，搶占CPU的掌握權(quán)。這有利于后面的高優(yōu)先級(jí)的任務(wù)也能準(zhǔn)時(shí)得到響應(yīng)。但實(shí)現(xiàn)相對(duì)較簡(jiǎn)單且可能消失低優(yōu)先級(jí)的任務(wù)長(zhǎng)期得不到調(diào)度。 第5題： 設(shè)N是一個(gè)大整數(shù)，求長(zhǎng)度為N的字符串的最長(zhǎng)回文子串。 算法1：第一個(gè)方法當(dāng)然是暴力法，外面的兩層循環(huán)找到全部子串，第三層循環(huán)推斷子串是否是回文。方法的時(shí)間簡(jiǎn)單度為O(n3)，空間簡(jiǎn)單度為O(1)。 算法2：采納動(dòng)態(tài)規(guī)劃法推斷子串是否是回文。開拓一個(gè)Pij用來(lái)表示s

12、tri.j是否為回文，Pij的狀態(tài)轉(zhuǎn)移方程如下： 當(dāng)i=j時(shí)，Pij=true 當(dāng)i+1=j時(shí)，Pij=stri=strj 其他，Pij=Pi+1j-1(stri=strj) 那么Pij中j-i+1最大的且值為true的就是最長(zhǎng)回文子串。這樣，這個(gè)方法的時(shí)間簡(jiǎn)單度為O(n2)，空間簡(jiǎn)單度為O(n2)。比暴力法有很大的改進(jìn)。 Source Code： #include stdio.h #include stdlib.h #include string.h int longestPalSubstr(char *str) int n = strlen(str); int i, j, len, max

13、len = 0, maxi = 0, maxj = 0; bool *P = (bool*)malloc(sizeof(bool) * n); for(i = 0; i n; i+) Pi = (bool*)malloc(sizeof(bool) * n); / initialize Pii for(i = 0; i n; i+) Pii = true; / compute Pnn by length for(len = 2; len = n; len+) for(i = 0; i n - len + 1; i+) j = i + len - 1; if(len = 2) Pij = (str

14、i = strj); else Pij = (stri = strj) Pi + 1j - 1); for(i = 0; i n; i+) for(j = i; j n; j+) if(Pij maxlen (j - i + 1) maxlen = j - i + 1; maxi = i; maxj = j; printf(The longest palin substr is ); for(i = maxi; i = maxj; i+) printf(%c, stri); printf(, maxlen is %dnn, maxlen); return maxlen; int main()

15、char str100; while(1) gets(str); if(strlen(str) = 0) break; longestPalSubstr(str); return 0; 算法3：第三個(gè)方法，可以從上面那個(gè)方法的狀態(tài)轉(zhuǎn)移方程獲得啟發(fā)，對(duì)于每一個(gè)回文子串可以先確定一個(gè)中心，然后向兩邊擴(kuò)展，這樣可以在時(shí)間簡(jiǎn)單度O(n2)，空間簡(jiǎn)單度O(1)的狀況下完成，需要留意的是，長(zhǎng)度為奇數(shù)和偶數(shù)的中心的狀況是不同的。 Source Code： #include stdio.h #include stdlib.h #include string.h int longestPalSubstr(cha

16、r *str) int len = strlen(str); int i, maxLen = 1, start = 0; int low, high; / 將每個(gè)字符作為中心向兩邊擴(kuò)展推斷 for(i = 1; i len; i+) / 處理長(zhǎng)度為偶數(shù)的狀況 low = i - 1; high = i; while(low = 0 high len strlow = strhigh) if(maxLen high - low + 1) start = low; maxLen = high - low + 1; low-; high+; / 處理長(zhǎng)度為奇數(shù)的狀況 low = i - 1; hig

17、h = i + 1; while(low = 0 high len strlow = strhigh) if(maxLen high - low + 1) start = low; maxLen = high - low + 1; low-; high+; printf(The longest palin substr is ); for(i = start; i start + maxLen; i+) printf(%c, stri); printf(, maxlen is %dnn, maxLen); return maxLen; int main() char str100; while

18、(1) gets(str); if(strlen(str) = 0) break; longestPalSubstr(str); return 0; 算法4：第四個(gè)方法采納后綴數(shù)組，將最長(zhǎng)回文子串的問(wèn)題轉(zhuǎn)化為最長(zhǎng)公共前綴的問(wèn)題。詳細(xì)的做法就是：將整個(gè)字符串翻轉(zhuǎn)之后，拼接到原字符串后，留意用特別字 符分開，這樣問(wèn)題就變成了新的字符串的某兩個(gè)后綴的最長(zhǎng)公共前綴的問(wèn)題了。這個(gè)方法比較強(qiáng)大，許多字符串的問(wèn)題都能夠奇妙的解決。不過(guò)實(shí)現(xiàn)起來(lái)也相對(duì)比較:難，好的實(shí)現(xiàn)和差的實(shí)現(xiàn)時(shí)間簡(jiǎn)單度相差很大。由于對(duì)后綴數(shù)組不是很清晰，未寫代碼，等學(xué)習(xí)了后綴數(shù)組再過(guò)來(lái)補(bǔ)。 算法5：第五個(gè)方法叫做Manacher算法，是一種

19、線性時(shí)間的方法，特別奇妙。首先，我們?cè)谏厦娴姆椒ㄖ袀€(gè)，都要考慮回文長(zhǎng)度為奇數(shù)或者偶數(shù)的狀況。這個(gè):方法，引入一個(gè)技巧，使得奇數(shù)和偶數(shù)的狀況統(tǒng)一處理了。詳細(xì)做法如下： abba轉(zhuǎn)換為#a#b#b#a#，也就是在每一個(gè)字符兩邊都加上一個(gè)特別字符。 然后創(chuàng)建一個(gè)新的Pi表示，以第i個(gè)字符為中心的回文字串的半徑。 例如上面的例子，對(duì)應(yīng)的P如下,設(shè)S為原始字符串： S # a # b # b # a # P 1 2 1 2 5 2 1 2 1 通過(guò)觀看上面的表，大家可以發(fā)覺Pi-1就是實(shí)際回文字串的長(zhǎng)度。假如知道P，遍歷一次就知道最長(zhǎng)的回文子串?？梢栽撊绾斡?jì)算P呢？這是這個(gè)算法最核心的部分。 下面的爭(zhēng)論

20、基本轉(zhuǎn)自博客：http:/./blog/read.php?2040 該博客中對(duì)Manacher算法介紹得也特別好，向大家推舉。 算法引入兩個(gè)變量id和mx，id表示最長(zhǎng)回文子串的中心位置，mx表示最長(zhǎng)回文字串的邊界位置，即：mx=id+Pid。 在這里有一個(gè)特別有用而且奇妙的結(jié)論：假如mx i，那么Pi = MIN(P2 * id - i, mx - i) 分開理解就是： 1. 假如mx - i Pj, 則Pi=Pj 2. 3. 否則，Pi = mx - i. 4. 這兩個(gè)該如何理解呢？詳細(xì)的解釋請(qǐng)看下面的兩個(gè)圖。 （1）當(dāng) mx - i Pj 的時(shí)候，以Sj為中心的回文子串包含在以Sid為中

21、心的回文子串中，由于 i 和 j 對(duì)稱，以Si為中心的回文子串必定包含在以Sid為中心的回文子串中，所以必有 Pi = Pj （2）當(dāng) Pj = mx - i 的時(shí)候，以Sj為中心的回文子串不肯定完全包含于以Sid為中心的回文子串中，但是基于對(duì)稱性可知，下圖中兩個(gè)綠框所包圍的部分是相同的，也就是 說(shuō)以Si為中心的回文子串，其向右至少會(huì)擴(kuò)張到mx的位置，也就是說(shuō) Pi = mx - i。至于mx之后的部分是否對(duì)稱，就只能老狡猾實(shí)去匹配了。對(duì)于 mx = i 的狀況，無(wú)法對(duì) Pi做更多的假設(shè)，只能Pi = 1，然后再去匹配了。 理解了上面的一點(diǎn)，就沒有問(wèn)題了。 Source Code： #incl

22、ude stdio.h #include stdlib.h #include string.h int longestPalSubstr(char *str) char s100; int i, maxLen = 1, start = 0, j; int len = strlen(str); int mx = 0, id = 0, min; s0 = $; s1 = #; for(i = 0, j = 2; i len; i+, j += 2) sj = stri; sj + 1 = #; sj = 0; len = len * 2 + 1; int *p = (int *)malloc(si

23、zeof(int) * len); memset(p, 0, len); p0 = 1; for(i = 1; i len; i+) min = p2 * id - i (mx - i) ? (mx - i) : p2 * id - i; pi = mx i ? min : 1; while(si + pi = si - pi) pi+; if(i + pi mx) mx = i + pi; id = i; for(i = 0; i len; i+) /printf(%d , pi); if(maxLen pi - 1) maxLen = pi - 1; start = i - maxLen;

24、 printf(The longest palin substr is ); for(i = start; i start + 2 * maxLen + 1; i+) if(si != #) printf(%c, si); printf(, maxlen is %dnn, maxLen); return maxLen; int main() char str100; while(1) gets(str); if(strlen(str) = 0) break; longestPalSubstr(str); return 0; 第6題： 數(shù)軸上從左到右有 n 個(gè)點(diǎn) a0,a1,?,an-1,給定一

25、根長(zhǎng)度為 L 的繩子,求繩子最多能 掩蓋其中的幾個(gè)點(diǎn)。 滿意aj-ai = L aj+1-ai L這兩個(gè)條件的j與i中間的全部點(diǎn)個(gè)數(shù)中的最大值，即j-i+1最大，方法很簡(jiǎn)潔：直接從左到右掃描，兩個(gè)指針i和j，i從位置0開頭，j從位置1開頭，假如aj - ai = L則j+并記錄中間經(jīng)過(guò)的點(diǎn)個(gè)數(shù)，假如aj - ai L則j-回退，掩蓋點(diǎn)個(gè)數(shù)-1回到剛好滿意條件的時(shí)候，將滿意條件的最大值與所求最大值比較，然后i+,j+直到求出最大的點(diǎn)個(gè)數(shù)。 有兩點(diǎn)需要留意： （1）這里可能沒有i和j使得aj - ai剛好等于L的，所以推斷條件不能為aj - ai = L。 （2）可能存在不同的掩蓋點(diǎn)但掩蓋的長(zhǎng)度相同，此時(shí)只選第一次掩蓋的點(diǎn)。 / 求最大掩蓋點(diǎn) #include stdio.h int maxCover(int a, int n, int L) int count = 2, maxCount = 1, start; int i = 0, j = 1; while(i n j n) while(j n) (aj -