1、kafka的message包括哪些信息

一個(gè)Kafka的Message由一個(gè)固定長度的header和一個(gè)變長的消息體body組成

header部分由一個(gè)字節(jié)的magic(文件格式)和四個(gè)字節(jié)的CRC32(用于判斷body消息體是否正常)構(gòu)成。

當(dāng)magic的值為1的時(shí)候，會在magic和crc32之間多一個(gè)字節(jié)的數(shù)據(jù)：attributes(保存一些相關(guān)屬性，

比如是否壓縮、壓縮格式等等);如果magic的值為0，那么不存在attributes屬性

body是由N個(gè)字節(jié)構(gòu)成的一個(gè)消息體，包含了具體的key/value消息

2、怎么查看kafka的offset

0.9版本以上，可以用最新的Consumer client 客戶端，有consumer.seekToEnd() / consumer.position() 可以用于得到當(dāng)前最新的offset：

3、hadoop的shuffle過程

一、Map端的shuffle

Map端會處理輸入數(shù)據(jù)并產(chǎn)生中間結(jié)果，這個(gè)中間結(jié)果會寫到本地磁盤，而不是HDFS。每個(gè)Map的輸出會先寫到內(nèi)存緩沖區(qū)中，當(dāng)寫入的數(shù)據(jù)達(dá)到設(shè)定的閾值時(shí)，系統(tǒng)將會啟動一個(gè)線程將緩沖區(qū)的數(shù)據(jù)寫到磁盤，這個(gè)過程叫做spill。

在spill寫入之前，會先進(jìn)行二次排序，首先根據(jù)數(shù)據(jù)所屬的partition進(jìn)行排序，然后每個(gè)partition中的數(shù)據(jù)再按key來排序。partition的目是將記錄劃分到不同的Reducer上去，以期望能夠達(dá)到負(fù)載均衡，以后的Reducer就會根據(jù)partition來讀取自己對應(yīng)的數(shù)據(jù)。接著運(yùn)行combiner(如果設(shè)置了的話)，combiner的本質(zhì)也是一個(gè)Reducer，其目的是對將要寫入到磁盤上的文件先進(jìn)行一次處理，這樣，寫入到磁盤的數(shù)據(jù)量就會減少。最后將數(shù)據(jù)寫到本地磁盤產(chǎn)生spill文件(spill文件保存在{mapred.local.dir}指定的目錄中，Map任務(wù)結(jié)束后就會被刪除)。

最后，每個(gè)Map任務(wù)可能產(chǎn)生多個(gè)spill文件，在每個(gè)Map任務(wù)完成前，會通過多路歸并算法將這些spill文件歸并成一個(gè)文件。至此，Map的shuffle過程就結(jié)束了。

二、Reduce端的shuffle

Reduce端的shuffle主要包括三個(gè)階段，copy、sort(merge)和reduce。

首先要將Map端產(chǎn)生的輸出文件拷貝到Reduce端，但每個(gè)Reducer如何知道自己應(yīng)該處理哪些數(shù)據(jù)呢?因?yàn)镸ap端進(jìn)行partition的時(shí)候，實(shí)際上就相當(dāng)于指定了每個(gè)Reducer要處理的數(shù)據(jù)(partition就對應(yīng)了Reducer)，所以Reducer在拷貝數(shù)據(jù)的時(shí)候只需拷貝與自己對應(yīng)的partition中的數(shù)據(jù)即可。每個(gè)Reducer會處理一個(gè)或者多個(gè)partition，但需要先將自己對應(yīng)的partition中的數(shù)據(jù)從每個(gè)Map的輸出結(jié)果中拷貝過來。

接下來就是sort階段，也成為merge階段，因?yàn)檫@個(gè)階段的主要工作是執(zhí)行了歸并排序。從Map端拷貝到Reduce端的數(shù)據(jù)都是有序的，所以很適合歸并排序。最終在Reduce端生成一個(gè)較大的文件作為Reduce的輸入。

最后就是Reduce過程了，在這個(gè)過程中產(chǎn)生了最終的輸出結(jié)果，并將其寫到HDFS上。

