本文是阿里巴巴 2019 面試題集錦(含答案)，是阿里巴巴自身技術(shù)專家們結(jié)合多年的工作、面試經(jīng)驗(yàn)總結(jié)提煉而成的面試真題。通過(guò)這些面試題，還可以間接地了解技術(shù)大牛們出題思路與考察要點(diǎn)。

想要入職大廠可謂是千軍萬(wàn)馬過(guò)獨(dú)木橋。要通過(guò)層層考驗(yàn)，刷題肯定是必不可少的。

為幫助開發(fā)者們提升面試技能、有機(jī)會(huì)入職阿里，云棲社區(qū)特別制作了這個(gè)專輯——阿里巴巴資深技術(shù)專家們結(jié)合多年的工作、面試經(jīng)驗(yàn)總結(jié)提煉而成的面試真題這一次整體放出。

這一次，不僅是知識(shí)的收獲，還將間接地與技術(shù)大牛們做了直觀的溝通，了解他們的出題思路與考察要點(diǎn)，并加以消化吸收，這對(duì)自己技術(shù)能力本身就是一種極大的提升。走上編程之路，不斷豐富自己方能與世接軌，努力做最優(yōu)秀的自己。

面試題001：如何實(shí)現(xiàn)一個(gè)高效的單向鏈表逆序輸出？

——阿里巴巴出題專家：昀龍／阿里云彈性人工智能負(fù)責(zé)人

參考答案

下面是其中一種寫法，也可以有不同的寫法，比如遞歸等。供參考。

typedefstructnode{intdata;structnode*next;node(intd):data(d),next(NULL){}}node;voidreverse(node*head){if(NULL==head||NULL==head->next){return;}node*prev=NULL;node*pcur=head->next;node*next;while(pcur!=NULL){if(pcur->next==NULL) { pcur->next=prev; break; } next=pcur->next; pcur->next=prev; prev=pcur; pcur=next; } head->next=pcur; node*tmp=head->next; while(tmp!=NULL) { cout<data<<" "; tmp=tmp->next; } }面試題002：已知sqrt (2)約等于1.414，要求不用數(shù)學(xué)庫(kù)，求sqrt (2)精確到小數(shù)點(diǎn)后10位。

——阿里巴巴出題專家：文景／阿里云CDN資深技術(shù)專家

考察點(diǎn)

基礎(chǔ)算法的靈活應(yīng)用能力（二分法學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的同學(xué)都知道，但不一定往這個(gè)方向考慮；如果學(xué)過(guò)數(shù)值計(jì)算的同學(xué)，應(yīng)該還要能想到牛頓迭代法并解釋清楚）。

退出條件設(shè)計(jì)。

參考答案

1. 已知sqrt(2)約等于1.414，那么就可以在(1.4, 1.5)區(qū)間做二分查找，如：

high=>1.5

low=>1.4

mid => (high+low)/2=1.45

1.45*1.45>2 ? high=>1.45 : low => 1.45

循環(huán)到c)

2. 退出條件

前后兩次的差值的絕對(duì)值<=0.0000000001, 則可退出。

代碼示例：

const double EPSINON = 0.0000000001;double sqrt2( ){double low = 1.4, high = 1.5;double mid = (low + high) / 2;while (high – low > EPSINON){if (mid*mid < 2){high = mid;}else{low = mid;}mid = (high + low) / 2;}return mid;}面試題003：給定一個(gè)二叉搜索樹(BST)，找到樹中第K小的節(jié)點(diǎn)。

——阿里巴巴出題專家：文景／阿里云CDN資深技術(shù)專家

考察點(diǎn)

1. 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的理解和編碼能力

2. 遞歸使用

示例：

如下圖，輸入K=3， 輸出節(jié)點(diǎn)值3

