2021年百度公司普通程序員面試題

第1題：

?判斷一個括號字符串是否匹配正確，如果括號有多種，怎么做？如（（[]））正確，[[(()錯誤。

?用棧來出現，凡是左括號就壓棧，凡是右括號就出棧，最后如果棧為空就匹配正確

第2題：

?百度Spider如何在不超過抓取限額的情況下使得抓取的網頁價值之和最大，要求一個最佳抓取方案。請詳細描述你的算法思路（可以用偽代碼），并分析時間復雜度和空間復雜度。

?假設每個網頁有價值為wi.

wi的值為浮點數,通過堆實現.

wi為整數,則通過桶式排序記錄每個價值對應的網頁數量

第3題：

?僅用O(1)的空間，將整數數組按奇偶數分成2部分，數組左邊是奇數、右邊是偶數。（要求：給出完整代碼，盡量高效，簡潔）

?#兩個指針，分別從頭和從尾遍歷數組，詳見代碼，已測試通過

#include

#include

#define bool int

#define false 0

#define true 1

void Reorder(int *pData, unsigned int length, bool (*func)(int));

bool isEven(int n);

void ReorderOddEven_1(int *pData, unsigned int length)

{

????if(pData == NULL || length == 0)

????????return;

????int *pBegin = pData;

????int *pEnd = pData + length - 1;

????while(pBegin < pEnd)

????{

????????// 向后移動pBegin，直到它指向偶數

????????while(pBegin < pEnd && (*pBegin & 0x1) != 0)

????????????pBegin ++;

????????// 向前移動pEnd，直到它指向奇數

????????while(pBegin < pEnd && (*pEnd & 0x1) == 0)

????????????pEnd --;

????????if(pBegin < pEnd)

????????{

????????????int temp = *pBegin;

????????????*pBegin = *pEnd;

????????????*pEnd = temp;

????????}

????}

}

void Reorder(int *pData, unsigned int length, bool

??(*func)(int))

{

????if(pData == NULL || length == 0)

????????return;

????int *pBegin = pData;

????int *pEnd = pData + length - 1;

????while(pBegin < pEnd)

????{

????????//向后移動pBegin

????????while(pBegin < pEnd &&!func(*pBegin))

????????????pBegin ++;

????????// 向前移動pEnd

????????while(pBegin < pEnd &&func(*pEnd))

????????????pEnd --;

????????if(pBegin < pEnd)

????????{

????????????int temp = *pBegin;

????????????*pBegin = *pEnd;

????????????*pEnd = temp;

????????}

????}

}

bool isEven(int n)

{

????return (n & 1) == 0;

}

第4題：

?給定兩個數A、B（0，

?

//二分法求解

//a^b = (a ^ (b/2))^2

int GetPow(int a, int b) {

??? if (b == 1 || b == 0) {

??? ? ? return a;

??? }

??? if (b % 2) {

??? ? ? return ((int) (pow((float) GetPow(a, b / 2), 2) * a) % 1000);

??? } else {

??? ? ? return ((int) (pow((float) GetPow(a, b / 2), 2)) % 1000);

??? }

}

第5題：

?微博上，每個用戶可以發送一條消息，可以 follow 另一個用戶， 當用戶發送消息時，所有 follow 他的用戶都能看見這條消息。如 A follow B，則 B 的消息，A 都能看見。

實現一個微博客消息存儲系統，可以使用多臺機器來滿足性能要求， 可以再海量的用戶和消息下，快速的實現以下兩種查詢：

a）給定一個用戶，查詢他發送的消息，按消息發送時間排序，新 的消息在前。

b）給定一個用戶，查詢他 follow 的所有人的消息，按消息發送時 間排序，新的消息在前.

?(a):根據uid,msg分庫記錄用戶的消息.直接通過sql查詢實現

(b):A follow B, B發消息的時候主動發送消息id到A的新鮮事列表.

如果A是僵死用戶就通過拉的方式,登陸后獲取所有關注用戶的微薄