4、spark集群運(yùn)算的模式

Spark 有很多種模式，最簡單就是單機(jī)本地模式，還有單機(jī)偽分布式模式，復(fù)雜的則運(yùn)行在集群中，目前能很好的運(yùn)行在 Yarn和 Mesos 中，當(dāng)然 Spark 還有自帶的 Standalone 模式，對于大多數(shù)情況 Standalone 模式就足夠了，如果企業(yè)已經(jīng)有 Yarn 或者 Mesos 環(huán)境，也是很方便部署的。

• standalone(集群模式)：典型的Mater/slave模式，不過也能看出Master是有單點(diǎn)故障的;Spark支持ZooKeeper來實(shí)現(xiàn) HA
• on yarn(集群模式)： 運(yùn)行在 yarn 資源管理器框架之上，由 yarn 負(fù)責(zé)資源管理，Spark 負(fù)責(zé)任務(wù)調(diào)度和計(jì)算
• on mesos(集群模式)： 運(yùn)行在 mesos 資源管理器框架之上，由 mesos 負(fù)責(zé)資源管理，Spark 負(fù)責(zé)任務(wù)調(diào)度和計(jì)算
• on cloud(集群模式)：比如 AWS 的 EC2，使用這個(gè)模式能很方便的訪問 Amazon的 S3;Spark 支持多種分布式存儲系統(tǒng)：HDFS 和 S3

5、HDFS讀寫數(shù)據(jù)的過程

讀：

1. 跟namenode通信查詢元數(shù)據(jù)，找到文件塊所在的datanode服務(wù)器
2. 挑選一臺datanode(就近原則，然后隨機(jī))服務(wù)器，請求建立socket流
3. datanode開始發(fā)送數(shù)據(jù)(從磁盤里面讀取數(shù)據(jù)放入流，以packet為單位來做校驗(yàn))
4. 客戶端以packet為單位接收，現(xiàn)在本地緩存，然后寫入目標(biāo)文件

寫：

1. 根namenode通信請求上傳文件，namenode檢查目標(biāo)文件是否已存在，父目錄是否存在
2. namenode返回是否可以上傳
3. client請求第一個(gè) block該傳輸?shù)侥男ヾatanode服務(wù)器上
4. namenode返回3個(gè)datanode服務(wù)器ABC
5. client請求3臺dn中的一臺A上傳數(shù)據(jù)(本質(zhì)上是一個(gè)RPC調(diào)用，建立pipeline)，A收到請求會繼續(xù)調(diào)用B，然后B調(diào)用C，將真?zhèn)€pipeline建立完成，逐級返回客戶端
6. client開始往A上傳第一個(gè)block(先從磁盤讀取數(shù)據(jù)放到一個(gè)本地內(nèi)存緩存)，以packet為單位，A收到一個(gè)packet就會傳給B，B傳給C;A每傳一個(gè)packet會放入一個(gè)應(yīng)答隊(duì)列等待應(yīng)答
7. 當(dāng)一個(gè)block傳輸完成之后，client再次請求namenode上傳第二個(gè)block的服務(wù)器。

6、RDD中reduceBykey與groupByKey哪個(gè)性能好，為什么

• reduceByKey：reduceByKey會在結(jié)果發(fā)送至reducer之前會對每個(gè)mapper在本地進(jìn)行merge，有點(diǎn)類似于在MapReduce中的combiner。這樣做的好處在于，在map端進(jìn)行一次reduce之后，數(shù)據(jù)量會大幅度減小，從而減小傳輸，保證reduce端能夠更快的進(jìn)行結(jié)果計(jì)算。
• groupByKey：groupByKey會對每一個(gè)RDD中的value值進(jìn)行聚合形成一個(gè)序列(Iterator)，此操作發(fā)生在reduce端，所以勢必會將所有的數(shù)據(jù)通過網(wǎng)絡(luò)進(jìn)行傳輸，造成不必要的浪費(fèi)。同時(shí)如果數(shù)據(jù)量十分大，可能還會造成OutOfMemoryError。