說(shuō)明：保證輸入的K滿足1<=K<=(節(jié)點(diǎn)數(shù)目）

參考答案

樹相關(guān)的題目，第一眼就想到遞歸求解，左右子樹分別遍歷。聯(lián)想到二叉搜索樹的性質(zhì)，root大于左子樹，小于右子樹，如果左子樹的節(jié)點(diǎn)數(shù)目等于K-1，那么root就是結(jié)果，否則如果左子樹節(jié)點(diǎn)數(shù)目小于K-1，那么結(jié)果必然在右子樹，否則就在左子樹。因此在搜索的時(shí)候同時(shí)返回節(jié)點(diǎn)數(shù)目，跟K做對(duì)比，就能得出結(jié)果了。

代碼示例：

/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/class Solution {private class ResultType {// 是否找到boolean found;// 節(jié)點(diǎn)數(shù)目int val;ResultType(boolean found, int val) {this.found = found;this.val = val;}}public int kthSmallest(TreeNode root, int k) {return kthSmallestHelper(root, k).val;}private ResultType kthSmallestHelper(TreeNode root, int k) {if (root == null) {return new ResultType(false, 0);}ResultType left = kthSmallestHelper(root.left, k);// 左子樹找到，直接返回if (left.found) {return new ResultType(true, left.val);}// 左子樹的節(jié)點(diǎn)數(shù)目 = K-1，結(jié)果為root的值if (k - left.val == 1) {return new ResultType(true, root.val);}// 右子樹尋找ResultType right = kthSmallestHelper(root.right, k - left.val - 1);if (right.found) {return new ResultType(true, right.val);}// 沒找到，返回節(jié)點(diǎn)總數(shù)return new ResultType(false, left.val + 1 + right.val);}}

復(fù)雜度分析：

時(shí)間復(fù)雜度： O(N），節(jié)點(diǎn)最多遍歷一遍

空間復(fù)雜度：O(1），（如果算上遞歸深度可以當(dāng)做O(logN)）

面試題004：LRU緩存機(jī)制。

——阿里巴巴出題專家：文景／阿里云CDN資深技術(shù)專家

設(shè)計(jì)和實(shí)現(xiàn)一個(gè)LRU（最近最少使用）緩存數(shù)據(jù)結(jié)構(gòu)，使它應(yīng)該支持一下操作：get和put。

get(key) - 如果key存在于緩存中，則獲取key的value（總是正數(shù)），否則返回 -1。

put(key,value) - 如果key不存在，請(qǐng)?jiān)O(shè)置或插入value。當(dāng)緩存達(dá)到其容量時(shí)，它應(yīng)該在插入新項(xiàng)目之前使最近最少使用的項(xiàng)目作廢。

參考答案

代碼示例：

《 Python版本 》

class LRUCache(object):def __init__(self, capacity):""":type capacity: int"""self.cache = {}self.keys = []self.capacity = capacitydef visit_key(self, key):if key in self.keys:self.keys.remove(key)self.keys.append(key)def elim_key(self):key = self.keys[0]self.keys = self.keys[1:]del self.cache[key]def get(self, key):""":type key: int:rtype: int"""if not key in self.cache:return -1self.visit_key(key)return self.cache[key]def put(self, key, value):""":type key: int:type value: int:rtype: void"""if not key in self.cache:if len(self.keys) == self.capacity:self.elim_key()self.cache[key] = valueself.visit_key(key)def main():s = [["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]]obj = LRUCache(2)l=[]for i,c in enumerate(s[0]):if(c == "get"):l.append(obj.get(s[1][i][0]))else:obj.put(s[1][i][0], s[1][i][1])print(l)if __name__ == "__main__":main()

《 C++版本 》

class LRUCache{public:LRUCache(int capacity) {cap = capacity;}int get(int key) {auto it = m.find(key);if (it == m.end()) return -1;l.splice(l.begin(), l, it->second);return it->second->second;}void set(int key, int value) {auto it = m.find(key);if (it != m.end()) l.erase(it->second);l.push_front(make_pair(key, value));m[key] = l.begin();if (m.size() > cap) {int k = l.rbegin()->first;l.pop_back();m.erase(k);}面試題005：關(guān)于epoll和select的區(qū)別，哪些說(shuō)法是正確的？（多選）

——阿里巴巴出題專家：寈峰／阿里技術(shù)專家

A. epoll和select都是I/O多路復(fù)用的技術(shù)，都可以實(shí)現(xiàn)同時(shí)監(jiān)聽多個(gè)I/O事件的狀態(tài)。

B. epoll相比select效率更高，主要是基于其操作系統(tǒng)支持的I/O事件通知機(jī)制，而select是基于輪詢機(jī)制。

C. epoll支持水平觸發(fā)和邊沿觸發(fā)兩種模式。

D. select能并行支持I/O比較小，且無(wú)法修改。

參考答案 A . B . C

面試題006：從innodb的索引結(jié)構(gòu)分析，為什么索引的key長(zhǎng)度不能太長(zhǎng)？

——阿里巴巴出題專家：近秋／阿里云數(shù)據(jù)庫(kù)產(chǎn)品技術(shù)部技術(shù)專家

參考答案

key太長(zhǎng)會(huì)導(dǎo)致一個(gè)頁(yè)當(dāng)中能夠存放的key的數(shù)目變少，間接導(dǎo)致索引樹的頁(yè)數(shù)目變多，索引層次增加，從而影響整體查詢變更的效率。

面試題007：MySQL的數(shù)據(jù)如何恢復(fù)到任意時(shí)間點(diǎn)？

——阿里巴巴出題專家：近秋／阿里云數(shù)據(jù)庫(kù)產(chǎn)品技術(shù)部技術(shù)專家

參考答案

恢復(fù)到任意時(shí)間點(diǎn)以定時(shí)的做全量備份，以及備份增量的binlog日志為前提?；謴?fù)到任意時(shí)間點(diǎn)首先將全量備份恢復(fù)之后，再此基礎(chǔ)上回放增加的binlog直至指定的時(shí)間點(diǎn)。

面試題008：NFS和SMB是最常見的兩種NAS（Network Attached Storage）協(xié)議，當(dāng)把一個(gè)文件系統(tǒng)同時(shí)通過(guò)NFS和SMB協(xié)議共享給多個(gè)主機(jī)訪問(wèn)時(shí)，以下哪些說(shuō)法是錯(cuò)誤的：（多選）

——阿里巴巴出題專家：起影／阿里云文件存儲(chǔ)高級(jí)技術(shù)專家

A. 不可能有這樣的操作，即把一個(gè)文件系統(tǒng)同時(shí)通過(guò)NFS和SMB協(xié)議共享給多個(gè)主機(jī)訪問(wèn)。

B. 主機(jī)a的用戶通過(guò)NFS協(xié)議創(chuàng)建的文件或者目錄，另一個(gè)主機(jī)b的用戶不能通過(guò)SMB協(xié)議將其刪除。

C. 在同一個(gè)目錄下，主機(jī)a通過(guò)NFS協(xié)議看到文件file.txt，主機(jī)b通過(guò)SMB協(xié)議也看到文件file.txt，那么它們是同一個(gè)文件。

D. 主機(jī)a通過(guò)NFS協(xié)議，以及主機(jī)b通過(guò)SMB協(xié)議，都可以通過(guò)主機(jī)端的數(shù)據(jù)緩存，提升文件訪問(wèn)性能。

參考答案 A . B . C

面試題009：輸入ping IP后敲回車，發(fā)包前會(huì)發(fā)生什么？

——阿里巴巴出題專家：懷虎／阿里云云效平臺(tái)負(fù)責(zé)人

參考答案

首先根據(jù)目的IP和路由表決定走哪個(gè)網(wǎng)卡，再根據(jù)網(wǎng)卡的子網(wǎng)掩碼地址判斷目的IP是否在子網(wǎng)內(nèi)。如果不在則會(huì)通過(guò)arp緩存查詢IP的網(wǎng)卡地址，不存在的話會(huì)通過(guò)廣播詢問(wèn)目的IP的mac地址，得到后就開始發(fā)包了，同時(shí)mac地址也會(huì)被arp緩存起來(lái)。

面試題010：請(qǐng)解釋下為什么鹿晗發(fā)布戀情的時(shí)候，微博系統(tǒng)會(huì)崩潰，如何解決？

——阿里巴巴出題專家：江嵐／阿里巴巴數(shù)據(jù)技術(shù)高級(jí)技術(shù)專家

參考答案 《 參考思路 》

A. 獲取微博通過(guò)pull方式還是push方式

B. 發(fā)布微博的頻率要遠(yuǎn)小于閱讀微博

C. 流量明星的發(fā)微博，和普通博主要區(qū)分對(duì)待，比如在sharding的時(shí)候，也要考慮這個(gè)因素

面試題011：現(xiàn)有一批郵件需要發(fā)送給訂閱顧客，且有一個(gè)集群（集群的節(jié)點(diǎn)數(shù)不定，會(huì)動(dòng)態(tài)擴(kuò)容縮容）來(lái)負(fù)責(zé)具體的郵件發(fā)送任務(wù)，如何讓系統(tǒng)盡快地完成發(fā)送？請(qǐng)?jiān)斒黾夹g(shù)方案！

——阿里巴巴出題專家：江嵐／阿里巴巴數(shù)據(jù)技術(shù)高級(jí)技術(shù)專家

參考答案

A. 借助消息中間件，通過(guò)發(fā)布者訂閱者模式來(lái)進(jìn)行任務(wù)分配

B. master-slave部署，由master來(lái)分配任務(wù)

C. 不借助任何中間件，且所有節(jié)點(diǎn)均等。通過(guò)數(shù)據(jù)庫(kù)的update returning，從而實(shí)現(xiàn)節(jié)點(diǎn)之間任務(wù)的互斥

面試題012：有一批氣象觀測(cè)站，現(xiàn)需要獲取這些站點(diǎn)的觀測(cè)數(shù)據(jù)，并存儲(chǔ)到Hive中。但是氣象局只提供了api查詢，每次只能查詢單個(gè)觀測(cè)點(diǎn)。那么如果能夠方便快速地獲取到所有的觀測(cè)點(diǎn)的數(shù)據(jù)？

——阿里巴巴出題專家：江嵐／阿里巴巴數(shù)據(jù)技術(shù)高級(jí)技術(shù)專家

參考答案

A. 通過(guò)shell或python等調(diào)用api，結(jié)果先暫存本地，最后將本地文件上傳到Hive中。

B. 通過(guò)datax的httpReader和hdfsWriter插件，從而獲取所需的數(shù)據(jù)。

C. 比較理想的回答，是在計(jì)算引擎的UDF中調(diào)用查詢api，執(zhí)行UDF的查詢結(jié)果存儲(chǔ)到對(duì)應(yīng)的表中。一方面，不需要同步任務(wù)的導(dǎo)出導(dǎo)入；另一方面，計(jì)算引擎的分布式框架天生提供了分布式、容錯(cuò)、并發(fā)等特性。

面試題013 如何實(shí)現(xiàn)兩金額數(shù)據(jù)相加（最多小數(shù)點(diǎn)兩位）？

——阿里巴巴出題專家：御術(shù)／螞蟻金服數(shù)據(jù)可視化高級(jí)技術(shù)專家

參考答案

其實(shí)問(wèn)題并不難，就是考察候選人對(duì) JavaScript 數(shù)據(jù)運(yùn)算上的認(rèn)知以及考慮問(wèn)題的縝密程度，有很多坑，可以用在筆試題，如果用在面試，回答過(guò)程中還可以隨機(jī)加入有很多計(jì)算機(jī)基礎(chǔ)的延伸。

回到這個(gè)問(wèn)題，由于直接浮點(diǎn)相 yu 加會(huì)失精，所以要轉(zhuǎn)整數(shù)；（可以插入問(wèn)遇到過(guò)嗎？是否可以舉個(gè)例子？）。

轉(zhuǎn)整數(shù)是第一個(gè)坑，雖然只有兩位可以通過(guò)乘以100轉(zhuǎn)整數(shù)，但由于乘以一百和除以一百都會(huì)出現(xiàn)浮點(diǎn)數(shù)的運(yùn)算，所以也會(huì)失精，還是要通過(guò)字符串來(lái)轉(zhuǎn)；（可以插入問(wèn)字符串轉(zhuǎn)整數(shù)有幾種方式？）

字符串轉(zhuǎn)整是第二個(gè)坑，因?yàn)樽詈笠獙?duì)齊計(jì)算，如果沒考慮周全先 toFixed(2)，對(duì)于只有一位小數(shù)點(diǎn)數(shù)據(jù)進(jìn)入計(jì)算就會(huì)錯(cuò)誤；轉(zhuǎn)整數(shù)后的計(jì)算是個(gè)加分點(diǎn)，很多同學(xué)往往就是直接算了，如果可以考慮大數(shù)計(jì)算的場(chǎng)景，恭喜同學(xué)進(jìn)入隱藏關(guān)卡，這就會(huì)涉及如何有效循環(huán)、遍歷、算法復(fù)雜度的問(wèn)題。

面試題014：關(guān)于并行計(jì)算的一些基礎(chǔ)開放問(wèn)題。

——阿里巴巴出題專家：何萬(wàn)青／阿里云高性能計(jì)算資深技術(shù)專家

? 如何定義并計(jì)算，請(qǐng)分別闡述分布式內(nèi)存到共享內(nèi)存模式行編程的區(qū)別和實(shí)現(xiàn)（例子代碼）？

? 請(qǐng)使用MPI和OpenMP分別實(shí)現(xiàn)N個(gè)處理器對(duì)M個(gè)變量的求和？

? 請(qǐng)說(shuō)明SIMD指令在循環(huán)中使用的權(quán)限？向量化優(yōu)化有哪些手段？

? 請(qǐng)用Amdahl定律說(shuō)明什么是并行效率以及并行算法的擴(kuò)展性？并說(shuō)明擴(kuò)展性的性能指標(biāo)和限制因素，最后請(qǐng)說(shuō)明在共享內(nèi)存計(jì)算機(jī)中，共享內(nèi)存的限制？OpenMP是怎樣實(shí)現(xiàn)共享內(nèi)存編程環(huán)境的？MPI阻塞和非阻塞讀寫的區(qū)別？

參考答案

（簡(jiǎn)要答案，但必須觸及，可以展開）

? 同時(shí)執(zhí)行多個(gè)/算法/邏輯操作/內(nèi)存訪問(wèn)/IO，相互獨(dú)立同時(shí)運(yùn)行，分三個(gè)層次：進(jìn)程級(jí)，多個(gè)節(jié)點(diǎn)分布式內(nèi)存通過(guò)MPI通信并行；線程級(jí)，共享內(nèi)存的多路機(jī)器，通過(guò)OpenMP實(shí)現(xiàn)多線程并行；指令集：通過(guò)SIMD指令實(shí)現(xiàn)單指令多數(shù)據(jù)。。。。舉例吧啦吧啦。

? MPI代碼，，，OpenMP代碼，分別寫出來(lái) M個(gè)元素，N個(gè)處理器的累加，后者注意private 參數(shù)。

SIMD在循環(huán)中的應(yīng)用，限制在于 SIMD指令處理的每一個(gè)數(shù)組的長(zhǎng)度，cache line利用，內(nèi)部循環(huán)間的依賴和條件調(diào)用等。

? 向量化，主要看SSE和AVX指令占比率，通過(guò)編譯器優(yōu)化。。。。在loop代碼中使用，

? 性能和計(jì)算規(guī)模隨處理器增加的變化曲線，實(shí)測(cè)HPL和峰值HPL比率，能用用Amdahl定律表達(dá) Tpar(N) = (an + (1-a)n/N )t + C (n,N), 能夠講明白串行部分對(duì)整個(gè)并行的天花板效應(yīng)，擴(kuò)展性能夠解釋清楚算法的擴(kuò)展性=并行效率隨處理器數(shù)目的變化關(guān)系，畫出來(lái)。

? 共享內(nèi)存計(jì)算機(jī)OpenMP對(duì)變量的限制描述，EREW，CREW，ERCW，CRCW等區(qū)別，NUMA概念，如何保持coherent等。

? 寫出OpenMP和MPI的核心函數(shù)，回答問(wèn)題即可。

面試題015：請(qǐng)計(jì)算XILINX公司VU9P芯片的算力相當(dāng)于多少TOPS，給出計(jì)算過(guò)程與公式。

——阿里巴巴出題專家：隱達(dá)／阿里云異構(gòu)計(jì)算資深專家

參考答案

基于不同的算法，這個(gè)值在十幾到幾百之間。但是，如果只是單純比算力，FPGA和ASIC、GPU相比并無(wú)太大優(yōu)勢(shì)，甚至大多時(shí)候有較大劣勢(shì)。FPGA的優(yōu)勢(shì)在于高度的靈活性和算法的針對(duì)性。

面試題016：一顆現(xiàn)代處理器，每秒大概可以執(zhí)行多少條簡(jiǎn)單的MOV指令，有哪些主要的影響因素？

——阿里巴巴出題專家：子團(tuán)／創(chuàng)新產(chǎn)品虛擬化&穩(wěn)定性資深技術(shù)專家

參考答案

及格：

每執(zhí)行一條mov指令需要消耗1個(gè)時(shí)鐘周期，所以每秒執(zhí)行的mov指令和CPU主頻相關(guān)。

加分：

在CPU微架構(gòu)上，要考慮數(shù)據(jù)預(yù)取，亂序執(zhí)行，多發(fā)射，內(nèi)存stall (前端stall和后端stall)等諸多因素，因此除了cpu主頻外，還和流水線上的效率(IPC)強(qiáng)相關(guān)，比較復(fù)雜的一個(gè)問(wèn)題。

面試題017：請(qǐng)分析MaxCompute產(chǎn)品與分布式技術(shù)的關(guān)系、當(dāng)前大數(shù)據(jù)計(jì)算平臺(tái)類產(chǎn)品的市場(chǎng)現(xiàn)狀和發(fā)展趨勢(shì)。

——阿里巴巴出題專家：云郎／阿里MaxCompute高級(jí)產(chǎn)品專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題018：對(duì)大數(shù)據(jù)平臺(tái)中的元數(shù)據(jù)管理是怎么理解的，元數(shù)據(jù)收集管理體系是怎么樣的，會(huì)對(duì)大數(shù)據(jù)應(yīng)用有什么樣的影響。

——阿里巴巴出題專家：映泉／阿里巴巴高級(jí)技術(shù)專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題019：你理解常見如阿里，和友商大數(shù)據(jù)平臺(tái)的技術(shù)體系差異以及發(fā)展趨勢(shì)和技術(shù)瓶頸，在存儲(chǔ)和計(jì)算兩個(gè)方面進(jìn)行概述。

——阿里巴巴出題專家：映泉／阿里巴巴高級(jí)技術(shù)專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題020：在云計(jì)算大數(shù)據(jù)處理場(chǎng)景中，每天運(yùn)行著成千上萬(wàn)的任務(wù)，每個(gè)任務(wù)都要進(jìn)行IO讀寫。存儲(chǔ)系統(tǒng)為了更好的服務(wù)，經(jīng)常會(huì)保證高優(yōu)先級(jí)的任務(wù)優(yōu)先執(zhí)行。當(dāng)多個(gè)作業(yè)或用戶訪問(wèn)存儲(chǔ)系統(tǒng)時(shí)，如何保證優(yōu)先級(jí)和公平性。

——阿里巴巴出題專家：田磊磊／阿里云文件存儲(chǔ)高級(jí)技術(shù)專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題 021：最大頻率棧。

——阿里巴巴出題專家：屹平／阿里云視頻云邊緣計(jì)算高級(jí)技術(shù)專家

實(shí)現(xiàn) FreqStack，模擬類似棧的數(shù)據(jù)結(jié)構(gòu)的操作的一個(gè)類。FreqStack 有兩個(gè)函數(shù)： push(int x)，將整數(shù) x 推入棧中。pop()，它移除并返回棧中出現(xiàn)最頻繁的元素。如果最頻繁的元素不只一個(gè)，則移除并返回最接近棧頂?shù)脑亍?/p>

示例：

push [5,7,5,7,4,5]

pop() -> 返回 5，因?yàn)?5 是出現(xiàn)頻率最高的。 棧變成 [5,7,5,7,4]。

pop() -> 返回 7，因?yàn)?5 和 7 都是頻率最高的，但 7 最接近棧頂。 棧變成 [5,7,5,4]。

pop() -> 返回 5 。 棧變成 [5,7,4]。

pop() -> 返回 4 。 棧變成 [5,7]。

參考答案

令 freq 作為x的出現(xiàn)次數(shù)的映射 Map。

此外maxfreq，即棧中任意元素的當(dāng)前最大頻率，因?yàn)槲覀儽仨殢棾鲱l率最高的元素。

