1、kafka的message包括哪些信息

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

header部分由一個字節(jié)的magic(文件格式)和四個字節(jié)的CRC32(用于判斷body消息體是否正常)構(gòu)成。當(dāng)magic的值為1的時候，會在magic和crc32之間多一個字節(jié)的數(shù)據(jù)：attributes(保存一些相關(guān)屬性，比如是否壓縮、壓縮格式等等)；如果magic的值為0，那么不存在attributes屬性花了一個月整理了一份最適合2018年學(xué)習(xí)的大數(shù)據(jù)學(xué)習(xí)干貨，從最基礎(chǔ)的大數(shù)據(jù)集群搭建，大搜數(shù)據(jù)組件和項(xiàng)目實(shí)戰(zhàn)，加群QQ群：834325294 注明CSDN既可免費(fèi)獲取。
body是由N個字節(jié)構(gòu)成的一個消息體，包含了具體的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é)果，這個中間結(jié)果會寫到本地磁盤，而不是HDFS。每個Map的輸出會先寫到內(nèi)存緩沖區(qū)中，當(dāng)寫入的數(shù)據(jù)達(dá)到設(shè)定的閾值時，系統(tǒng)將會啟動一個線程將緩沖區(qū)的數(shù)據(jù)寫到磁盤，這個過程叫做spill。
　　在spill寫入之前，會先進(jìn)行二次排序，首先根據(jù)數(shù)據(jù)所屬的partition進(jìn)行排序，然后每個partition中的數(shù)據(jù)再按key來排序。partition的目是將記錄劃分到不同的Reducer上去，以期望能夠達(dá)到負(fù)載均衡，以后的Reducer就會根據(jù)partition來讀取自己對應(yīng)的數(shù)據(jù)。接著運(yùn)行combiner(如果設(shè)置了的話)，combiner的本質(zhì)也是一個Reducer，其目的是對將要寫入到磁盤上的文件先進(jìn)行一次處理，這樣，寫入到磁盤的數(shù)據(jù)量就會減少。最后將數(shù)據(jù)寫到本地磁盤產(chǎn)生spill文件(spill文件保存在{mapred.local.dir}指定的目錄中，Map任務(wù)結(jié)束后就會被刪除)。

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

二、Reduce端的shuffle

　　Reduce端的shuffle主要包括三個階段，copy、sort(merge)和reduce。
　　首先要將Map端產(chǎn)生的輸出文件拷貝到Reduce端，但每個Reducer如何知道自己應(yīng)該處理哪些數(shù)據(jù)呢？因?yàn)镸ap端進(jìn)行partition的時候，實(shí)際上就相當(dāng)于指定了每個Reducer要處理的數(shù)據(jù)(partition就對應(yīng)了Reducer)，所以Reducer在拷貝數(shù)據(jù)的時候只需拷貝與自己對應(yīng)的partition中的數(shù)據(jù)即可。每個Reducer會處理一個或者多個partition，但需要先將自己對應(yīng)的partition中的數(shù)據(jù)從每個Map的輸出結(jié)果中拷貝過來。
　　接下來就是sort階段，也成為merge階段，因?yàn)檫@個階段的主要工作是執(zhí)行了歸并排序。從Map端拷貝到Reduce端的數(shù)據(jù)都是有序的，所以很適合歸并排序。最終在Reduce端生成一個較大的文件作為Reduce的輸入。

　　最后就是Reduce過程了，在這個過程中產(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，使用這個模式能很方便的訪問 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請求第一個 block該傳輸?shù)侥男ヾatanode服務(wù)器上
4、namenode返回3個datanode服務(wù)器ABC
5、client請求3臺dn中的一臺A上傳數(shù)據(jù)（本質(zhì)上是一個RPC調(diào)用，建立pipeline），A收到請求會繼續(xù)調(diào)用B，然后B調(diào)用C，將真?zhèn)€pipeline建立完成，逐級返回客戶端
6、client開始往A上傳第一個block（先從磁盤讀取數(shù)據(jù)放到一個本地內(nèi)存緩存），以packet為單位，A收到一個packet就會傳給B，B傳給C；A每傳一個packet會放入一個應(yīng)答隊(duì)列等待應(yīng)答
7、當(dāng)一個block傳輸完成之后，client再次請求namenode上傳第二個block的服務(wù)器。

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

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

7、spark2.0的了解

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

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

寬依賴：父RDD的分區(qū)被子RDD的多個分區(qū)使用  例如 groupByKey、reduceByKey、sortByKey等操作會產(chǎn)生寬依賴，會產(chǎn)生shuffle

窄依賴：父RDD的每個分區(qū)都只被子RDD的一個分區(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，獲得每個topic+partition的最新的offset，從而定義每個batch的offset的范圍。當(dāng)處理數(shù)據(jù)的job啟動時，就會使用Kafka的簡單consumerapi來獲取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)存做這些操作的時候，一個是JAVA對象的內(nèi)存開銷很大，另一個是隨著堆內(nèi)存數(shù)據(jù)的增多，JAVA的GC時間會變得很長，使用磁盤操作有以下幾個好處：
磁盤緩存由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ù)據(jù)丟失，現(xiàn)給出兩點(diǎn)建議：
enable.auto.commit=false  關(guān)閉自動提交位移
在消息被完整處理之后再手動提交位移

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