通過以上對比可以發(fā)現(xiàn)在進(jìn)行大量數(shù)據(jù)的reduce操作時(shí)候建議使用reduceByKey。不僅可以提高速度，還是可以防止使用groupByKey造成的內(nèi)存溢出問題。

7、spark2.0的了解

• 更簡單：ANSI SQL與更合理的API
• 速度更快：用Spark作為編譯器
• 更智能：Structured Streaming

8、rdd 怎么分區(qū)寬依賴和窄依賴

• 寬依賴：父RDD的分區(qū)被子RDD的多個(gè)分區(qū)使用 例如 groupByKey、reduceByKey、sortByKey等操作會產(chǎn)生寬依賴，會產(chǎn)生shuffle
• 窄依賴：父RDD的每個(gè)分區(qū)都只被子RDD的一個(gè)分區(qū)使用 例如map、filter、union等操作會產(chǎn)生窄依賴

9、spark streaming 讀取kafka數(shù)據(jù)的兩種方式

這兩種方式分別是：

Receiver-base

使用Kafka的高層次Consumer API來實(shí)現(xiàn)。receiver從Kafka中獲取的數(shù)據(jù)都存儲在Spark Executor的內(nèi)存中，然后Spark Streaming啟動的job會去處理那些數(shù)據(jù)。然而，在默認(rèn)的配置下，這種方式可能會因?yàn)榈讓拥氖《鴣G失數(shù)據(jù)。如果要啟用高可靠機(jī)制，讓數(shù)據(jù)零丟失，就必須啟用Spark Streaming的預(yù)寫日志機(jī)制(Write Ahead Log，WAL)。該機(jī)制會同步地將接收到的Kafka數(shù)據(jù)寫入分布式文件系統(tǒng)(比如HDFS)上的預(yù)寫日志中。所以，即使底層節(jié)點(diǎn)出現(xiàn)了失敗，也可以使用預(yù)寫日志中的數(shù)據(jù)進(jìn)行恢復(fù)。

Direct

Spark1.3中引入Direct方式，用來替代掉使用Receiver接收數(shù)據(jù)，這種方式會周期性地查詢Kafka，獲得每個(gè)topic+partition的最新的offset，從而定義每個(gè)batch的offset的范圍。當(dāng)處理數(shù)據(jù)的job啟動時(shí)，就會使用Kafka的簡單consumer api來獲取Kafka指定offset范圍的數(shù)據(jù)。

10、kafka的數(shù)據(jù)存在內(nèi)存還是磁盤

Kafka最核心的思想是使用磁盤，而不是使用內(nèi)存，可能所有人都會認(rèn)為，內(nèi)存的速度一定比磁盤快，我也不例外。在看了Kafka的設(shè)計(jì)思想，查閱了相應(yīng)資料再加上自己的測試后，發(fā)現(xiàn)磁盤的順序讀寫速度和內(nèi)存持平。

而且Linux對于磁盤的讀寫優(yōu)化也比較多，包括read-ahead和write-behind，磁盤緩存等。如果在內(nèi)存做這些操作的時(shí)候，一個(gè)是JAVA對象的內(nèi)存開銷很大，另一個(gè)是隨著堆內(nèi)存數(shù)據(jù)的增多，JAVA的GC時(shí)間會變得很長，使用磁盤操作有以下幾個(gè)好處：

• 磁盤緩存由Linux系統(tǒng)維護(hù)，減少了程序員的不少工作。
• 磁盤順序讀寫速度超過內(nèi)存隨機(jī)讀寫。
• JVM的GC效率低，內(nèi)存占用大。使用磁盤可以避免這一問題。
• 系統(tǒng)冷啟動后，磁盤緩存依然可用。

11、怎么解決kafka的數(shù)據(jù)丟失

producer端：

宏觀上看保證數(shù)據(jù)的可靠安全性，肯定是依據(jù)分區(qū)數(shù)做好數(shù)據(jù)備份，設(shè)立副本數(shù)。

broker端：

topic設(shè)置多分區(qū)，分區(qū)自適應(yīng)所在機(jī)器，為了讓各分區(qū)均勻分布在所在的broker中，分區(qū)數(shù)要大于broker數(shù)。