當(dāng)前主要的問(wèn)題就變成了：在具有相同的（最大）頻率的元素中，怎么判斷那個(gè)元素是最新的？我們可以使用棧來(lái)查詢這一信息：靠近棧頂?shù)脑乜偸窍鄬?duì)更新一些。

為此，我們令 group 作為從頻率到具有該頻率的元素的映射。到目前，我們已經(jīng)實(shí)現(xiàn)了 FreqStack 的所有必要的組件。

算法：

實(shí)際上，作為實(shí)現(xiàn)層面上的一點(diǎn)細(xì)節(jié)，如果 x 的頻率為 f，那么我們將獲取在所有 group[i] (i <= f) 中的 x,而不僅僅是棧頂?shù)哪莻€(gè)。這是因?yàn)槊總€(gè) group[i] 都會(huì)存儲(chǔ)與第 i 個(gè) x 副本相關(guān)的信息。

最后，我們僅僅需要如上所述維持 freq，group，以及 maxfreq。

代碼示例：

class FreqStack {Map freq;Map> group;int maxfreq;public FreqStack() {freq = new HashMap();group = new HashMap();maxfreq = 0;}public void push(int x) {int f = freq.getOrDefault(x, 0) + 1;freq.put(x, f);if (f > maxfreq)maxfreq = f;group.computeIfAbsent(f, z-> new Stack()).push(x);}public int pop() {int x = group.get(maxfreq).pop();freq.put(x, freq.get(x) - 1);if (group.get(maxfreq).size() == 0)maxfreq--;return x;}}

