在CSDN上看到這哥的后臺開發(fā)面試問題整理，覆蓋面還算比較全，這里拿出來強答一發(fā)。這里，我可能會額外加入幾個自己想到的試題。
題目列表
- 了解哪幾種排序方式？有沒有 O(n) 的排序
- 平衡二叉樹的插入
- 二叉查找樹
- 10 個 G 的最高訪問 Ip 統(tǒng)計
- 倒排索引
- 常用緩存置換算法
- Lru算法的實現(xiàn)及優(yōu)化
- 堆和棧的區(qū)別
- 常用 hash 算法
- md5、sha1 的實現(xiàn)
- 一萬個 url 的快速查找
- 兩個有序數(shù)組找并集的優(yōu)化
- 10億個整數(shù)中找最大的 100 個，用 O(n)
- RSA加密原理（附加）
題解
了解哪幾種排序方式？有沒有 O(n) 的排序
- 冒泡排序、快速排序、堆排序、直接（或二分）插入排序、希爾排序、歸并排序、基數(shù)排序
- 在一些限制條件下有O(n)的排序
平衡二叉樹的插入
看這里吧?？偨Y(jié)旋轉(zhuǎn)的4條規(guī)則
- LL旋轉(zhuǎn)
- RR旋轉(zhuǎn)
- LR旋轉(zhuǎn) 先左子樹RR，自己再LL
- RL旋轉(zhuǎn) 先右子樹LL，自己再RR
二叉查找樹。
這題是要干嘛?。?！還是不管他了！
讓來面試的自稱有男朋友的妹紙用C語言實現(xiàn)一個紅黑樹吧。
10 個 G 的最高訪問 Ip 統(tǒng)計
10個G的IP，如果4字節(jié)一個來算的話，大約250億個。
- 如果重復率高，內(nèi)存足夠，直接用hash表計數(shù)即可
- 如果重復率低，那就先將10G文件通過hash分組到多個文件中，之后分別對每個文件進行hash計數(shù)。
倒排索引
引用wiki
倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。
有兩種不同的反向索引形式：
- 一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
- 一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創(chuàng)建。
常用緩存置換算法
- FIFO 先進先出 常規(guī)實現(xiàn) 隊列
- LRU Least Recently Used 最近最久未使用算法 常規(guī)實現(xiàn) 鏈表
- LFU Least Frequently Used 最近最少使用算法 常規(guī)實現(xiàn) 小頂堆
Lru算法的實現(xiàn)及優(yōu)化
常規(guī)實現(xiàn)是一個雙向鏈接+hashmap。時間復雜度為O(1)，基本上沒什么優(yōu)化空間了。
通常優(yōu)化會集中在內(nèi)存方面，即雙向鏈接這塊的內(nèi)存占用。如redis會會使用近似lru算法來優(yōu)化掉雙向鏈表
堆和棧的區(qū)別
不知道這題為啥被放到了這里。
- stack區(qū) 由編譯器自動分配釋放，為連續(xù)的空間，向底地址增長，存放局部變量，函數(shù)參數(shù)等數(shù)據(jù)。
- heap區(qū) 一般由程序員主要分配釋放，如malloc，free，new，delete。分配方式類似鏈表，底層通過調(diào)用brk和mmap進行分配
- 理論上stack區(qū)的數(shù)據(jù)操作效率比heap區(qū)要高
常用 hash 算法
- 復雜散列算法如md5，sha1
- 簡單散列算法如ELF，SDBM，RS，F(xiàn)NV等
md5、sha1 的實現(xiàn)
不至于真考這種題吧，汗！
一萬個 url 的快速查找
一萬個 url，扔hash表里不就好了。沒明白這題是想考啥。不像是要考trie，AC自動機這些東西
兩個有序數(shù)組找并集的優(yōu)化
歸并的思路，時間復雜度最壞的情況 O(max(m,n)) 了，沒得優(yōu)化了。
10億個整數(shù)中找最大的 100 個，用 O(n)
真正的 O(n) 誰能做到麻煩告知下
- TopN問題，常規(guī)思路是用一個堆，之后不斷地取新數(shù)據(jù)更新這個堆，更新完后即可得到結(jié)果。但這個復雜度是 O(nlgm)
- 如果整數(shù)的范圍不大，內(nèi)存也足夠的話，可以用一個char數(shù)組來計數(shù)。之后倒序找出最大的100個。這個理論上能在 O(n) 內(nèi)。
RSA加密原理（附加）
歐拉函數(shù)n有比它小的互質(zhì)數(shù)的個數(shù)Phi(n)=n*(1-1/p1)(1-1/p2)... p是其質(zhì)因數(shù)
歐拉定理a與n互質(zhì)則(a^Phi(n))%n==1 => (a^(p-1))%p=1（p質(zhì)數(shù)）
質(zhì)數(shù)p,q，p!=q，N=pq，r=(p-1)(q-1)
選擇一個e（e<r），求得e關(guān)于模r的模反元素d
(N,e)是公鑰，(N,d)是私鑰
加密ne ≡ c (mod N) 解密cd ≡ n (mod N) （n為信息，c為加密結(jié)果）
cd ≡ n e·d(mod N)
作者原創(chuàng)，轉(zhuǎn)載請注明出處
