刷題網站：xiaolincoding.com
最近有位讀者去蝦皮面試啦，所以今天給大家推薦一篇整理了 15 道蝦皮面試真題答案的文章。
文中比較長，大家可以收藏慢慢看。
給你鍊表的頭結點head ，請將其按升序排列並返回排序後的鍊表 。
圖片實例1：
輸入：head=[4,2,1,3]輸出：[1,2,3,4]實例2：
圖片輸入：head=[-1,5,3,4,0]輸出：[-1,0,3,4,5]這道題可以用雙指針+歸併排序算法解決，主要以下四個步驟
\1. 快慢指針法，遍歷鍊表找到中間節點
\2. 中間節點切斷鍊表
\3. 分別用歸併排序排左右子鍊表
\4. 合併子鍊表
完整代碼如下：
classSolution{publicListNodesortList(ListNodehead){//如果鍊表為空，或者只有一個節點，直接返回即可，不用排序if(head==null||head.next==null)returnhead;//快慢指針移動，以尋找到中間節點ListNodeslow=head;ListNodefast=head;while(fast.next!=null&&fast.next.next!=null){fast=fast.next.next;slow=slow.next;}//找到中間節點，slow節點的next指針，指向midListNodemid=slow.next;//切斷鍊表slow.next=null;//排序左子鍊表ListNodeleft=sortList(head);//排序左子鍊表ListNoderight=sortList(mid);//合併鍊表returnmerge(left,right);}publicListNodemerge(ListNodeleft,ListNoderight){ListNodehead=newListNode(0);ListNodetemp=head;while(left!=null&&right!=null){if(left.val<=right.val){temp.next=left;left=left.next;}else{temp.next=right;right=right.next;}temp=temp.next;}if(left!=null){temp.next=left;}elseif(right!=null){temp.next=right;}returnhead.next;}}2.對稱與非對稱加密算法的區別先複習一下相關概念：
對稱加密算法:加密和解密使用相同密鑰的加密算法。常見的對稱加密算法有AES、3DES、DES、RC5、RC6等。
圖片非對稱加密算法：非對稱加密算法需要兩個密鑰（公開密鑰和私有密鑰）。公鑰與私鑰是成對存在的，如果用公鑰對數據進行加密，只有對應的私鑰才能解密。主要的非對稱加密算法有：RSA、Elgamal、DSA、D-H、ECC。
圖片3. TCP如何保證可靠性 假設應用程序的進程發起IO調用，但是如果內核的數據還沒準備好的話，那應用程序進程就一直在阻塞等待，一直等到內核數據準備好了，從內核拷貝到用戶空間，才返回成功提示，此次IO操作，稱之為阻塞IO。
圖片4.2 非阻塞IO模型如果內核數據還沒準備好，可以先返回錯誤信息給用戶進程，讓它不需要等待，而是通過輪詢的方式再來請求。這就是非阻塞IO，流程圖如下：
圖片4.3 IO多路復用模型IO多路復用之select
應用進程通過調用select函數，可以同時監控多個fd，在select函數監控的fd中，只要有任何一個數據狀態準備就緒了，select函數就會返回可讀狀態，這時應用進程再發起recvfrom請求去讀取數據。
圖片select有幾個缺點：
IO多路復用之epoll
為了解決select存在的問題，多路復用模型epoll誕生，它採用事件驅動來實現，流程圖如下：
圖片epoll先通過epoll_ctl()來註冊一個fd（文件描述符），一旦基於某個fd就緒時，內核會採用回調機制，迅速激活這個fd，當進程調用epoll_wait()時便得到通知。這裡去掉了遍歷文件描述符的坑爹操作，而是採用監聽事件回調的機制。這就是epoll的亮點。
4.4 IO模型之信號驅動模型信號驅動IO不再用主動詢問的方式去確認數據是否就緒，而是向內核發送一個信號（調用sigaction的時候建立一個SIGIO的信號），然後應用用戶進程可以去做別的事，不用阻塞。當內核數據準備好後，再通過SIGIO信號通知應用進程，數據準備好後的可讀狀態。應用用戶進程收到信號之後，立即調用recvfrom，去讀取數據。
圖片4.5 IO 模型之異步IO(AIO)AIO實現了IO全流程的非阻塞，就是應用進程發出系統調用後，是立即返回的，但是立即返回的不是處理結果，而是表示提交成功類似的意思。等內核數據準備好，將數據拷貝到用戶進程緩衝區，發送信號通知用戶進程IO操作執行完畢。
流程如下：
圖片5. hystrix 工作原理 Hystrix 工作流程圖如下:
圖片Hystrix 提供了兩個命令對象：HystrixCommand和HystrixObservableCommand，它將代表你的一個依賴請求任務，向構造函數中傳入請求依賴所需要的參數。
有四種方式執行Hystrix命令。分別是：
如果啟用了 Hystrix緩存，任務執行前將先判斷是否有相同命令執行的緩存。如果有則直接返回包含緩存響應的Observable；如果沒有緩存的結果，但啟動了緩存，將緩存本次執行結果以供後續使用。
如果迴路器被打開，Hystrix將不會執行命令，直接進入Fallback處理邏輯。
日常開發中，我們經常遇到這種業務場景，如：外賣訂單超30分鐘未支付，則自動取消訂單；用戶註冊成功15分鐘後，發短信消息通知用戶等等。這就是延時任務處理場景。針對此類場景我們主要有以下幾種處理方案：
http請求流程
為了解決並發事務存在的髒讀、不可重複讀、幻讀等問題，數據庫大叔設計了四種隔離級別。分別是讀未提交，讀已提交，可重複讀，串行化（Serializable）。
四大隔離級別，都會存在哪些並發問題呢
Read View的可見性規則如下：
數據庫是通過加鎖實現隔離級別的，比如，你想一個人靜靜，不被別人打擾，你可以把自己關在房子，並在房門上加上一把鎖！串行化隔離級別就是加鎖實現的。但是如果頻繁加鎖，性能會下降。因此設計數據庫的大叔想到了MVCC。
可重複讀的實現原理就是MVCC多版本並發控制。在一個事務範圍內，兩個相同的查詢，讀取同一條記錄，卻返回了不同的數據，這就是不可重複讀。可重複讀隔離級別，就是為了解決不可重複讀問題。
查詢一條記錄，基於MVCC，是怎樣的流程呢？
InnoDB 實現MVCC，是通過Read View+ Undo Log實現的，Undo Log保存了歷史快照，Read View可見性規則幫助判斷當前版本的數據是否可見。
可重複讀（RR）隔離級別，是如何解決不可重複讀問題的？
假設存在事務A和B，SQL執行流程如下
圖片在可重複讀（RR）隔離級別下，一個事務里只會獲取一次read view，都是副本共用的，從而保證每次查詢的數據都是一樣的。
假設當前有一張core_user表，插入一條初始化數據,如下：
圖片基於MVCC，我們來看看執行流程
然後回到版本鏈：開始從版本鏈中挑選可見的記錄：
圖片由圖可以看出，最新版本的列name的內容是孫權，該版本的trx_id值為100。開始執行read view可見性規則校驗：
min_limit_id(100)=<trx_id（100）<102;creator_trx_id=trx_id=100;由此可得，trx_id=100的這個記錄，當前事務是可見的。所以查到是name為孫權的記錄。
圖片然後再次回到版本鏈：從版本鏈中挑選可見的記錄：
圖片從圖可得，最新版本的列name的內容是曹操，該版本的trx_id值為101。開始執行read view可見性規則校驗：
min_limit_id(100)=<trx_id（101）<max_limit_id（102);因為m_ids{100,101}包含trx_id（101），並且creator_trx_id(100)不等於trx_id（101）所以，trx_id=101這個記錄，對於當前事務是不可見的。這時候呢，版本鏈roll_pointer跳到下一個版本，trx_id=100這個記錄，再次校驗是否可見：
min_limit_id(100)=<trx_id（100）<max_limit_id（102);因為m_ids{100,101}包含trx_id（100），並且creator_trx_id(100)等於trx_id（100）所以，trx_id=100這個記錄，對於當前事務是可見的，所以兩次查詢結果，都是name=孫權的那個記錄。即在可重複讀（RR）隔離級別下，復用老的Read View副本，解決了不可重複讀的問題。
9. 聊聊索引在哪些場景下會失效？1. 查詢條件包含or，可能導致索引失效
2. 如何字段類型是字符串，where時一定用引號括起來，否則索引失效
3. like通配符可能導致索引失效。
4. 聯合索引，查詢時的條件列不是聯合索引中的第一個列，索引失效。
5. 在索引列上使用mysql的內置函數，索引失效。
6. 對索引列運算（如，+、-、*、/），索引失效。
7. 索引字段上使用（！= 或者 < >，not in）時，可能會導致索引失效。
8. 索引字段上使用is null， is not null，可能導致索引失效。
9. 左連接查詢或者右連接查詢查詢關聯的字段編碼格式不一樣，可能導致索引失效。
10. mysql估計使用全表掃描要比使用索引快,則不使用索引。
虛擬內存，是虛擬出來的內存，它的核心思想就是確保每個程序擁有自己的地址空間，地址空間被分成多個塊，每一塊都有連續的地址空間。同時物理空間也分成多個塊，塊大小和虛擬地址空間的塊大小一致，操作系統會自動將虛擬地址空間映射到物理地址空間，程序只需關注虛擬內存，請求的也是虛擬內存，真正使用卻是物理內存。
現代操作系統使用虛擬內存，即虛擬地址取代物理地址，使用虛擬內存可以有2個好處：
零拷貝實現思想，就利用了虛擬內存這個點：多個虛擬內存可以指向同一個物理地址，可以把內核空間和用戶空間的虛擬地址映射到同一個物理地址，這樣的話，就可以減少IO的數據拷貝次數啦，示意圖如下：
圖片11. 排行榜的實現，比如高考成績排序 排行版的實現，一般使用redis的zset數據類型。
實現demo如下：
圖片12.分布式鎖實現 分布式鎖，是控制分布式系統不同進程共同訪問共享資源的一種鎖的實現。秒殺下單、搶紅包等等業務場景，都需要用到分布式鎖，我們項目中經常使用Redis作為分布式鎖。
選了Redis分布式鎖的幾種實現方法，大家來討論下，看有沒有啥問題哈。
如果執行完setnx加鎖，正要執行expire設置過期時間時，進程crash掉或者要重啟維護了，那這個鎖就「長生不老」了，別的線程永遠獲取不到鎖啦，所以分布式鎖不能這麼實現。
12.2 setnx + value值是過期時間longexpires=System.currentTimeMillis()+expireTime;//系統時間+設置的過期時間StringexpiresStr=String.valueOf(expires);//如果當前鎖不存在，返回加鎖成功if(jedis.setnx(key,expiresStr)==1){returntrue;}//如果鎖已經存在，獲取鎖的過期時間StringcurrentValueStr=jedis.get(key);//如果獲取到的過期時間，小於系統當前時間，表示已經過期if(currentValueStr!=null&&Long.parseLong(currentValueStr)<System.currentTimeMillis()){//鎖已過期，獲取上一個鎖的過期時間，並設置現在鎖的過期時間（不了解redis的getSet命令的小夥伴，可以去官網看下哈）StringoldValueStr=jedis.getSet(key_resource_id,expiresStr);if(oldValueStr!=null&&oldValueStr.equals(currentValueStr)){//考慮多線程並發的情況，只有一個線程的設置值和當前值相同，它才可以加鎖returntrue;}}//其他情況，均返回加鎖失敗returnfalse;}筆者看過有開發小夥伴就是這麼實現分布式鎖的，但是這種方案也有這些缺點：
這個方案可能存在這樣的問題：
在這裡，判斷當前線程加的鎖和釋放鎖是不是一個原子操作。如果調用jedis.del()釋放鎖的時候，可能這把鎖已經不屬於當前客戶端，會解除他人加的鎖。
一般也是用lua腳本代替。lua腳本如下：
ifredis.call('get',KEYS[1])==ARGV[1]thenreturnredis.call('del',KEYS[1])elsereturn0end;這種方式比較不錯了，一般情況下，已經可以使用這種實現方式。但是存在鎖過期釋放了，業務還沒執行完的問題（實際上，估算個業務處理的時間，一般沒啥問題了）。
12.5 Redisson分布式鎖可能存在鎖過期釋放，業務沒執行完的問題。有些小夥伴認為，稍微把鎖過期時間設置長一些就可以啦。其實我們設想一下，是否可以給獲得鎖的線程，開啟一個定時守護線程，每隔一段時間檢查鎖是否還存在，存在則對鎖的過期時間延長，防止鎖過期提前釋放。
當前開源框架Redisson就解決了這個分布式鎖問題。我們一起來看下Redisson底層原理是怎樣的吧：
圖片只要線程一加鎖成功，就會啟動一個watch dog看門狗，它是一個後台線程，會每隔10秒檢查一下，如果線程1還持有鎖，那麼就會不斷的延長鎖key的生存時間。因此，Redisson就是使用Redisson解決了鎖過期釋放，業務沒執行完問題。
13. 零拷貝零拷貝就是不需要將數據從一個存儲區域複製到另一個存儲區域。它是指在傳統IO模型中，指CPU拷貝的次數為0。它是IO的優化方案
流程圖如下：
圖片從流程圖可以看出，傳統IO的讀寫流程，包括了4次上下文切換（4次用戶態和內核態的切換），4次數據拷貝（兩次CPU拷貝以及兩次的DMA拷貝)。
13.2 mmap+write實現的零拷貝mmap 的函數原型如下：
void*mmap(void*addr,size_tlength,intprot,intflags,intfd,off_toffset);mmap使用了虛擬內存，可以把內核空間和用戶空間的虛擬地址映射到同一個物理地址，從而減少數據拷貝次數！
mmap+write實現的零拷貝流程如下：
圖片可以發現，mmap+write實現的零拷貝，I/O發生了4次用戶空間與內核空間的上下文切換，以及3次數據拷貝。其中3次數據拷貝中，包括了2次DMA拷貝和1次CPU拷貝。
mmap是將讀緩衝區的地址和用戶緩衝區的地址進行映射，內核緩衝區和應用緩衝區共享，所以節省了一次CPU拷貝『』並且用戶進程內存是虛擬的，只是映射到內核的讀緩衝區，可以節省一半的內存空間。
sendfile實現的零拷貝sendfile是Linux2.1內核版本後引入的一個系統調用函數，API如下：
ssize_tsendfile(intout_fd,intin_fd,off_t*offset,size_tcount);sendfile表示在兩個文件描述符之間傳輸數據，它是在操作系統內核中操作的，避免了數據從內核緩衝區和用戶緩衝區之間的拷貝操作，因此可以使用它來實現零拷貝。
sendfile實現的零拷貝流程如下：
sendfile實現的零拷貝
可以發現，sendfile實現的零拷貝，I/O發生了2次用戶空間與內核空間的上下文切換，以及3次數據拷貝。其中3次數據拷貝中，包括了2次DMA拷貝和1次CPU拷貝。那能不能把CPU拷貝的次數減少到0次呢？有的，即帶有DMA收集拷貝功能的sendfile！
sendfile+DMA scatter/gather實現的零拷貝linux 2.4版本之後，對sendfile做了優化升級，引入SG-DMA技術，其實就是對DMA拷貝加入了scatter/gather操作，它可以直接從內核空間緩衝區中將數據讀取到網卡。使用這個特點搞零拷貝，即還可以多省去一次CPU拷貝。
sendfile+DMA scatter/gather實現的零拷貝流程如下：
圖片可以發現，sendfile+DMA scatter/gather實現的零拷貝，I/O發生了2次用戶空間與內核空間的上下文切換，以及2次數據拷貝。其中2次數據拷貝都是包DMA拷貝。這就是真正的 零拷貝（Zero-copy) 技術，全程都沒有通過CPU來搬運數據，所有的數據都是通過DMA來進行傳輸的。
14. synchronizedsynchronized是Java中的關鍵字，是一種同步鎖。synchronized關鍵字可以作用於方法或者代碼塊。
一般面試時。可以這麼回答：
如果synchronized作用於代碼塊，反編譯可以看到兩個指令：monitorenter、monitorexit，JVM使用monitorenter和monitorexit兩個指令實現同步；如果作用synchronized作用於方法,反編譯可以看到ACCSYNCHRONIZED標記，JVM通過在方法訪問標識符(flags)中加入ACCSYNCHRONIZED來實現同步功能。
monitor是什麼呢？操作系統的管程（monitors）是概念原理，ObjectMonitor是它的原理實現。
圖片在Java虛擬機（HotSpot）中，Monitor（管程）是由ObjectMonitor實現的，其主要數據結構如下：
ObjectMonitor(){_header=NULL;_count=0;//記錄個數_waiters=0,_recursions=0;_object=NULL;_owner=NULL;_WaitSet=NULL;//處於wait狀態的線程，會被加入到_WaitSet_WaitSetLock=0;_Responsible=NULL;_succ=NULL;_cxq=NULL;FreeNext=NULL;_EntryList=NULL;//處於等待鎖block狀態的線程，會被加入到該列表_SpinFreq=0;_SpinClock=0;OwnerIsThread=0;}ObjectMonitor中幾個關鍵字段的含義如圖所示：
圖片14.3 Java Monitor 的工作機理
圖片
圖片Mark Word 是用於存儲對象自身的運行時數據，如哈希碼（HashCode）、GC分代年齡、鎖狀態標誌、線程持有的鎖、偏向線程 ID、偏向時間戳等。
圖片重量級鎖，指向互斥量的指針。其實synchronized是重量級鎖，也就是說Synchronized的對象鎖，Mark Word鎖標識位為10，其中指針指向的是Monitor對象的起始地址。
15. 分布式id生成方案有哪些？什麼是雪花算法？分布式id生成方案主要有：
什麼是雪花算法？
雪花算法是一種生成分布式全局唯一ID的算法，生成的ID稱為Snowflake IDs。這種算法由Twitter創建，並用於推文的ID。
一個Snowflake ID有64位。
雪花算法
留言列表