復(fù)雜度分析：

時(shí)間復(fù)雜度：對(duì)于 push 和 pop 操作， O(1)。

空間復(fù)雜度： O(N)，其中 N 為 FreqStack 中元素的數(shù)目。

面試題022：給定一個(gè)鏈表，刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

——阿里巴巴出題專家：屹平／阿里云視頻云邊緣計(jì)算高級(jí)技術(shù)專家

? 示例：

給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.

當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.

說(shuō)明：

給定的 n 保證是有效的。

要求：

只允許對(duì)鏈表進(jìn)行一次遍歷。

參考答案

我們可以使用兩個(gè)指針而不是一個(gè)指針。第一個(gè)指針從列表的開頭向前移動(dòng) n+1n+1 步，而第二個(gè)指針將從列表的開頭出發(fā)?，F(xiàn)在，這兩個(gè)指針被 nn 個(gè)結(jié)點(diǎn)分開。我們通過(guò)同時(shí)移動(dòng)兩個(gè)指針向前來(lái)保持這個(gè)恒定的間隔，直到第一個(gè)指針到達(dá)最后一個(gè)結(jié)點(diǎn)。此時(shí)第二個(gè)指針將指向從最后一個(gè)結(jié)點(diǎn)數(shù)起的第 nn 個(gè)結(jié)點(diǎn)。我們重新鏈接第二個(gè)指針?biāo)玫慕Y(jié)點(diǎn)的 next 指針指向該結(jié)點(diǎn)的下下個(gè)結(jié)點(diǎn)。

