備戰秋招——演算法與數據結構（15）

1. shell指令碼統計檔案中單詞的個數

方法一：
（1）cat file|sed ‘s/[,.:;/!?]/ /g’|awk ‘{for(i=1;i<=NF;i++)array[KaTeX parse error: Expected 'EOF', got '}' at position 6: i]++;}̲ END{for(i in a…i]++;}
END{for(i in array) print i,array[i]}’
#（1）和（2）效果一致。

方法二：
（1）awk ‘BEGIN{RS="[,.:;/!?]"}{for(i=1;i<=NF;i++)array[$i]++;}
END{for(i in array) print i,array[i]}’ file

2. redis的物件型別有哪些，底層的數據結構。（主要是有序列表的底層實現）

Redis的五大數據型別也稱五大數據物件；前面介紹過6大數據結構，Redis並沒有直 接使用這些結構來實現鍵值對數據庫，而是使用這些結構構建了一個物件系統 redisObject；這個物件系統包含了五大數據物件，字串物件（string）、列表物件 （list）、雜湊物件（hash）、集合（set）物件和有序集合物件（zset）；而這五大 物件的底層數據編碼可以用命令OBJECT ENCODING來進行檢視。
1.字串物件(string):字串物件底層數據結構實現爲簡單動態字串（SDS）和直接 儲存，但其編碼方式 可以是int、raw或者embstr，區別在於記憶體結構的不同。
2.列表物件(list):列表物件的編碼可以是ziplist和linkedlist。
3.雜湊物件(hash):雜湊物件的編碼可以是ziplist和hashtable。
4.集合物件(set):集合物件的編碼可以是intset和hashtable。
5.有序集合物件(zset):有序集合的編碼可以是ziplist和skiplist。
（1）ziplist編碼
ziplist編碼的有序集合物件底層實現是壓縮列表，其結構與雜湊物件類似，不同的是 兩個緊密相連的壓縮列表節點，第一個儲存元素的成員，第二個儲存元素的分值，而且 分值小的靠近表頭，大的靠近表尾。

（2）skiplist編碼
skiplist編碼的有序集合物件底層實現是跳躍表和字典兩種；
每個跳躍表節點都儲存一個集合元素，並按分值從小到大排列；節點的object屬性保 存了元素的成員，score屬性儲存分值；
字典的每個鍵值對儲存一個集合元素，字典的鍵儲存元素的成員，字典的值儲存分值。

skiplist編碼同時使用跳躍表和字典實現的原因
跳躍表優點是有序，但是查詢分值複雜度爲O(logn)；字典查詢分值複雜度爲O(1) ， 但是無序，所以結合連個結構的有點進行實現。
雖然採用兩個結構但是集合的元素成員和分值是共用的，兩種結構通過指針指向同一地 址，不會浪費記憶體。
有序集合編碼轉換：
有序集合物件使用ziplist編碼需要滿足兩個條件：一是所有元素長度小於64位元組； 二是元素個數小於128個；不滿足任意一條件將使用skiplist編碼。
以上兩個條件可以在Redis組態檔中修改zset-max-ziplist-entries選項和 zset-max-ziplist-value選項。

需要完整版一線網際網路大廠面試題以及關於c++ Linux後臺伺服器開發的一些知識點分享：Linux，Nginx，MySQL，Redis，P2P，K8S，Docker，TCP/IP，協程，DPDK，webrtc，音視訊等等視訊。
vx關注零聲學院公衆號領取！

3. linux下IPC有哪些

①匿名管道（PIPE）和有名管道（FIFO）：最簡單
②信號（SIGNAL）：系統的開銷最小
③共用對映區（MMAP）：可以在無血緣關係的進程間通訊
④本地通訊端（SOCKET）：最穩定（但是比較複雜）

4. vector記憶體增長方式

vector的實現通常會分配比新的空間需求更大的記憶體空間。容器預留這些空間作爲備 用，從而用來儲存更多新的元素。這樣，就不需要每次新增新的元素都重新分配容器的 記憶體空間了。
在插入新元素時，若遇到已分配容量不足的情況，會自動拓展容量大小，而這個拓展容 量的過程爲：
開闢另外一塊更大的記憶體空間，該空間大小通常爲原空間大小的兩倍(理論分析上是 1.5最好，但從時間和空間上綜合考慮，一般取2)；
將原記憶體空間中的數據拷貝到新開闢的記憶體空間中；
解構原記憶體空間的數據，釋放原記憶體空間，並調整各種指針指向新記憶體空間。
vector型別提供了一些成員函數，允許我們與它的現實中記憶體分配部分互動。
c.capacity() 不重新分配記憶體空間的話，c可以儲存多少元素
c.reserve(n) 分配至少能容納n個元素的記憶體空間
c.shrink_to_fit() 將capacity()減少爲size()相同大小,size()爲vector已經儲存元素個數。