分區(qū)是kafka進(jìn)行并行讀寫的單位，是提升kafka速度的關(guān)鍵。

Consumer端

consumer端丟失消息的情形比較簡單：如果在消息處理完成前就提交了offset，那么就有可能造成數(shù)據(jù)的丟失。由于Kafka consumer默認(rèn)是自動提交位移的，所以在后臺提交位移前一定要保證消息被正常處理了，因此不建議采用很重的處理邏輯，如果處理耗時(shí)很長，則建議把邏輯放到另一個(gè)線程中去做。為了避免數(shù)據(jù)丟失，現(xiàn)給出兩點(diǎn)建議：

• enable.auto.commit=false 關(guān)閉自動提交位移
• 在消息被完整處理之后再手動提交位移

12、fsimage和edit的區(qū)別?

• 大家都知道namenode與secondary namenode 的關(guān)系，當(dāng)他們要進(jìn)行數(shù)據(jù)同步時(shí)叫做checkpoint時(shí)就用到了fsimage與edit，fsimage是保存最新的元數(shù)據(jù)的信息，當(dāng)fsimage數(shù)據(jù)到一定的大小事會去生成一個(gè)新的文件來保存元數(shù)據(jù)的信息，這個(gè)新的文件就是edit，edit會回滾最新的數(shù)據(jù)。

13、列舉幾個(gè)配置文件優(yōu)化?

1)Core-site.xml 文件的優(yōu)化

• a、fs.trash.interval，默認(rèn)值： 0;說明： 這個(gè)是開啟hdfs文件刪除自動轉(zhuǎn)移到垃圾箱的選項(xiàng)，值為垃圾箱文件清除時(shí)間。一般開啟這個(gè)會比較好，以防錯(cuò)誤刪除重要文件。單位是分鐘。
• b、dfs.namenode.handler.count，默認(rèn)值：10;說明：hadoop系統(tǒng)里啟動的任務(wù)線程數(shù)，這里改為40，同樣可以嘗試該值大小對效率的影響變化進(jìn)行最合適的值的設(shè)定。
• c、mapreduce.tasktracker.http.threads，默認(rèn)值：40;說明：map和reduce是通過http進(jìn)行數(shù)據(jù)傳輸?shù)?，這個(gè)是設(shè)置傳輸?shù)牟⑿芯€程數(shù)。

14、datanode 首次加入 cluster 的時(shí)候，如果 log 報(bào)告不兼容文件版本，那需要namenode 執(zhí)行格式化操作，這樣處理的原因是?

• 1)這樣處理是不合理的，因?yàn)槟敲?namenode 格式化操作，是對文件系統(tǒng)進(jìn)行格式化，namenode 格式化時(shí)清空 dfs/name 下空兩個(gè)目錄下的所有文件，之后，會在目錄 dfs.name.dir 下創(chuàng)建文件。
• 2)文本不兼容，有可能時(shí) namenode 與 datanode 的 數(shù)據(jù)里的 namespaceID、clusterID 不一致，找到兩個(gè) ID 位置，修改為一樣即可解決。

15、MapReduce 中排序發(fā)生在哪幾個(gè)階段?這些排序是否可以避免?為什么?

• 1)一個(gè) MapReduce 作業(yè)由 Map 階段和 Reduce 階段兩部分組成，這兩階段會對數(shù)據(jù)排序，從這個(gè)意義上說，MapReduce 框架本質(zhì)就是一個(gè) Distributed Sort。
• 2)在 Map 階段，Map Task 會在本地磁盤輸出一個(gè)按照 key 排序(采用的是快速排序)的文件(中間可能產(chǎn)生多個(gè)文件，但最終會合并成一個(gè))，在 Reduce 階段，每個(gè) Reduce Task 會對收到的數(shù)據(jù)排序，這樣，數(shù)據(jù)便按照 Key 分成了若干組，之后以組為單位交給 reduce()處理。
• 3)很多人的誤解在 Map 階段，如果不使用 Combiner便不會排序，這是錯(cuò)誤的，不管你用不用 Combiner，Map Task 均會對產(chǎn)生的數(shù)據(jù)排序(如果沒有 Reduce Task，則不會排序，實(shí)際上 Map 階段的排序就是為了減輕 Reduce端排序負(fù)載)。
• 4)由于這些排序是 MapReduce 自動完成的，用戶無法控制，因此，在hadoop 1.x 中無法避免，也不可以關(guān)閉，但 hadoop2.x 是可以關(guān)閉的。

