位元組的師兄跟我聊了聊位元組跳動的Java面試，演算法是重點，性能調優百分之百會問

一、演算法題一面：

1.  lc 里最長上升子序列的變形題
2. 實作輸入英文單詞聯想的功能

二面：

1.矩陣旋轉，要求空間復雜度 O(1)
2.無序的陣列的中位數，要求時間復雜度盡可能的小

最新2020整理收集的一些面試題（都整理成檔案），有很多干貨，包含mysql，netty，spring，執行緒，spring cloud等詳細講解，也有詳細的學習規劃圖，面試題整理等，我感覺在面試這塊講的非常清楚:獲取面試資料只需:[點擊這里領取!!!] 暗號：CSDN 在這里插入圖片描述

二、計算機網路

1. tcp 怎么保證資料包有序

主機每次發送資料時，TCP 就給每個資料包分配一個序列號并且在一個特定的時間內等待接收主機對分配的這個序列號進行確認，

如果發送主機在一個特定時間內沒有收到接收主機的確認，則發送主機會重傳此資料包，
接收主機利用序列號對接收的資料進行確認，以便檢測對方發送的資料是否有丟失或者亂序等，
接收主機一旦收到已經順序化的資料，它就將這些資料按正確的順序重組成資料流并傳遞到高層進行處理，

2. tcp 和 udp 的異同

TCP 是面向流的可靠資料傳輸連接
UDP 是面向資料包的不可靠無連接

3. tcp 怎么保證可靠性

差錯檢驗機制，反饋機制，重傳機制，引入序號，滑動視窗協議，選擇重傳

4. tcp 中擁塞避免和流量控制機制

擁塞避免和流量控制這兩種機制很像，但是流量控制是由接收方的接受能力也就是接收視窗所決定的，如果接收視窗夠大，以動態調整發送視窗的大小調整發送速度
擁塞避免主要由網路情況所限制，網路情況良好，則加大發送速率，網路狀態差（冗余 ACK 和丟包）則降低發送速率（慢啟動，擁塞控制，快恢復，快重傳） RENO，BBR

5. tcp 四次揮手的詳細解釋

tcp 四次揮手其實可以分為兩個階段
第一：
客戶端至服務器的半雙工連接關閉
客戶端向服務器發送 FIN 信號，進入 FIN_WAIT1 的狀態，等待服務器的 ACK 信號
收到服務器的 ACK 后，進入 FIN_WAIT2
第二：
服務器至客戶端的半雙工連接關閉
客戶端收到服務器發來的 FIN 后，發送 ACK，并進入 TIME_WAIT，等待 2msl，若無例外，則客戶端認為連接成功關閉
服務器收到客戶端發來的 ACK 后，關閉連接

6. 四次揮手之后為什么還要等待 2msl

MSL 是報文最大生存時間
1 是因為有可能客戶端發往服務器的 ACK 丟失，服務器并不知道客戶端已經確認關閉，這時候客戶端的關倍訓導致服務器端無法正常關閉
2 是為了保證連接中的報文都已經傳遞，假如短時間關閉又重新實作一個 TCP 還連到了同個埠上，舊連接中尚未消失的資料就會被認為是新連接的資料，

7. 瀏覽器從輸入網址到顯示出網頁的全程序

輸入網址或者 ip，
如果輸入的是網址，首先要查找域名的 ip 地址
第一步會在瀏覽器快取中查找，如果沒有，轉至查詢系統快取，如果還是沒有，發送請求給路由器，路由器首先會在自身的快取中查找，如果還是沒有，向 ips 發出請求，查詢 ips 中的 dns 快取，如果還是沒有遞回向上查詢直至根服務器，
瀏覽器與 ip 機器之間建立 TCP 連接（三次握手）（HTTP）或者在 TCP 上進一步建立 SSL/TLS 連接（HTTPS）
接下來就是發送 HTTP 報文啥的了
GET，POST，DELETE，PUT，

8. 滑動視窗機制的原理和理解

GBN 協議，回退 N 步協議，這是對停等協議的改進，因為停等協議的傳輸效率非常低下，每次可發送的資料為 N，基數為 base，小于 base 的資料已經發送并且確認，base 是最小的已發送未確認的報文序號，在接收端同樣也有一個接收視窗，（解釋）GBN采用的是累計確認方式，這時候說一下選擇重傳機制，再說一下 TCP 中既不是 GBN 也不是 SR ，而是 GBN 和 SR 的綜合體，
N 的大小必須報文序列編號的一半，否則接收端對報文的確認可能發生混淆