代碼示例：

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode first = dummy;ListNode second = dummy;// Advances first pointer so that the gap between first and second is n nodes apartfor (int i = 1; i <= n + 1; i++) {first = first.next;}// Move first to the end, maintaining the gapwhile (first != null) {first = first.next;second = second.next;}second.next = second.next.next;return dummy.next;}

復(fù)雜度分析：

*時(shí)間復(fù)雜度：O(L)，該算法對(duì)含有 L 個(gè)結(jié)點(diǎn)的列表進(jìn)行了一次遍歷。因此時(shí)間復(fù)雜度為 O(L)。

*空間復(fù)雜度：O(1)，我們只用了常量級(jí)的額外空間。

面試題023：如果讓你設(shè)計(jì)一個(gè)通用的、支持各種數(shù)據(jù)庫(kù)秒級(jí)備份和恢復(fù)的系統(tǒng)，你會(huì)如何設(shè)計(jì)？

——阿里巴巴出題專家：千震／阿里云數(shù)據(jù)庫(kù)高級(jí)技術(shù)專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題024：如果讓你來(lái)設(shè)計(jì)一個(gè)支持?jǐn)?shù)據(jù)庫(kù)、NOSQL和大數(shù)據(jù)之間數(shù)據(jù)實(shí)時(shí)流動(dòng)的數(shù)據(jù)流及處理的系統(tǒng)，你會(huì)考慮哪些問(wèn)題？如何設(shè)計(jì)？