16、hadoop的優(yōu)化?

• 1)優(yōu)化的思路可以從配置文件和系統(tǒng)以及代碼的設(shè)計(jì)思路來優(yōu)化
• 2)配置文件的優(yōu)化：調(diào)節(jié)適當(dāng)?shù)膮?shù)，在調(diào)參數(shù)時(shí)要進(jìn)行測試
• 3)代碼的優(yōu)化：combiner的個(gè)數(shù)盡量與reduce的個(gè)數(shù)相同，數(shù)據(jù)的類型保持一致，可以減少拆包與封包的進(jìn)度
• 4)系統(tǒng)的優(yōu)化：可以設(shè)置linux系統(tǒng)打開最大的文件數(shù)預(yù)計(jì)網(wǎng)絡(luò)的帶寬MTU的配置
• 5)為 job 添加一個(gè) Combiner，可以大大的減少shuffer階段的maoTask拷貝過來給遠(yuǎn)程的 reduce task的數(shù)據(jù)量，一般而言combiner與reduce相同。
• 6)在開發(fā)中盡量使用stringBuffer而不是string，string的模式是read-only的，如果對它進(jìn)行修改，會產(chǎn)生臨時(shí)的對象，二stringBuffer是可修改的，不會產(chǎn)生臨時(shí)對象。
• 7)修改一下配置：以下是修改 mapred-site.xml 文件

a、修改最大槽位數(shù)：槽位數(shù)是在各個(gè) tasktracker 上的 mapred-site.xml 上設(shè)置的，默認(rèn)都是 2 

property  
namemapred.tasktracker.map.tasks.maximum/name  
value2/value  
/property  
property  
namemapred.tasktracker.reduce.tasks.maximum/name  
value2/value  
/property 

b、調(diào)整心跳間隔：集群規(guī)模小于 300 時(shí)，心跳間隔為 300 毫秒

• mapreduce.jobtracker.heartbeat.interval.min 心跳時(shí)間
• mapred.heartbeats.in.second 集群每增加多少節(jié)點(diǎn)，時(shí)間增加下面的值
• mapreduce.jobtracker.heartbeat.scaling.factor 集群每增加上面的個(gè)數(shù)，心跳增多少

c、啟動帶外心跳

• mapreduce.tasktracker.outofband.heartbeat 默認(rèn)是 false

d、配置多塊磁盤

mapreduce.local.dir 

e、配置 RPC hander 數(shù)目

• mapred.job.tracker.handler.count 默認(rèn)是 10，可以改成 50，根據(jù)機(jī)器的能力

f、配置 HTTP 線程數(shù)目

• tasktracker.http.threads 默認(rèn)是 40，可以改成 100 根據(jù)機(jī)器的能力

g、選擇合適的壓縮方式，以 snappy 為例： 

property  
namemapred.compress.map.output/name  
valuetrue/value  
/property  
property  
namemapred.map.output.compression.codec/name  
valueorg.apache.hadoop.io.compress.SnappyCodec/value  
/property 

17、設(shè)計(jì)題

1)采集nginx產(chǎn)生的日志，日志的格式為user ip time url htmlId 每天產(chǎn)生的文件的數(shù)據(jù)量上億條，請?jiān)O(shè)計(jì)方案把數(shù)據(jù)保存到HDFS上，并提供一下實(shí)時(shí)查詢的功能(響應(yīng)時(shí)間小于3s)

A、某個(gè)用戶某天訪問某個(gè)URL的次數(shù)

B、某個(gè)URL某天被訪問的總次數(shù)

• 實(shí)時(shí)思路是：使用Logstash + Kafka + Spark-streaming + Redis + 報(bào)表展示平臺
• 離線的思路是：Logstash + Kafka + Elasticsearch + Spark-streaming + 關(guān)系型數(shù)據(jù)庫

