具體問題
-
編程題：鏈表加法
與這個(gè)題目類似：add-two-numbers，但是給出的兩個(gè)數(shù)和計(jì)算的結(jié)果是正向的：鏈表頭部就是最高位，尾部才是個(gè)位。
譬如135+25=160：
input：
1->3->5
2->5
output:
1->6->0
當(dāng)時(shí)思路：直接使用兩個(gè)棧來存儲(chǔ)兩個(gè)鏈表，再每次從棧頂取元素相加。
面試官：能否只使用一個(gè)棧實(shí)現(xiàn)？
一個(gè)棧+遞歸？？
存疑。
TCP、UDP區(qū)別
| 協(xié)議 | 是否面向連接 | 傳輸可靠性 | 傳輸形式 | 傳輸速率 | 所需資源 |
| :----: | ---- | ---- | ---- | ---- | ---- |
|TCP| 面向連接 | 可靠 | 字節(jié)流 | 慢 | 多 |
|UDP| 不面向連接 | 不可靠 | 數(shù)據(jù)報(bào)文段 | 快 | 少 |UDP最大數(shù)據(jù)報(bào)文長度
UDP最大數(shù)據(jù)報(bào)文長度=IP數(shù)據(jù)報(bào)的最大報(bào)文長度(65535字節(jié))-IP首部(20字節(jié))-UDP首部(8字節(jié))介紹
TCP擁塞控制
慢開始、擁塞避免、快重傳、快恢復(fù)。內(nèi)核態(tài)與用戶態(tài)的區(qū)別
權(quán)限不同
內(nèi)核態(tài)：可以執(zhí)行特權(quán)指令和非特權(quán)指令。
用戶態(tài)：僅能執(zhí)行非特權(quán)指令。
百度百科：特權(quán)指令
常見的特權(quán)指令有以下幾種:
（1）有關(guān)對I/O設(shè)備使用的指令 如啟動(dòng)I/O設(shè)備指令、測試I/O設(shè)備工作狀態(tài)和控制I/O設(shè)備動(dòng)作的指令等。
（2）有關(guān)訪問程序狀態(tài)的指令 如對程序狀態(tài)字（PSW）的指令等。
（3）存取特殊寄存器指令 如存取中斷寄存器、時(shí)鐘寄存器等指令。
（4）其他指令。
- 內(nèi)核態(tài)與用戶態(tài)如何切換
用戶態(tài)->內(nèi)核態(tài)：
切換過程中會(huì)用到 訪管指令（非特權(quán)指令，因?yàn)樾枰谟脩魬B(tài)使用）
- 系統(tǒng)調(diào)用，即用戶程序要求操作系統(tǒng)的服務(wù)
- 中斷
- 異常
- 用戶程序企圖執(zhí)行特權(quán)指令
內(nèi)核態(tài)->用戶態(tài)：
中斷返回指令（特權(quán)指令，因?yàn)橹荒茉趦?nèi)核態(tài)調(diào)用）
介紹
TIME_WAIT狀態(tài)
等待時(shí)間：2*MSL。
原因：確保連接的被動(dòng)結(jié)束方（簡稱B）能夠收到主動(dòng)結(jié)束方（簡稱A）的ACK報(bào)文。
如果B沒收到，則會(huì)重新發(fā)送FIN報(bào)文。丟失ACK的傳輸時(shí)間加上重發(fā)FIN傳輸?shù)臅r(shí)間約為2*MSL。局域網(wǎng)內(nèi)不同設(shè)備發(fā)送消息的沖突如何處理
主要考點(diǎn)：CSMA/CD協(xié)議
載波監(jiān)聽：不管在發(fā)送前，還是發(fā)送中，每個(gè)主機(jī)都必須不停地檢測信道。
碰撞檢測：邊發(fā)送邊監(jiān)聽。
當(dāng)檢測到?jīng)_突時(shí)，就立即停止發(fā)送，面的繼續(xù)進(jìn)行無效的發(fā)送，白白浪費(fèi)網(wǎng)絡(luò)資源，然后等待一段隨機(jī)時(shí)間后再次發(fā)送。
使用 截?cái)喽M(jìn)制指數(shù)退避 算法來確定重傳時(shí)間：
每次從離散的整數(shù)集合中隨機(jī)取一個(gè)數(shù)，記為
r。重傳推后的時(shí)間就是r倍的爭用期。
參考：
- 百度百科：截?cái)喽M(jìn)制指數(shù)退避
- 《計(jì)算機(jī)網(wǎng)絡(luò)》第七版 謝希仁編著
介紹
HashMap的數(shù)據(jù)結(jié)構(gòu)
數(shù)組、鏈表、紅黑樹。如何設(shè)計(jì)一個(gè)支持并發(fā)的
HashMap
參考ConcurrenHashMap和SynchronizedHashMap的實(shí)現(xiàn)。除了鏈表和紅黑樹，還可以如何處理
Hash沖突
公共溢出區(qū)、再哈希、順序?qū)ぶ罚ň€性探測、二次探測、偽隨機(jī)數(shù)）。使用再哈希處理哈希碰撞時(shí)，查找時(shí)如何區(qū)分使用的哪一個(gè)哈希算法
當(dāng)時(shí)回答的是，依次與每一個(gè)Hash算法計(jì)算的哈希值所在位置存儲(chǔ)的數(shù)據(jù)進(jìn)行equals比較，直到找到 或者 所有hash函數(shù)都比較完且不存在。
不存在的判定條件應(yīng)該是所有hash函數(shù)都比較完，而不應(yīng)該是某一個(gè)hash值所在位置為空就停止：有可能為空的位置在當(dāng)前查找的元素插入時(shí)存在，所以發(fā)生沖突繼續(xù)使用后續(xù)的hash函數(shù)計(jì)算，而查找時(shí)那個(gè)位置的元素已被移除。
存疑
介紹一下原子類
對原子類的操作都具有原子性，即不可再拆分。原子操作的實(shí)現(xiàn)原理
參考：
聊聊并發(fā)（五）——原子操作的實(shí)現(xiàn)原理
原子操作是如何實(shí)現(xiàn)的？ #3
