百度客戶端三面面經（附答案）

后臺回復“20210302”獲取百度客戶端三面面經pdf版~

主題一：C++

t1. 是否了解volatile關鍵字？

1. volatile指的是易變的變數，該關鍵詞提醒編譯器其后所定義的變數隨時都可能改變，因此編譯后的程式每次需要存盤或讀取該變數時，都會直接從變數地址中讀取資料，
2. 若沒有volatile，編譯器可能優化讀寫，暫存某個變數至暫存器（暫存器速度快于記憶體），若該變數是由其他程式更新，就會出現不一致的現象，

t2. 簡單說一下記憶體對齊的內容？

1. CPU對不能被對齊量（要操作記憶體的大小）整除的記憶體地址的訪問，便是訪問未對齊內容，這或者對性能或者對可靠性造成影響，因此我們應該盡量避免訪問未對齊內容，因此C/C++出現了記憶體對齊機制，

2. 所有基礎型別的對齊量就是其大小，但是struct、class、union的型別的對齊量等于其非靜態成員變數中最大的對齊量，

3. 比如一個結構體有一個char一個int一個short，那么該結構體的大小是12bytes，因為char后有三個空白填充，而short有兩個空白填充，

t3.overload 、override、overwrite 之間的區別？

1. Overload 多載，類內宣告的幾個具有不同引數串列的同名函式，根據引數串列確定呼叫哪個函式，多載不關心函式回傳型別，
2. Override 覆寫，子類重新定義基類中有相同名稱、引數和回傳值型別的虛函式，重寫的基類中被重寫的函式必須有virtual修飾，
3. Overwrite 重寫（重定義），若子類和基類的函式同名，但引數不同，則不管有無virtual，基類的函式被隱藏，若函式同名引數也相同，但沒有virtual宣告，則也被隱藏，否則就是重寫了，

主題二：作業系統：

t1. 簡要介紹一下區域性原理？用代碼舉例利用了時間區域性和空間區域性的演算法？

1. 區域性原理是指CPU訪問存盤器時，無論是存取指令還是存取資料，所訪問的存盤單元都趨于聚集在一個較小的連續區域中， 包含時間區域性（近期很可能被再次訪問）、空間區域性（臨近空間很可能被訪問），
2. 比如用一個臨時變數sum計算一個陣列A的和，那么遍歷的程序中，我們根據記憶體順序訪問陣列，利用了空間區域性，而每次都要對臨時變數sum的訪問便是利用了時間區域性，

t2. 說一下分頁、分段、段頁式分配的異同？

1. 分頁，用戶程式的地址空間被劃分成若干固定大小的區域，稱為“頁”，相應地，記憶體空間分成若干個物理塊，頁和塊的大小相等，可將用戶程式的任一頁放在記憶體的任一塊中，實作了離散分配，分頁方式的優點是頁長固定，因而便于構造頁表、易于管理，且不存在外碎片，
2. 分段，段是按照程式的自然分界劃分的長度可以動態改變的區域，通常，程式員把子程式、運算元和常數等不同型別的資料劃分到不同的段中，并且每個程式可以有多個相同型別的段，段的邏輯獨立性使其易于編譯、管理、修改和保護，段長可以根據需要動態改變，不存在內碎片，
3. 段頁式，程式的地址空間按邏輯單位分成基本獨立的段，而每一段有自己的段名，再把每段分成固定大小的若干頁，程式對記憶體的調入或調出是按頁進行的，但它又可按段實作共享和保護，能有效地利用主存，為組織多道程式運行提供了方便，但增加了硬體成本、系統的復雜性和管理上的開銷，

主題三：計算機網路：

t1. 是否了解RIP協議和OSPF協議？

1. RIP（路由資訊協議）

   RIP協議是一種采用距離向量演算法的路由協議，基于距離-向量的路由選擇協議，其設計思想簡單，它要求路由器周期性地通知相鄰路由器自己可以到達的網路，以及到達網路的距離（跳數），這里的“距離”實際上指的是“最短距離”，

   簡述RIP協議的作業原理： 路由器每30秒把自己的路由表發給鄰居，路由器用鄰居發來的路由表根據距離向量演算法修改自己的路由表，初始時每個路由器只有到直連網距離為1的路由，

2. OSPF（開放最短路徑優先協議）

   OSPF不受某一家廠商控制，而是公開發表的，使用Dijikstra最短路徑演算法，使用分布式的鏈路狀態協議，

   簡述OSPF協議的作業原理： 路由器互相發送直接相連的鏈路資訊和它擁有的到其它路由器的鏈路資訊，每個 OSPF 路由器維護相同自治系統拓撲結構的資料庫，從這個資料庫里，構造出最短路徑樹來計算出路由表，當拓撲結構發生變化時，OSPF 能迅速重新計算出路徑，而只產生少量的路由協議流量，此外，所有 OSPF 路由選擇協議的交換都是經過身份驗證的，

主題四：演算法

t1. 給定長度為 n ? 1 n - 1 n?1 的陣列，所有元素均在 [ 1 , n ] [1, n] [1,n] 范圍內，求唯一未出現的數字

int find(vector<int>& nums) {
    int t = 0, n = nums.size() + 1;
    for (int i = 1; i <= n; i++) {
        t ^= i;
    }
    for (int i = 0; i < n - 1; i++) {
        t ^= nums[i];
    }
    return t;
}

這道題可以用比較簡單的映射作法，然后遍歷一遍，看看哪個數字不存在即可找到答案，但是這樣的話空間復雜度就是 O ( n ) O(n) O(n)，

我們可以利用數學方法中的異或運算，當兩個數相同時，異或結果為 0 0 0，而任何數與 0 0 0 異或均為這個數，因此我們，可以先得到 1 1 1 一直異或到 n n n 的結果 t t t，再將 t t t 與陣列中每個數異或，最后留下來的數就是唯一未出現的數，空間復雜度也降低至 O ( 1 ) O(1) O(1)，

• 時間復雜度： O ( n ) O(n) O(n)

• 空間復雜度： O ( 1 ) O(1) O(1)

t2. 給定陣列，將所有的 0 0 0 移動到陣列末尾，要求時間復雜度 O ( n ) O(n) O(n)

本題采用雙向查找的方式，分以下幾個步驟完成：

1. 設定陣列左右兩邊的下標變數 i 和 j
2. 先從陣列右邊開始查找不為 0 的數，等于 0 則用 continue 繼續查找，直到找到再進行第 3 步
3. 從左側遍歷查找等于 0 的數，找到之后與第2步找到的不為 0 的數進行互換
4. 重復第 2 步和第 3 步直至一輪遍歷結束，即可實作時間復雜度為 O ( n ) O(n) O(n)

void putzeroback(vector<int>& arr) { 
    int i = 0, j = arr.size()-1; 
    while(i < j) { 
        if(arr[j] == 0) { 
            j--; 
            continue; 
        } 
        if(arr[i] == 0) { 
            arr[i] = arr[j]; 
            arr[j] = 0; 
            j--; 
        } 
        i++; 
    } 
}

關注GTAlgorithm，專注周賽、面經題解分享，陪大家一起攻克演算法難關~

演算法干歡訓總

第 230 場周賽

百度客戶端二面面經（附答案）