A、B、數(shù)據(jù)在進(jìn)入到Spark-streaming 中進(jìn)行過濾，把符合要求的數(shù)據(jù)保存到Redis中

18、有 10 個(gè)文件，每個(gè)文件 1G，每個(gè)文件的每一行存放的都是用戶的 query，每個(gè)文件的query 都可能重復(fù)。要求你按照 query 的頻度排序。 還是典型的 TOP K 算法 ##，

解決方案如下：

1)方案 1：

順序讀取 10 個(gè)文件，按照 hash(query)%10 的結(jié)果將 query 寫入到另外 10 個(gè)文件(記為)中。這樣新生成的文件每個(gè)的大小大約也 1G(假設(shè) hash 函數(shù)是隨機(jī)的)。 找一臺內(nèi)存在 2G 左右的機(jī)器，依次對用 hash_map(query, query_count)來統(tǒng)計(jì)每個(gè)query 出現(xiàn)的次數(shù)。利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的 query 和對應(yīng)的 query_cout 輸出到文件中。這樣得到了 10 個(gè)排好序的文件(記為)。 對這 10 個(gè)文件進(jìn)行歸并排序(內(nèi)排序與外排序相結(jié)合)。

2)方案 2：

一般 query 的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對于所有的 query，一次性就可以加入到內(nèi)存了。這樣，我們就可以采用 trie 樹/hash_map等直接來統(tǒng)計(jì)每個(gè) query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。

3)方案 3：

與方案 1 類似，但在做完 hash，分成多個(gè)文件后，可以交給多個(gè)文件來處理，采用分布式的架構(gòu)來處理(比如 MapReduce)，最后再進(jìn)行合并。

19、在 2.5 億個(gè)整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這 2.5 億個(gè)整數(shù) 。

• 方案 1：采用 2-Bitmap(每個(gè)數(shù)分配 2bit，00 表示不存在，01 表示出現(xiàn)一次，10 表示多次，11 無意義)進(jìn)行，共需內(nèi)存 2^32 * 2 bit=1 GB 內(nèi)存，還可以接受。然后掃描這 2.5億個(gè)整數(shù)，查看 Bitmap 中相對應(yīng)位，如果是 00 變 01，01 變 10，10 保持不變。所描完事后，查看 bitmap，把對應(yīng)位是 01 的整數(shù)輸出即可。
• 方案 2：也可采用與第 1 題類似的方法，進(jìn)行劃分小文件的方法。然后在小文件中找出不重復(fù)的整數(shù)，并排序。然后再進(jìn)行歸并，注意去除重復(fù)的元素。

20、騰訊面試題：給 40 億個(gè)不重復(fù)的 unsigned int 的整數(shù)，沒排過序的，然后再給一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在那 40 億個(gè)數(shù)當(dāng)中? ##

方案 1：oo，申請 512M 的內(nèi)存，一個(gè) bit 位代表一個(gè) unsigned int 值。讀入 40 億個(gè)數(shù)，設(shè)置相應(yīng)的 bit 位，讀入要查詢的數(shù)，查看相應(yīng) bit 位是否為 1，為 1 表示存在，為 0 表示不存在。

方案 2：這個(gè)問題在《編程珠璣》里有很好的描述，大家可以參考下面的思路，探討一下： 又因?yàn)?2^32 為 40 億多，所以給定一個(gè)數(shù)可能在，也可能不在其中; 這里我們把 40 億個(gè)數(shù)中的每一個(gè)用 32 位的二進(jìn)制來表示 ，假設(shè)這 40 億個(gè)數(shù)開始放在一個(gè)文件中。 然后將這 40 億個(gè)數(shù)分成兩類:

• 1.最高位為 0
• 2.最高位為 1

并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)=20 億，而另一個(gè)=20 億(這相當(dāng)于折半了); 與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找 再然后把這個(gè)文件為又分成兩類:

• 1.次最高位為 0
• 2.次最高位為 1

并將這兩類分別寫入到兩個(gè)文件中，其中一個(gè)文件中數(shù)的個(gè)數(shù)=10 億，而另一個(gè)=10 億(這相當(dāng)于折半了); 與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找。

