Hadoop概述開源分布式計(jì)算平臺,以HDFS、MapReduce為核心,為用戶提供了系統(tǒng)底層細(xì)節(jié)透明的分布式基礎(chǔ)架構(gòu).高容錯(cuò)、高伸縮MR允許用戶在不了解分布式系統(tǒng)底層細(xì)節(jié)的...
將所有查詢進(jìn)行hash(query)%10,映射成新的10個(gè)文件,大約每個(gè)1GB。對每個(gè)文件使用hash_map統(tǒng)計(jì)頻率并排序,然后對10個(gè)結(jié)果再歸并排序。
分析:IP總個(gè)數(shù)2^32 = 4G,如果單機(jī)用一個(gè)hash表來存儲,光IP部分就得4G*4 = 16G,不現(xiàn)實(shí) 把文件按照hash(IP)%1000的方式分割成1000個(gè)小文...
一個(gè)文件占用內(nèi)存大小為5G x 64B = 320G,遠(yuǎn)大于實(shí)際內(nèi)存4G,不能一次性載入內(nèi)存。把每個(gè)文件中的url進(jìn)行hash(url)%1000,各得到1000個(gè)小文件,每...
題目:輸入一個(gè)整數(shù)n,求從1到n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)。 解法:
題目:輸入一個(gè)正整數(shù)數(shù)組,把數(shù)組里所有數(shù)字拼接起來排成一個(gè)數(shù),打印能拼接處的所有數(shù)字中最小的一個(gè)。例如輸入數(shù)組{3,32,321},則打印出這3個(gè)數(shù)字能排成的最小數(shù)字3213...
題目:把n個(gè)骰子仍在地上,所有骰子朝上一面的點(diǎn)數(shù)之和為s。輸入n,打印出s的所有可能的值出現(xiàn)的概率。 n個(gè)骰子的點(diǎn)數(shù)之和最小為n,最大值為6n,n個(gè)骰子的所有點(diǎn)數(shù)的排列數(shù)為6...
題目一:輸入一個(gè)英文句子,翻轉(zhuǎn)句子中單詞的順序,但單詞內(nèi)字符的順序不變。為簡單起見,標(biāo)點(diǎn)符號和普通字母一樣處理。例如輸入字符串"I am a student.", 則輸出"s...
題目:輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字s,在數(shù)組中查找兩個(gè)數(shù),使得他們的和正好是s。如果有多對數(shù)字的和等于s,輸出任意一對即可。 解法: 題目:輸入一個(gè)正數(shù)s,打印出所有和為...
題目:輸入一個(gè)整形數(shù)組,數(shù)組里有正數(shù)也有負(fù)數(shù),數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度O(n) 解法:動(dòng)態(tài)規(guī)劃問題
題目:輸入n個(gè)整數(shù),找出其中最小的k個(gè)數(shù)。 解法:top K問題。如果n不大,可以一次性載入內(nèi)存,則用一個(gè)數(shù)組保存,然后進(jìn)行多次partition()即可 如果n很大,無法一...
題目:數(shù)組中有一個(gè)數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半,請找出這個(gè)數(shù)字。 解法:假設(shè)將數(shù)組排序,因?yàn)樗髷?shù)字出現(xiàn)次數(shù)超過一半,則arr[n/2]即為所求。排序的時(shí)間復(fù)雜度O(nl...
題目:輸入一個(gè)字符串,打印出該字符串中字符的所有排列。 解法:遞歸的思路。以abc為例,固定首字母,剩余部分全排列即可。 擴(kuò)展題目:求一個(gè)字符串所有的組合解法:給定一個(gè)長度為...
題目:輸入一顆二叉樹和一個(gè)整數(shù),打印出二叉樹中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。從根結(jié)點(diǎn)開始往下一直到葉結(jié)點(diǎn)所經(jīng)過的結(jié)點(diǎn)形成一條路徑。 解法:
題目:輸入一個(gè)整數(shù)數(shù)組,判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。 分析:后序遍歷:左右根二叉搜索樹:左子樹都比根小,又子樹都比根大 根據(jù)后序遍歷的特征,找到根節(jié)點(diǎn)。然后...
題目:輸入兩個(gè)整數(shù)序列,第一個(gè)序列表示棧的壓入順序,請判斷第二個(gè)序列是否為該棧的彈出順序。 解法:開一個(gè)輔助棧,模擬出棧入棧的過程:從彈出序列開始,如果當(dāng)前元素等于棧頂元素,...