9. Https 原理和實作

10. cookie 和 session 的區別是什么

由于 HTTP 協議是無狀態的協議，所以服務端需要記錄用戶的狀態時，就需要用某種機制來識具體的用戶
cookie 存在本地的上的
session 是存在服務器上的
通俗講，Cookie 是訪問某些網站以后在本地存盤的一些網站相關的資訊，下次再訪問的時候減少一些步驟，另外一個更準確的說法是：Cookies 是服務器在本地機器上存盤的小段文本并隨每一個請求發送至同一個服務器，是一種在客戶端保持狀態的方案，
Session 是存在服務器的一種用來存放用戶資料的類HashTable結構，
二者都用來保持用戶的狀態，cookie可更改，對服務器來說并不安全，服務器常見做法有這兩種：
1.把 session 加密后放入瀏覽器的 cookie 中，瀏覽器重連后將加密的 session 發給服務器
2.cookie 中存盤著 session的id，瀏覽器重連時只需要發送 session_id’ 即可

三、作業系統

1. 行程和執行緒的區別

行程就是保存背景關系切換的程式執行時間總和 = CPU 加載背景關系 + CPU 執行 + CPU 保存背景關系

2. 執行緒是什么呢？

行程的顆粒度太大，每次都要有上下的調入，保存，調出，如果我們把行程比喻為一個運行在電腦上的軟體，那么一個軟體的執行不可能是一條邏輯執行的，必定有多個分支和多個程式段，就好比要實作程式A，實際分成 a，b，c 等多個塊組合而成，那么這里具體的執行就可能變成：
程式 A 得到 CPU =》CPU 加載背景關系，開始執行程式 A 的 a 小段，然后執行 A 的 b 小段，然后再執行 A 的 c 小段，最后 CPU 保存 A 的背景關系，
這里 a，b，c 的執行是共享了 A 的背景關系， CPU 在執行的時候沒有進行背景關系切換的，這里的 a，b，c 就是執行緒，也就是說執行緒是共享了行程的背景關系環境，的更為細小的 CPU 時間段，

3. 行程切換與執行緒切換

4. Linux 中五種 IO 模型

阻塞 I/O（blocking I/O）
非阻塞 I/O （nonblocking I/O）
I/O 復用 (select 和poll) （I/O multiplexing）
信號驅動 I/O （signal driven I/O (SIGIO)）
異步 I/O （asynchronous I/O (the POSIX aio_functions)）
前四種都是同步，只有最后一種才是異步 IO，
同步 IO 和異步 IO 的區別就在于：資料拷貝的時候行程是否阻塞！
阻塞 IO 和非阻塞 IO 的區別就在于：應用程式的呼叫是否立即回傳！

如何實作一個同步非阻塞的請求
實作行程同步的機制有什么
信號量的實作機制
共享鎖和排他鎖
實作一個讀寫鎖
設計一個無鎖佇列
協程的原理

四、資料庫

1. 索引是什么

索引（Index）是幫助 MySQL 高效獲取資料的資料結構，
索引能極大的減少存盤引擎需要掃描的資料量
索引可以把隨機 IO 變成順序 IO
索引可以幫助我們在進行分組、排序等操作時，避免使用臨時表

2. 為什么要用 B+ 樹（B+ 樹的優缺點）

B+ 樹是 B- 樹的變種（PLUS 版）多路絕對平衡查找樹，好的時間復雜度
B+ 樹掃庫、表能力更強
B+ 樹的磁盤讀寫能力更強
B+ 樹的排序能力更強
B+ 樹的查詢效率更加穩定（仁者見仁、智者見智，有可能 B-Tree 第一次就命中了，直接回傳，而 B+Tree 需要找到葉節點，所以查找效率不一定比 B-Tree 更高）
支持順序排序，葉節點之間存在鏈接

3. B+索引和哈希索引的區別？

B-tree 索引
索引是按照順序存盤的，所以，如果按照 B-tree 索引，可以直接回傳，帶順序的資料，但這個資料只是該索引列含有的資訊，因此是順序 I/O
適用于：
精確匹配
范圍匹配
最左匹配
Hash 索引
索引列值的哈希值+資料行指標：因此找到后還需要根據指標去找資料，造成隨機I/O
適合：
精確匹配
不適合：
模糊匹配
范圍匹配
不能排序