——阿里巴巴出題專家：千震／阿里云數(shù)據(jù)庫(kù)高級(jí)技術(shù)專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題025：給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù)，返回兩個(gè)數(shù)組的索引，這兩個(gè)索引指向的數(shù)字的加和等于指定的整數(shù)。需要最優(yōu)的算法，分析算法的空間和時(shí)間復(fù)雜度。

——阿里巴巴出題專家：龍欣／異構(gòu)計(jì)算資深技術(shù)專家

參考答案

開放性問(wèn)題，無(wú)標(biāo)準(zhǔn)答案。

面試題026：假如給你一個(gè)新產(chǎn)品，你將從哪些方面來(lái)保障它的質(zhì)量？

——阿里巴巴出題專家：晨暉 ／阿里云中間件技術(shù)部測(cè)試開發(fā)專家

參考答案

可以從代碼開發(fā)、測(cè)試保障、線上質(zhì)量三個(gè)方面來(lái)保障。

在代碼開發(fā)階段，有單元測(cè)試、代碼Review、靜態(tài)代碼掃描等；測(cè)試保障階段，有功能測(cè)試、性能測(cè)試、高可用測(cè)試、穩(wěn)定性測(cè)試、兼容性測(cè)試等；在線上質(zhì)量方面，有灰度發(fā)布、緊急回滾、故障演練、線上監(jiān)控和巡檢等。

面試題027：如何用socket編程實(shí)現(xiàn)ftp協(xié)議？

——阿里巴巴出題專家：吳明／阿里云彈性計(jì)算資深技術(shù)專家

參考答案

https://www.jianshu.com/p/e9a2e0755496

面試題028：請(qǐng)?jiān)u估一下程序的執(zhí)行結(jié)果？

——阿里巴巴出題專家：桃谷／阿里云中間件技術(shù)專家

public class SynchronousQueueQuiz { public static void main(String[] args) throws Exception {BlockingQueue queue = new SynchronousQueue<>(); System.out.print(queue.offer(1) + " "); System.out.print(queue.offer(2) + " "); System.out.print(queue.offer(3) + " "); System.out.print(queue.take() + " "); System.out.println(queue.size()); } }

A. true true true 1 3

B. true true true (阻塞)

C. false false false null 0

D. false false false (阻塞)

參考答案 D