.....

以此類推，就可以找到了,而且時(shí)間復(fù)雜度為 O(logn)，方案 2 完。

3)附：這里，再簡單介紹下，位圖方法： 使用位圖法判斷整形數(shù)組是否存在重復(fù) ,判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時(shí)我們通常希望少進(jìn)行幾次掃描，這時(shí)雙重循環(huán)法就不可取了。

位圖法比較適合于這種情況，它的做法是按照集合中最大元素 max 創(chuàng)建一個(gè)長度為 max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上 1，如遇到 5 就給新數(shù)組的第六個(gè)元素置 1，這樣下次再遇到 5 想置位時(shí)發(fā)現(xiàn)新數(shù)組的第六個(gè)元素已經(jīng)是 1 了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這 種給新數(shù)組初始化時(shí)置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運(yùn)算次數(shù)最壞的情況為 2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效 率還能提高一倍。

21、怎么在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的一個(gè)?

• 方案 1：先做 hash，然后求模映射為小文件，求出每個(gè)小文件中重復(fù)次數(shù)最多的一個(gè)，并記錄重復(fù)次數(shù)。然后找出上一步求出的數(shù)據(jù)中重復(fù)次數(shù)最多的一個(gè)就是所求(具體參考前面的題)。

22、上千萬或上億數(shù)據(jù)(有重復(fù))，統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的錢 N 個(gè)數(shù)據(jù)。

• 方案 1：上千萬或上億的數(shù)據(jù)，現(xiàn)在的機(jī)器的內(nèi)存應(yīng)該能存下。所以考慮采用 hash_map/搜索二叉樹/紅黑樹等來進(jìn)行統(tǒng)計(jì)次數(shù)。然后就是取出前 N 個(gè)出現(xiàn)次數(shù)最多的數(shù)據(jù)了，可以用第 2 題提到的堆機(jī)制完成。

23、一個(gè)文本文件，大約有一萬行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前 10 個(gè)詞，給出思想，給出時(shí)間復(fù)雜度分析 ##。

• 方案 1：這題是考慮時(shí)間效率。用 trie 樹統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是 O(nle)(le表示單詞的平準(zhǔn)長度)。然后是找出出現(xiàn)最頻繁的前 10 個(gè)詞，可以用堆來實(shí)現(xiàn)，前面的題中已經(jīng)講到了，時(shí)間復(fù)雜度是 O(nlg10)。所以總的時(shí)間復(fù)雜度，是 O(nle)與 O(nlg10)中較大的哪一 個(gè)。

24、100w 個(gè)數(shù)中找出最大的 100 個(gè)數(shù) ##。

• 方案 1：在前面的題中，我們已經(jīng)提到了，用一個(gè)含 100 個(gè)元素的最小堆完成。復(fù)雜度為O(100wlg100)。
• 方案 2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比 100 多的時(shí)候，采用傳統(tǒng)排序算法排序，取前 100 個(gè)。復(fù)雜度為 O(100w100)。
• 方案 3：采用局部淘汰法。選取前 100 個(gè)元素，并排序，記為序列 L。然后一次掃描剩余的元素 x，與排好序的 100 個(gè)元素中最小的元素比，如果比這個(gè)最小的 要大，那么把這個(gè)最小的元素刪除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循環(huán)，直到掃描了所有的元素。復(fù)雜度為 O(100w*100)。

25、有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。 請用 5 分鐘時(shí)間，找出重復(fù)出現(xiàn)最多的前 10 條。

• 分析： 常規(guī)方法是先排序，在遍歷一次，找出重復(fù)最多的前 10 條。但是排序的算法復(fù)雜度最低為nlgn。
• 可以設(shè)計(jì)一個(gè) hash_table, hash_mapstring, int，依次讀取一千萬條短信，加載到hash_table 表中，并且統(tǒng)計(jì)重復(fù)的次數(shù)，與此同時(shí)維護(hù)一張最多 10 條的短信表。 這樣遍歷一次就能找出最多的前 10 條，算法復(fù)雜度為 O(n)。