1、hash 索引僅滿足 “=”、“IN” 和 “<=>” 查詢，不能使用范圍查詢因為 hash 索引比較的是經常 hash 運算之后的hash值，因此只能進行等值的過濾，不能基于范圍的查找，因為經過hash演算法處理后的 hash 值的大小關系，并不能保證與處理前的 hash 大小關系對應，
2、hash 索引無法被用來進行資料的排序操作由于 hash 索引中存放的都是經過hash 計算之后的值，而 hash 值的大小關系不一定與 hash 計算之前的值一樣，所以資料庫無法利用 hash 索引中的值進行排序操作，
3、對于組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合并后再一起計算 Hash 值，而不是單獨計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用，
4、Hash 索引遇到大量Hash值相等的情況后性能并不一定就會比 B-Tree 索引高，對于選擇性比較低的索引鍵，如果創建 Hash 索引，那么將會存在大量記錄指標資訊存于同一個 Hash 值相關聯，這樣要定位某一條記錄時就會非常麻煩，會浪費多次表資料的訪問，而造成整體性能低下，
總結：哈希適用在小范圍的精確查找，在列資料很大，又不需要排序，不需要模糊查詢，范圍查詢時有用

4. B+ 樹中葉子節點間的指標有什么用？

使得訪問更加簡單，b 樹的話需要不斷在父節點和葉子節點之間來回移動

5. 聚簇和非聚簇索引的區別？

聚簇索引：將資料存盤與索引放到了一塊，找到索引也就找到了資料，聚簇索引的葉子節點就是資料節點，由于聚簇索引是將資料跟索引結構放到一塊，因此一個表僅有一個聚簇索引，聚簇索引具有唯一性
非聚簇索引：非聚簇索引的葉子節點仍然是索引節點，只不過有指向對應資料塊的指標，將資料存盤于索引分開結構，索引結構的葉子節點指向了資料的對應行

6. 非聚簇索引的查詢都要回表嗎？

是的

7. B+ 樹和 AVL 樹 B 樹二叉搜索樹有什么區別？

這幾種各有交集但又不盡相同，
什么是二叉搜索樹？
它或者是一棵空樹，或者是具有下列性質的二叉樹：
1.左子節點的值必定小于父節點的值
2.右子節點的值必定大于父節點的值
首先 AVL 樹是自平衡的二叉搜索樹AVL在該定義的基礎上加入了平衡條件，即：某節點的左右子樹的高度差小于等于1
另一種非嚴格自平衡的二叉搜索樹是紅黑樹，二者使用場景略微有些不同，
AVL 追求整體的絕對平衡，適合于少量插入，大量查找的應用場景（因為維護全域平衡，插入一個往往需要 O(log n)）
紅黑樹適用于一部分插入，一部分查詢的場景（變色，左旋右旋場景相對少些）
B+ 樹是對 B 樹的拓展
一棵 m 階 B 樹 (balanced tree of order m) 是一棵平衡的m路搜索樹，它或者是空樹，或者是滿足下列性質的樹：
1、根結點至少有兩個子女；
2、每個非根節點所包含的關鍵字個數 j 滿足：┌m/2┐ - 1 <= j <= m - 1；
3、除根結點以外的所有結點（不包括葉子結點）的度數正好是關鍵字總數加 1，故內部子樹個數 k 滿足：┌m/2┐ <= k <= m ；
4、所有的葉子結點都位于同一層，
B+ 樹對 B 樹的改進就是：只有葉節點存資料，并且維護了兩個指標，一個指向根節點另一個指向順序葉節點的首位，
B+ 樹還在葉子節點中加入了鏈接指標

五、雜項

這一部分和專案比較相關，基本上專案中有什么或者面試官想到什么問什么，問了很多但是不通用，就只寫一點，

GIL 是什么

全域狀態鎖
2. 為什么會有?

出現多執行緒編程之間資料和狀態一致性問題，為了解決這個資料不能同步的問題
3. 有什么作用?

怎么規避它對于并行的影響?

六、語言相關

1.java的記憶體管理機制

（1）垃圾回收
（2）參考計數
（3）記憶體池機制
2. 講一下 jvm GC 的原理和詳細解釋（分代，標記回收，記憶體劃分）

面試資料

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/224806.html

標籤：其他

上一篇：90%的人都不知道這份演算法面試筆記的存在，阿里面試官直言太變態了。。。。。。

下一篇：哈工大物聯網專業三秋實驗一