13、列舉幾個配置文件優(yōu)化？  1）Core-site.xml 文件的優(yōu)化   a、fs.trash.interval，默認(rèn)值： 0；說明： 這個是開啟hdfs文件刪除自動轉(zhuǎn)移到垃圾箱的選項(xiàng)，值為垃圾箱文件清除時間。一般開啟這個會比較好，以防錯誤刪除重要文件。單位是分鐘。   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ù)?，這個是設(shè)置傳輸?shù)牟⑿芯€程數(shù)。

14、datanode首次加入 cluster 的時候，如果 log 報(bào)告不兼容文件版本，那需要namenode 執(zhí)行格式化操作，這樣處理的原因是？
  1）這樣處理是不合理的，因?yàn)槟敲?nbsp;namenode格式化操作，是對文件系統(tǒng)進(jìn)行格式化，namenode 格式化時清空 dfs/name 下空兩個目錄下的所有文件，之后，會在目錄 dfs.name.dir 下創(chuàng)建文件。 2）文本不兼容，有可能時 namenode 與 datanode 的 數(shù)據(jù)里的 namespaceID、clusterID 不一致，找到兩個 ID 位置，修改為一樣即可解決。

15、MapReduce中排序發(fā)生在哪幾個階段？這些排序是否可以避免？為什么？
  1）一個 MapReduce 作業(yè)由 Map 階段和 Reduce 階段兩部分組成，這兩階段會對數(shù)據(jù)排序，從這個意義上說，MapReduce 框架本質(zhì)就是一個 Distributed Sort。 2）在 Map 階段，Map Task 會在本地磁盤輸出一個按照 key 排序（采用的是快速排序）的文件（中間可能產(chǎn)生多個文件，但最終會合并成一個），在Reduce 階段，每個 Reduce Task 會對收到的數(shù)據(jù)排序，這樣，數(shù)據(jù)便按照 Key 分成了若干組，之后以組為單位交給 reduce（）處理。 3）很多人的誤解在 Map 階段，如果不使用 Combiner便不會排序，這是錯誤的，不管你用不用 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ù)時要進(jìn)行測試 3）代碼的優(yōu)化：combiner的個數(shù)盡量與reduce的個數(shù)相同，數(shù)據(jù)的類型保持一致，可以減少拆包與封包的進(jìn)度 4）系統(tǒng)的優(yōu)化：可以設(shè)置linux系統(tǒng)打開最大的文件數(shù)預(yù)計(jì)網(wǎng)絡(luò)的帶寬MTU的配置 5）為 job 添加一個 Combiner，可以大大的減少shuffer階段的maoTask拷貝過來給遠(yuǎn)程的   reduce task的數(shù)據(jù)量，一般而言combiner與reduce相同。 6）在開發(fā)中盡量使用stringBuffer而不是string，string的模式是read-only的，如果對它進(jìn)行修改，會產(chǎn)生臨時的對象，二stringBuffer是可修改的，不會產(chǎn)生臨時對象。 7）修改一下配置：以下是修改 mapred-site.xml 文件   a、修改最大槽位數(shù)：槽位數(shù)是在各個tasktracker 上的 mapred-site.xml 上設(shè)置的，默認(rèn)都是 2

<property>
<name>mapred.tasktracker.map.tasks.maximum</name>
<value>2</value>
</property>
<property>
<name>mapred.tasktracker.reduce.tasks.maximum</name>
<value>2</value>
</property>

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

