<noframes id="dh1vt"><progress id="dh1vt"></progress>

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

          小編:管理員 86閱讀 2021.06.17

          第1題:


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



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


          第2題:


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



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

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

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


          第3題:


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



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

          #include <stdio.h>

          #include <stdlib.h>

          #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<100000),求A^B中最后三位數是多少。請簡要描述你的思路。



           

          //二分法求解

          //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是僵死用戶就通過拉的方式,登陸后獲取所有關注用戶的微薄


          關聯標簽: