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í)候，會(huì)在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端會(huì)處理輸入數(shù)據(jù)并產(chǎn)生中間結(jié)果，這個(gè)中間結(jié)果會(huì)寫到本地磁盤，而不是HDFS。每個(gè)Map的輸出會(huì)先寫到內(nèi)存緩沖區(qū)中，當(dāng)寫入的數(shù)據(jù)達(dá)到設(shè)定的閾值時(shí)，系統(tǒng)將會(huì)啟動(dòng)一個(gè)線程將緩沖區(qū)的數(shù)據(jù)寫到磁盤，這個(gè)過程叫做spill。
　　在spill寫入之前，會(huì)先進(jìn)行二次排序，首先根據(jù)數(shù)據(jù)所屬的partition進(jìn)行排序，然后每個(gè)partition中的數(shù)據(jù)再按key來排序。partition的目是將記錄劃分到不同的Reducer上去，以期望能夠達(dá)到負(fù)載均衡，以后的Reducer就會(huì)根據(jù)partition來讀取自己對(duì)應(yīng)的數(shù)據(jù)。接著運(yùn)行combiner(如果設(shè)置了的話)，combiner的本質(zhì)也是一個(gè)Reducer，其目的是對(duì)將要寫入到磁盤上的文件先進(jìn)行一次處理，這樣，寫入到磁盤的數(shù)據(jù)量就會(huì)減少。最后將數(shù)據(jù)寫到本地磁盤產(chǎn)生spill文件(spill文件保存在{mapred.local.dir}指定的目錄中，Map任務(wù)結(jié)束后就會(huì)被刪除)。

　　最后，每個(gè)Map任務(wù)可能產(chǎn)生多個(gè)spill文件，在每個(gè)Map任務(wù)完成前，會(huì)通過多路歸并算法將這些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就對(duì)應(yīng)了Reducer)，所以Reducer在拷貝數(shù)據(jù)的時(shí)候只需拷貝與自己對(duì)應(yīng)的partition中的數(shù)據(jù)即可。每個(gè)Reducer會(huì)處理一個(gè)或者多個(gè)partition，但需要先將自己對(duì)應(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 模式，對(duì)于大多數(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 支持多種分布式存儲(chǔ)系統(tǒng)：HDFS 和 S3

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

 讀：
1、跟namenode通信查詢?cè)獢?shù)據(jù)，找到文件塊所在的datanode服務(wù)器
2、挑選一臺(tái)datanode（就近原則，然后隨機(jī)）服務(wù)器，請(qǐng)求建立socket流
3、datanode開始發(fā)送數(shù)據(jù)（從磁盤里面讀取數(shù)據(jù)放入流，以packet為單位來做校驗(yàn)）
4、客戶端以packet為單位接收，現(xiàn)在本地緩存，然后寫入目標(biāo)文件
  寫：
1、根namenode通信請(qǐng)求上傳文件，namenode檢查目標(biāo)文件是否已存在，父目錄是否存在
2、namenode返回是否可以上傳
3、client請(qǐng)求第一個(gè) block該傳輸?shù)侥男ヾatanode服務(wù)器上
4、namenode返回3個(gè)datanode服務(wù)器ABC
5、client請(qǐng)求3臺(tái)dn中的一臺(tái)A上傳數(shù)據(jù)（本質(zhì)上是一個(gè)RPC調(diào)用，建立pipeline），A收到請(qǐng)求會(huì)繼續(xù)調(diào)用B，然后B調(diào)用C，將真?zhèn)€pipeline建立完成，逐級(jí)返回客戶端
6、client開始往A上傳第一個(gè)block（先從磁盤讀取數(shù)據(jù)放到一個(gè)本地內(nèi)存緩存），以packet為單位，A收到一個(gè)packet就會(huì)傳給B，B傳給C；A每傳一個(gè)packet會(huì)放入一個(gè)應(yīng)答隊(duì)列等待應(yīng)答
7、當(dāng)一個(gè)block傳輸完成之后，client再次請(qǐng)求namenode上傳第二個(gè)block的服務(wù)器。

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

    reduceByKey：reduceByKey會(huì)在結(jié)果發(fā)送至reducer之前會(huì)對(duì)每個(gè)mapper在本地進(jìn)行merge，有點(diǎn)類似于在MapReduce中的combiner。這樣做的好處在于，在map端進(jìn)行一次reduce之后，數(shù)據(jù)量會(huì)大幅度減小，從而減小傳輸，保證reduce端能夠更快的進(jìn)行結(jié)果計(jì)算。
    groupByKey：groupByKey會(huì)對(duì)每一個(gè)RDD中的value值進(jìn)行聚合形成一個(gè)序列(Iterator)，此操作發(fā)生在reduce端，所以勢必會(huì)將所有的數(shù)據(jù)通過網(wǎng)絡(luò)進(jìn)行傳輸，造成不必要的浪費(fèi)。同時(shí)如果數(shù)據(jù)量十分大，可能還會(huì)造成OutOfMemoryError。
   
 通過以上對(duì)比可以發(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等操作會(huì)產(chǎn)生寬依賴，會(huì)產(chǎn)生shuffle
窄依賴：父RDD的每個(gè)分區(qū)都只被子RDD的一個(gè)分區(qū)使用  例如map、filter、union等操作會(huì)產(chǎn)生窄依賴

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

這兩種方式分別是：
Receiver-base
使用Kafka的高層次Consumer API來實(shí)現(xiàn)。receiver從Kafka中獲取的數(shù)據(jù)都存儲(chǔ)在Spark Executor的內(nèi)存中，然后Spark Streaming啟動(dòng)的job會(huì)去處理那些數(shù)據(jù)。然而，在默認(rèn)的配置下，這種方式可能會(huì)因?yàn)榈讓拥氖《鴣G失數(shù)據(jù)。如果要啟用高可靠機(jī)制，讓數(shù)據(jù)零丟失，就必須啟用Spark Streaming的預(yù)寫日志機(jī)制（Write Ahead Log，WAL）。該機(jī)制會(huì)同步地將接收到的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ù)，這種方式會(huì)周期性地查詢Kafka，獲得每個(gè)topic+partition的最新的offset，從而定義每個(gè)batch的offset的范圍。當(dāng)處理數(shù)據(jù)的job啟動(dòng)時(shí)，就會(huì)使用Kafka的簡單consumer api來獲取Kafka指定offset范圍的數(shù)據(jù)。

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

Kafka最核心的思想是使用磁盤，而不是使用內(nèi)存，可能所有人都會(huì)認(rèn)為，內(nèi)存的速度一定比磁盤快，我也不例外。在看了Kafka的設(shè)計(jì)思想，查閱了相應(yīng)資料再加上自己的測試后，發(fā)現(xiàn)磁盤的順序讀寫速度和內(nèi)存持平。
而且Linux對(duì)于磁盤的讀寫優(yōu)化也比較多，包括read-ahead和write-behind，磁盤緩存等。如果在內(nèi)存做這些操作的時(shí)候，一個(gè)是JAVA對(duì)象的內(nèi)存開銷很大，另一個(gè)是隨著堆內(nèi)存數(shù)據(jù)的增多，JAVA的GC時(shí)間會(huì)變得很長，使用磁盤操作有以下幾個(gè)好處：
磁盤緩存由Linux系統(tǒng)維護(hù)，減少了程序員的不少工作。
磁盤順序讀寫速度超過內(nèi)存隨機(jī)讀寫。
JVM的GC效率低，內(nèi)存占用大。使用磁盤可以避免這一問題。
系統(tǒng)冷啟動(dò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)是自動(dòng)提交位移的，所以在后臺(tái)提交位移前一定要保證消息被正常處理了，因此不建議采用很重的處理邏輯，如果處理耗時(shí)很長，則建議把邏輯放到另一個(gè)線程中去做。為了避免數(shù)據(jù)丟失，現(xiàn)給出兩點(diǎn)建議：
enable.auto.commit=false  關(guān)閉自動(dòng)提交位移
在消息被完整處理之后再手動(dòng)提交位移

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ù)到一定的大小事會(huì)去生成一個(gè)新的文件來保存元數(shù)據(jù)的信息，這個(gè)新的文件就是edit，edit會(huì)回滾最新的數(shù)據(jù)。

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

  1）Core-site.xml 文件的優(yōu)化
    a、fs.trash.interval，默認(rèn)值： 0；說明： 這個(gè)是開啟hdfs文件刪除自動(dòng)轉(zhuǎn)移到垃圾箱的選項(xiàng)，值為垃圾箱文件清除時(shí)間。一般開啟這個(gè)會(huì)比較好，以防錯(cuò)誤刪除重要文件。單位是分鐘。
    b、dfs.namenode.handler.count，默認(rèn)值：10；說明：hadoop系統(tǒng)里啟動(dòng)的任務(wù)線程數(shù)，這里改為40，同樣可以嘗試該值大小對(duì)效率的影響變化進(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 格式化操作，是對(duì)文件系統(tǒng)進(jìn)行格式化，namenode 格式化時(shí)清空 dfs/name 下空兩個(gè)目錄下的所有文件，之后，會(huì)在目錄 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 階段兩部分組成，這兩階段會(huì)對(duì)數(shù)據(jù)排序，從這個(gè)意義上說，MapReduce 框架本質(zhì)就是一個(gè) Distributed Sort。
  2）在 Map 階段，Map Task 會(huì)在本地磁盤輸出一個(gè)按照 key 排序（采用的是快速排序）的文件（中間可能產(chǎn)生多個(gè)文件，但最終會(huì)合并成一個(gè)），在 Reduce 階段，每個(gè) Reduce Task 會(huì)對(duì)收到的數(shù)據(jù)排序，這樣，數(shù)據(jù)便按照 Key 分成了若干組，之后以組為單位交給 reduce（）處理。
  3）很多人的誤解在 Map 階段，如果不使用 Combiner便不會(huì)排序，這是錯(cuò)誤的，不管你用不用 Combiner，Map Task 均會(huì)對(duì)產(chǎn)生的數(shù)據(jù)排序（如果沒有 Reduce Task，則不會(huì)排序，實(shí)際上 Map 階段的排序就是為了減輕 Reduce端排序負(fù)載）。
  4）由于這些排序是 MapReduce 自動(dòng)完成的，用戶無法控制，因此，在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的，如果對(duì)它進(jìn)行修改，會(huì)產(chǎn)生臨時(shí)的對(duì)象，二stringBuffer是可修改的，不會(huì)產(chǎn)生臨時(shí)對(duì)象。
  7）修改一下配置：以下是修改 mapred-site.xml 文件
    a、修改最大槽位數(shù)：槽位數(shù)是在各個(gè) 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 時(shí)，心跳間隔為 300 毫秒
mapreduce.jobtracker.heartbeat.interval.min 心跳時(shí)間
mapred.heartbeats.in.second 集群每增加多少節(jié)點(diǎn)，時(shí)間增加下面的值
mapreduce.jobtracker.heartbeat.scaling.factor 集群每增加上面的個(gè)數(shù)，心跳增多少
    c、啟動(dòng)帶外心跳
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ù)量上億條，請(qǐng)?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)表展示平臺(tái)
離線的思路是：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ī)的）。 找一臺(tái)內(nèi)存在 2G 左右的機(jī)器，依次對(duì)用 hash_map(query, query_count)來統(tǒng)計(jì)每個(gè)query 出現(xiàn)的次數(shù)。利用快速/堆/歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序。將排序好的 query 和對(duì)應(yīng)的 query_cout 輸出到文件中。這樣得到了 10 個(gè)排好序的文件（記為）。 對(duì)這 10 個(gè)文件進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。
    2）方案 2：
    一般 query 的總量是有限的，只是重復(fù)的次數(shù)比較多而已，可能對(duì)于所有的 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）方案 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 中相對(duì)應(yīng)位，如果是 00 變 01，01 變 10，10 保持不變。所描完事后，查看 bitmap，把對(duì)應(yīng)位是 01 的整數(shù)輸出即可。
  2）方案 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）方案 1：oo，申請(qǐng) 512M 的內(nèi)存，一個(gè) bit 位代表一個(gè) unsigned int 值。讀入 40 億個(gè)數(shù)，設(shè)置相應(yīng)的 bit 位，讀入要查詢的數(shù)，查看相應(yīng) bit 位是否為 1，為 1 表示存在，為 0 表示不存在。
 
  2）方案 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）方案 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）方案 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）方案 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）方案 1：在前面的題中，我們已經(jīng)提到了，用一個(gè)含 100 個(gè)元素的最小堆完成。復(fù)雜度為O(100wlg100)。
  2）方案 2：采用快速排序的思想，每次分割之后只考慮比軸大的一部分，知道比軸大的一部分在比 100 多的時(shí)候，采用傳統(tǒng)排序算法排序，取前 100 個(gè)。復(fù)雜度為 O(100w100)。
  3）方案 3：采用局部淘汰法。選取前 100 個(gè)元素，并排序，記為序列 L。然后一次掃描剩余的元素 x，與排好序的 100 個(gè)元素中最小的元素比，如果比這個(gè)最小的 要大，那么把這個(gè)最小的元素刪除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循環(huán)，直到掃描了所有的元素。復(fù)雜度為 O(100w*100)。

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

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

最新評(píng)論