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