• mapreduce.jobtracker.heartbeat.interval.min 心跳時間
• mapred.heartbeats.in.second 集群每增加多少節(jié)點(diǎn)，時間增加下面的值
• mapreduce.jobtracker.heartbeat.scaling.factor 集群每增加上面的個數(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>
<name>mapred.compress.map.output</name>
<value>true</value>
</property>
<property>
<name>mapred.map.output.compression.codec</name>
<value>org.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í)時查詢的功能（響應(yīng)時間小于3s）
A、某個用戶某天訪問某個URL的次數(shù)
B、某個URL某天被訪問的總次數(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 個文件，每個文件 1G，每個文件的每一行存放的都是用戶的 query，每個文件的query 都可能重復(fù)。要求你按照 query 的頻度排序。 還是典型的 TOP K 算法，
解決方案如下：    1）方案 1：    順序讀取 10 個文件，按照 hash(query)%10 的結(jié)果將 query 寫入到另外 10 個文件（記為）中。這樣新生成的文件每個的大小大約也 1G（假設(shè) hash 函數(shù)是隨機(jī)的）。 找一臺內(nèi)存在 2G 左右的機(jī)器，依次對用 hash_map(query, query_count)來統(tǒng)計(jì)每個query 出現(xiàn)的次數(shù)。利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的 query 和對應(yīng)的 query_cout 輸出到文件中。這樣得到了 10 個排好序的文件（記為）。 對這 10 個文件進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。    2）方案 2：    一般 query 的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對于所有的 query，一次性就可以加入到內(nèi)存了。這樣，我們就可以采用 trie 樹/hash_map等直接來統(tǒng)計(jì)每個 query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速/堆/歸并排序就可以了。    3）方案 3：    與方案 1 類似，但在做完 hash，分成多個文件后，可以交給多個文件來處理，采用分布式的架構(gòu)來處理（比如MapReduce），最后再進(jìn)行合并。

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

20、騰訊面試題：給 40 億個不重復(fù)的 unsigned int 的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那 40 億個數(shù)當(dāng)中？  1）方案 1：oo，申請 512M 的內(nèi)存，一個bit 位代表一個 unsigned int 值。讀入 40 億個數(shù)，設(shè)置相應(yīng)的 bit 位，讀入要查詢的數(shù)，查看相應(yīng) bit 位是否為 1，為 1 表示存在，為 0 表示不存在。  2）方案 2：這個問題在《編程珠璣》里有很好的描述，大家可以參考下面的思路，探討一下：又因?yàn)?nbsp;2^32 為 40 億多，所以給定一個數(shù)可能在，也可能不在其中；這里我們把 40 億個數(shù)中的每一個用 32 位的二進(jìn)制來表示 ，假設(shè)這 40 億個數(shù)開始放在一個文件中。 然后將這 40 億個數(shù)分成兩類: 
1.最高位為 0 
2.最高位為 1    并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=20 億，而另一個>=20 億（這相當(dāng)于折半了）； 與要查找的數(shù)的最高位比較并接著進(jìn)入相應(yīng)的文件再查找再然后把這個文件為又分成兩類: 
1.次最高位為 0 
2.次最高位為 1    并將這兩類分別寫入到兩個文件中，其中一個文件中數(shù)的個數(shù)<=10 億，而另一個>=10 億（這相當(dāng)于折半了）； 與要查找的數(shù)的次最高位比較并接著進(jìn)入相應(yīng)的文件再查找。 
.....    以此類推，就可以找到了,而且時間復(fù)雜度為 O(logn)，方案 2 完。  3)附：這里，再簡單介紹下，位圖方法： 使用位圖法判斷整形數(shù)組是否存在重復(fù) ,判斷集合中存在重復(fù)是常見編程任務(wù)之一，當(dāng)集合中數(shù)據(jù)量比較大時我們通常希望少進(jìn)行幾次掃描，這時雙重循環(huán)法就不可取了。    位圖法比較適合于這種情況，它的做法是按照集合中最大元素 max 創(chuàng)建一個長度為 max+1的新數(shù)組，然后再次掃描原數(shù)組，遇到幾就給新數(shù)組的第幾位置上 1，如遇到 5 就給新數(shù)組的第六個元素置 1，這樣下次再遇到 5 想置位時發(fā)現(xiàn)新數(shù)組的第六個元素已經(jīng)是 1 了，這說明這次的數(shù)據(jù)肯定和以前的數(shù)據(jù)存在著重復(fù)。這 種給新數(shù)組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運(yùn)算次數(shù)最壞的情況為 2N。如果已知數(shù)組的最大值即能事先給新數(shù)組定長的話效 率還能提高一倍。

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

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

23、一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前 10 個詞，給出思想，給出時間復(fù)雜度分析。 
  1）方案 1：這題是考慮時間效率。用 trie 樹統(tǒng)計(jì)每個詞出現(xiàn)的次數(shù)，時間復(fù)雜度是 O(n*le)（le表示單詞的平準(zhǔn)長度）。然后是找出出現(xiàn)最頻繁的前 10 個詞，可以用堆來實(shí)現(xiàn)，前面的題中已經(jīng)講到了，時間復(fù)雜度是 O(n*lg10)。所以總的時間復(fù)雜度，是 O(n*le)與 O(n*lg10)中較大的哪一 個。

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

25、有一千萬條短信，有重復(fù)，以文本文件的形式保存，一行一條，有重復(fù)。 請用 5 分鐘時間，找出重復(fù)出現(xiàn)最多的前 10 條。 
  1）分析： 常規(guī)方法是先排序，在遍歷一次，找出重復(fù)最多的前 10 條。但是排序的算法復(fù)雜度最低為nlgn。  2）可以設(shè)計(jì)一個 hash_table, hash_map<string,int>，依次讀取一千萬條短信，加載到hash_table 表中，并且統(tǒng)計(jì)重復(fù)的次數(shù)，與此同時維護(hù)一張最多 10 條的短信表。 這樣遍歷一次就能找出最多的前 10 條，算法復(fù)雜度為 O(n)。  

到此這篇關(guān)于2018最新BAT大數(shù)據(jù)面試題(附答案)的文章就介紹到這了,更多相關(guān)BAT大數(shù)據(jù)面試題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持腳本之家！

最新評論