桶排序php

Ⅰ 想學web前端需要學什麼知識

隨著互聯網的發展，各種小程序、APP以及很多的互聯網+創業公司的興起，對現在前端工程的要求也越來越高，如何適應目前IT行業時代的發展趨勢，web前端工程師又需要掌握那些技能呢？

一、HTML5+CSS3

HTML是網頁的主要組成部分，網頁的本質就是HTML，是用來製作超文本文檔的簡單標記語言；CSS樣式是對HTML語言的有效補充，通過使用CSS樣式，便於頁面的修改以及頁面風格的統一，還可以減少頁面的體積，通過HTML和CSS完成靜態頁面的布局。HTML5+CSS3是HTML+CSS的更新，增加了很多非常實用的功能。這部分主要是從PC端和移動端兩方面掌握整體的頁面布局技術，並且配合項目實戰操練、學以致用。

二、JS交互設計

這一部分主要掌握JS的基本語法、演算法和高級語法，熟練使用面向對象的思想進行DOM編程，通過JQuery經典案例學習精通JQuery技術。

通過以上介紹，相信大家都了解了web前端開發需要學習的內容了，現在隨著行業而發展，對前端的要求也越來越高，對高端人才的需求也越來越多，只有大家掌握的知識越多，掌握的技能越全面，越好，之後的選擇權才會更多，發展前景更好。

Ⅱ php的演算法可以實現大數據分析嗎

1.Bloom filter

適用范圍：可以用來實現數據字典，進行數據的判重，或者集合求交集

基本原理及要點：
對於原理來說很簡單，位數組+k個獨立hash函數。將hash函數對應的值的位數組置1，查找時如果發現所有hash函數對應位都是1說明存在，很明顯這個過程並不保證查找的結果是100%正確的。同時也不支持刪除一個已經插入的關鍵字，因為該關鍵字對應的位會牽動到其他的關鍵字。所以一個簡單的改進就是 counting Bloom filter，用一個counter數組代替位數組，就可以支持刪除了。

還有一個比較重要的問題，如何根據輸入元素個數n，確定位數組m的大小及hash函數個數。當hash函數個數k=(ln2)*(m/n)時錯誤率最小。在錯誤率不大於E的情況下，m至少要等於n*lg(1/E)才能表示任意n個元素的集合。但m還應該更大些，因為還要保證bit數組里至少一半為 0，則m 應該>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2為底的對數)。

舉個例子我們假設錯誤率為0.01，則此時m應大概是n的13倍。這樣k大概是8個。

注意這里m與n的單位不同，m是bit為單位，而n則是以元素個數為單位(准確的說是不同元素的個數)。通常單個元素的長度都是有很多bit的。所以使用bloom filter內存上通常都是節省的。

擴展：
Bloom filter將集合中的元素映射到位數組中，用k（k為哈希函數個數）個映射位是否全1表示元素在不在這個集合中。Counting bloom filter（CBF）將位數組中的每一位擴展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其與集合元素的出現次數關聯。SBF採用counter中的最小值來近似表示元素的出現頻率。

問題實例：給你A,B兩個文件，各存放50億條URL，每條URL佔用64位元組，內存限制是4G，讓你找出A,B文件共同的URL。如果是三個乃至n個文件呢？

根據這個問題我們來計算下內存的佔用，4G=2^32大概是40億*8大概是340億，n=50億，如果按出錯率0.01算需要的大概是650億個 bit。現在可用的是340億，相差並不多，這樣可能會使出錯率上升些。另外如果這些urlip是一一對應的，就可以轉換成ip，則大大簡單了。

2.Hashing

適用范圍：快速查找，刪除的基本數據結構，通常需要總數據量可以放入內存

基本原理及要點：
hash函數選擇，針對字元串，整數，排列，具體相應的hash方法。
碰撞處理，一種是open hashing，也稱為拉鏈法；另一種就是closed hashing，也稱開地址法，opened addressing。 (http://www.my400800.cn)

擴展：
d-left hashing中的d是多個的意思，我們先簡化這個問題，看一看2-left hashing。2-left hashing指的是將一個哈希表分成長度相等的兩半，分別叫做T1和T2，給T1和T2分別配備一個哈希函數，h1和h2。在存儲一個新的key時，同時用兩個哈希函數進行計算，得出兩個地址h1[key]和h2[key]。這時需要檢查T1中的h1[key]位置和T2中的h2[key]位置，哪一個位置已經存儲的（有碰撞的）key比較多，然後將新key存儲在負載少的位置。如果兩邊一樣多，比如兩個位置都為空或者都存儲了一個key，就把新key 存儲在左邊的T1子表中，2-left也由此而來。在查找一個key時，必須進行兩次hash，同時查找兩個位置。

問題實例：
1).海量日誌數據，提取出某日訪問網路次數最多的那個IP。

IP的數目還是有限的，最多2^32個，所以可以考慮使用hash將ip直接存入內存，然後進行統計。

3.bit-map

適用范圍：可進行數據的快速查找，判重，刪除，一般來說數據范圍是int的10倍以下

基本原理及要點：使用bit數組來表示某些元素是否存在，比如8位電話號碼

擴展：bloom filter可以看做是對bit-map的擴展

問題實例：

1)已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位最多99 999 999，大概需要99m個bit，大概10幾m位元組的內存即可。

2)2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

將bit-map擴展一下，用2bit表示一個數即可，0表示未出現，1表示出現一次，2表示出現2次及以上。或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map。

4.堆

適用范圍：海量數據前n大，並且n比較小，堆可以放入內存

基本原理及要點：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我們比較當前元素與最大堆里的最大元素，如果它小於最大元素，則應該替換那個最大元素。這樣最後得到的n個元素就是最小的n個。適合大數據量，求前n小，n的大小比較小的情況，這樣可以掃描一遍即可得到所有的前n元素，效率很高。

擴展：雙堆，一個最大堆與一個最小堆結合，可以用來維護中位數。

問題實例：
1)100w個數中找最大的前100個數。

用一個100個元素大小的最小堆即可。

5.雙層桶劃分 ----其實本質上就是【分而治之】的思想，重在「分」的技巧上！

適用范圍：第k大，中位數，不重復或重復的數字

基本原理及要點：因為元素范圍很大，不能利用直接定址表，所以通過多次劃分，逐步確定范圍，然後最後在一個可以接受的范圍內進行。可以通過多次縮小，雙層只是一個例子。

擴展：

問題實例：
1).2.5億個整數中找出不重復的整數的個數，內存空間不足以容納這2.5億個整數。

有點像鴿巢原理，整數個數為2^32,也就是，我們可以將這2^32個數，劃分為2^8個區域(比如用單個文件代表一個區域)，然後將數據分離到不同的區域，然後不同的區域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁碟空間，就可以很方便的解決。

2).5億個int找它們的中位數。

這個例子比上面那個更明顯。首先我們將int劃分為2^16個區域，然後讀取數據統計落到各個區域里的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域，同時知道這個區域中的第幾大數剛好是中位數。然後第二次掃描我們只統計落在這個區域中的那些數就可以了。

實際上，如果不是int是int64，我們可以經過3次這樣的劃分即可降低到可以接受的程度。即可以先將int64分成2^24個區域，然後確定區域的第幾大數，在將該區域分成2^20個子區域，然後確定是子區域的第幾大數，然後子區域里的數的個數只有2^20，就可以直接利用direct addr table進行統計了。

6.資料庫索引

適用范圍：大數據量的增刪改查

基本原理及要點：利用數據的設計實現方法，對海量數據的增刪改查進行處理。
擴展：
問題實例：

7.倒排索引(Inverted index)

適用范圍：搜索引擎，關鍵字查詢

基本原理及要點：為何叫倒排索引？一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。

以英文為例，下面是要被索引的文本：
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我們就能得到下面的反向文件索引：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
檢索的條件"what", "is" 和 "it" 將對應集合的交集。

正向索引開發出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。在正向索引中，文檔占據了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關系。

擴展：

問題實例：文檔檢索系統，查詢那些文件包含了某單詞，比如常見的學術論文的關鍵字搜索。

8.外排序

適用范圍：大數據的排序，去重

基本原理及要點：外排序的歸並方法，置換選擇 敗者樹原理，最優歸並樹

擴展：

問題實例：
1).有一個1G大小的一個文件，裡面每一行是一個詞，詞的大小不超過16個位元組，內存限制大小是1M。返回頻數最高的100個詞。

這個數據具有很明顯的特點，詞的大小為16個位元組，但是內存只有1m做hash有些不夠，所以可以用來排序。內存可以當輸入緩沖區使用。

9.trie樹

適用范圍：數據量大，重復多，但是數據種類小可以放入內存

基本原理及要點：實現方式，節點孩子的表示方式

擴展：壓縮實現。

問題實例：
1).有10個文件，每個文件1G， 每個文件的每一行都存放的是用戶的query，每個文件的query都可能重復。要你按照query的頻度排序 。

2).1000萬字元串，其中有些是相同的(重復),需要把重復的全部去掉，保留沒有重復的字元串。請問怎麼設計和實現？

3).尋找熱門查詢：查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復後，不超過3百萬個，每個不超過255位元組。

10.分布式處理 maprece

適用范圍：數據量大，但是數據種類小可以放入內存

基本原理及要點：將數據交給不同的機器去處理，數據劃分，結果歸約。

擴展：

問題實例：

1).The canonical example application of MapRece is a process to count the appearances of

each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);

void rece(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by

the Map function, using the word as the result key. The framework puts together all the pairs

with the same key and feeds them to the same call to Rece, thus this function just needs to

sum all of its input values to find the total appearances of that word.

2).海量數據分布在100台電腦中，想個辦法高效統計出這批數據的TOP10。

3).一共有N個機器，每個機器上有N個數。每個機器最多存O(N)個數並對它們操作。如何找到N^2個數的中數(median)？

經典問題分析

上千萬or億數據（有重復），統計其中出現次數最多的前N個數據,分兩種情況：可一次讀入內存，不可一次讀入。

可用思路：trie樹+堆，資料庫索引，劃分子集分別統計，hash，分布式計算，近似統計，外排序

所謂的是否能一次讀入內存，實際上應該指去除重復後的數據量。如果去重後數據可以放入內存，我們可以為數據建立字典，比如通過 map，hashmap，trie，然後直接進行統計即可。當然在更新每條數據的出現次數的時候，我們可以利用一個堆來維護出現次數最多的前N個數據，當然這樣導致維護次數增加，不如完全統計後在求前N大效率高。

如果數據無法放入內存。一方面我們可以考慮上面的字典方法能否被改進以適應這種情形，可以做的改變就是將字典存放到硬碟上，而不是內存，這可以參考資料庫的存儲方法。

當然還有更好的方法，就是可以採用分布式計算，基本上就是map-rece過程，首先可以根據數據值或者把數據hash(md5)後的值，將數據按照范圍劃分到不同的機子，最好可以讓數據劃分後可以一次讀入內存，這樣不同的機子負責處理各種的數值范圍，實際上就是map。得到結果後，各個機子只需拿出各自的出現次數最多的前N個數據，然後匯總，選出所有的數據中出現次數最多的前N個數據，這實際上就是rece過程。

實際上可能想直接將數據均分到不同的機子上進行處理，這樣是無法得到正確的解的。因為一個數據可能被均分到不同的機子上，而另一個則可能完全聚集到一個機子上，同時還可能存在具有相同數目的數據。比如我們要找出現次數最多的前100個，我們將1000萬的數據分布到10台機器上，找到每台出現次數最多的前 100個，歸並之後這樣不能保證找到真正的第100個，因為比如出現次數最多的第100個可能有1萬個，但是它被分到了10台機子，這樣在每台上只有1千個，假設這些機子排名在1000個之前的那些都是單獨分布在一台機子上的，比如有1001個，這樣本來具有1萬個的這個就會被淘汰，即使我們讓每台機子選出出現次數最多的1000個再歸並，仍然會出錯，因為可能存在大量個數為1001個的發生聚集。因此不能將數據隨便均分到不同機子上，而是要根據hash 後的值將它們映射到不同的機子上處理，讓不同的機器處理一個數值范圍。

而外排序的方法會消耗大量的IO，效率不會很高。而上面的分布式方法，也可以用於單機版本，也就是將總的數據根據值的范圍，劃分成多個不同的子文件，然後逐個處理。處理完畢之後再對這些單詞的及其出現頻率進行一個歸並。實際上就可以利用一個外排序的歸並過程。

另外還可以考慮近似計算，也就是我們可以通過結合自然語言屬性，只將那些真正實際中出現最多的那些詞作為一個字典，使得這個規模可以放入內存。

Ⅲ PHP如何實現基數排序

<?php
for($i=0;$i<500;$i++)
$arr[$i]=rand(0,10000);
printArr($arr);
echo"<hr>";
functionbase_sort(&$arr){
$len=count($arr);
$max=0;
$cnt=0;
$arr_=array();
for($i=0;$i<$len;$i++)//獲取數組中的最大值
if($arr[$i]>$max)
$max=$arr[$i];
while($max/10!=0){//獲取最大值一共有多少位，以便於以後決定進行多少次入桶和出桶
$max=(int)$max/10;
$cnt++;
}
$cnt--;
for($i=0;$i<$cnt;$i++){
$temp=pow(10,$i);
for($j=0;$j<$len;$j++){//將每一個元素進行入桶
$a=$arr[$j]/$temp%10;
$arr_[$a][]=$arr[$j];
}
for($arr_index=0,$k=0;$k<10;$k++){//將每一個元素進行出桶，並將他們進行合並
for($j=0;$j<count($arr_[$k]);$j++){
if(!empty($arr_[$k])){
$arr[$arr_index++]=$arr_[$k][$j];
}
}
}
unset($arr_);
}
}
base_sort($arr);
printArr($arr);
functionprintArr($arr){
for($i=0;$i<count($arr);$i++)
echo''.$arr[$i];
echo"
";
}
?>

Ⅳ 如何理解c/c++和php語言的區別

一、編程語言

1.根據熟悉的語言，談談兩種語言的區別？

主要淺談下C/C++和PHP語言的區別:

1)PHP弱類型語言，一種腳本語言，對數據的類型不要求過多，較多的應用於Web應用開發，現在好多互聯網開發公司的主流web後台開發語言，主要框架為mvc模型，如smarty,yaf，升級的PHP7速度較快，對伺服器的壓力要小很多，在新浪微博已經有應用，對比很明顯。

2)C/C++開發語言，C語言更偏向硬體底層開發，C++語言是目前為止我認為語法內容最多的一種語言。C/C++在執行速度上要快很多，畢竟其他類型的語言大都是C開發的，更多應用於網路編程和嵌入式編程。

2.volatile是幹啥用的，（必須將cpu的寄存器緩存機制回答得很透徹），使用實例有哪些？（重點）

1） 訪問寄存器比訪問內存單元要快,編譯器會優化減少內存的讀取，可能會讀臟數據。聲明變數為volatile，編譯器不再對訪問該變數的代碼優化，仍然從內存讀取，使訪問穩定。

總結：volatile關鍵詞影響編譯器編譯的結果，用volatile聲明的變數表示該變數隨時可能發生變化，與該變數有關的運算，不再編譯優化，以免出錯。

2）使用實例如下( 區分C程序員和嵌入式系統程序員的最基本的問題。 )：

並行設備的硬體寄存器（如：狀態寄存器）
一個中斷服務子程序中會訪問到的非自動變數(Non-automatic variables)
多線程應用中被幾個任務共享的變數
3)一個參數既可以是const還可以是volatile嗎？解釋為什麼。

可以。一個例子是只讀的狀態寄存器。它是volatile因為它可能被意想不到地改變。它是const因為程序不應該試圖去修改它。
4）一個指針可以是volatile 嗎？解釋為什麼。
可以。盡管這並不是很常見。一個例子當中斷服務子程序修改一個指向一個buffer的指針時。

下面的函數有什麼錯誤：
int square(volatile int *ptr) {
return *ptr * *ptr;
}
下面是答案：
這段代碼有點變態。這段代碼的目的是用來返指針*ptr指向值的平方，但是，由於*ptr指向一個volatile型參數，編譯器將產生類似下面的代碼：
int square(volatile int *ptr){
int a,b;
a = *ptr;
b = *ptr;
return a * b;
}
由於*ptr的值可能被意想不到地改變，因此a和b可能是不同的。結果，這段代碼可能並不是你所期望的平方值！正確的代碼如下：
long square(volatile int *ptr){
int a;
a = *ptr;
return a * a;
}

更多linux內核視頻教程文本資料免費獲取後台私信【 內核 】。

3.static const等等的用法，（能說出越多越好）（重點）

² 首先說說const的用法（絕對不能說是常數）

1）在定義的時候必須進行初始化

2）指針可以是const 指針，也可以是指向const對象的指針

3）定義為const的形參，即在函數內部是不能被修改的

4）類的成員函數可以被聲明為正常成員函數，不能修改類的成員變數

5）類的成員函數可以返回的是常對象，即被const聲明的對象

6）類的成員變數是指成員變數不能在聲明時初始化，必須在構造函數的列表裡進行初始化

（註：千萬不要說const是個常數，會被認為是外行人的！！！！哪怕說個只讀也行）

下面的聲明都是什麼意思？
const int a; a是一個正常整型數
int const a; a是一個正常整型數
const int *a; a是一個指向常整型數的指針，整型數是不可修改的，但指針可以
int * const a; a為指向整型數的常指針，指針指向的整型數可以修改，但指針是不可修改的
int const * a const; a是一個指向常整型數的常指針，指針指向的整型數是不可修改的，同時指針也是不可修改的
通過給優化器一些附加的信息，使用關鍵字const也許能產生更緊湊的代碼。合理地使用關鍵字const可以使編譯器很自然地保護那些不希望被改變的參數，防止其被無意的代碼修改。簡而言之，這樣可以減少bug的出現。

Const如何做到只讀？

這些在編譯期間完成，對於內置類型，如int， 編譯器可能使用常數直接替換掉對此變數的引用。而對於結構體不一定。

² 再說說static的用法（三個明顯的作用一定要答出來）

1）在函數體內，一個被聲明為靜態的變數在這一函數被調用過程中維持其值不變。
2）在模塊內（但在函數體外），一個被聲明為靜態的變數可以被模塊內所用函數訪問，但不能被模塊外其它函數訪問。它是一個本地的全局變數。
3）在模塊內，一個被聲明為靜態的函數只可被這一模塊內的其它函數調用。那就是，這個函數被限制在聲明它的模塊的本地范圍內使用

4）類內的static成員變數屬於整個類所擁有，不能在類內進行定義，只能在類的作用域內進行定義

5）類內的static成員函數屬於整個類所擁有，不能包含this指針，只能調用static成員函數

static全局變數與普通的全局變數有什麼區別?static局部變數和普通局部變數有什麼區別?static函數與普通函數有什麼區別?

static全局變數與普通的全局變數有什麼區別：static全局變數只初始化一次，防止在其他文件單元中被引用;
static局部變數和普通局部變數有什麼區別：static局部變數只被初始化一次，下一次依據上一次結果值；
static函數與普通函數有什麼區別：static函數在內存中只有一份，普通函數在每個被調用中維持一份拷貝

4.extern c 作用

告訴編譯器該段代碼以C語言進行編譯。

5.指針和引用的區別

1）引用是直接訪問，指針是間接訪問。

2）引用是變數的別名，本身不單獨分配自己的內存空間，而指針有自己的內存空間

3）引用綁定內存空間（必須賦初值），是一個變數別名不能更改綁定，可以改變對象的值。

總的來說：引用既具有指針的效率，又具有變數使用的方便性和直觀性

6. 關於靜態內存分配和動態內存分配的區別及過程

1) 靜態內存分配是在編譯時完成的，不佔用CPU資源；動態分配內存運行時完成，分配與釋放需要佔用CPU資源；

2)靜態內存分配是在棧上分配的，動態內存是堆上分配的；

3)動態內存分配需要指針或引用數據類型的支持，而靜態內存分配不需要；

4)靜態內存分配是按計劃分配，在編譯前確定內存塊的大小，動態內存分配運行時按需分配。

5)靜態分配內存是把內存的控制權交給了編譯器，動態內存把內存的控制權交給了程序員；

6)靜態分配內存的運行效率要比動態分配內存的效率要高，因為動態內存分配與釋放需要額外的開銷；動態內存管理水平嚴重依賴於程序員的水平，處理不當容易造成內存泄漏。

7. 頭文件中的 ifndef/define/endif 干什麼用 ？

預處理，防止頭文件被重復使用，包括pragma once都是這樣的

8. 宏定義求兩個元素的最小值

#define MIN(A,B) （（A） next;

}

else

{

return NULL;

}

}

Node* pFind = pHead;

while (pCurrent) {

pFind = pFind->next;

pCurrent = pCurrent->next;

}

return pFind;

}

2. 給定一個單向鏈表（長度未知），請遍歷一次就找到中間的指針，假設該鏈表存儲在只讀存儲器，不能被修改

設置兩個指針，一個每次移動兩個位置，一個每次移動一個位置，當第一個指針到達尾節點時，第二個指針就達到了中間節點的位置

處理鏈表問題時，」快行指針「是一種很常見的技巧，快行指針指的是同時用兩個指針來迭代訪問鏈表，只不過其中一個比另一個超前一些。快指針往往先行幾步，或與慢指針相差固定的步數。

node *create() {

node *p1, *p2, *head;

int cycle = 1, x;

head = (node*)malloc(sizeof(node));

p1 = head;

while (cycle)

{

cout > x;

if (x != 0)

{

p2 = (node*)malloc(sizeof(node));

p2->data = x;

p1->next = p2;

p1 = p2;

}

else

{

cycle = 0;

}

}

head = head->next;

p1->next = NULL;

return head;

}

void findmid(node* head) {

node *p1, *p2, *mid;

p1 = head;

p2 = head;

while (p1->next->next != NULL)

{

p1 = p1->next->next;

p2 = p2->next;

mid = p2;

}

}

3. 將一個數組生成二叉排序樹

排序，選數組中間的一個元素作為根節點，左邊的元素構造左子樹，右邊的節點構造有子樹。

4. 查找數組中第k大的數字？

因為快排每次將數組劃分為兩組加一個樞紐元素，每一趟劃分你只需要將k與樞紐元素的下標進行比較，如果比樞紐元素下標大就從右邊的子數組中找，如果比樞紐元素下標小從左邊的子數組中找，如果一樣則就是樞紐元素，找到，如果需要從左邊或者右邊的子數組中再查找的話，只需要遞歸一邊查找即可，無需像快排一樣兩邊都需要遞歸，所以復雜度必然降低。

最差情況如下：假設快排每次都平均劃分，但是都不在樞紐元素上找到第k大第一趟快排沒找到，時間復雜度為O(n)，第二趟也沒找到，時間復雜度為O(n/2)，第k趟找到，時間復雜度為O(n/2k)，所以總的時間復雜度為O(n(1+1/2+....+1/2k))=O(n)，明顯比冒泡快，雖然遞歸深度是一樣的，但是每一趟時間復雜度降低。

5. 紅黑樹的定義和解釋？B樹的基本性質？

紅黑樹：

性質1. 節點是紅色或黑色。
性質2. 根節點是黑色。
性質3. 每個葉子結點都帶有兩個空的黑色結點（被稱為黑哨兵），如果一個結點n的只有一個左孩子，那麼n的右孩子是一個黑哨兵；如果結點n只有一個右孩子，那麼n的左孩子是一個黑哨兵。
性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

B樹：

1.所有非葉子結點至多擁有兩個兒子（Left和Right）；

2.所有結點存儲一個關鍵字；

3.非葉子結點的左指針指向小於其關鍵字的子樹，右指針指向大於其關鍵字的子樹；

6. 常見的加密演算法？

對稱式加密就是加密和解密使用同一個密鑰。
非對稱式加密就是加密和解密所使用的不是同一個密鑰，通常有兩個密鑰，稱為「公鑰」和「私鑰」，它們兩個必需配對使用。
DES：對稱演算法，數據加密標准，速度較快，適用於加密大量數據的場合；
MD5的典型應用是對一段Message產生fingerprint(指紋)，以防止被「篡改」。
RSA是第一個既能用於數據加密也能用於數字簽名的演算法。

7. https?

HTTP下加入SSL層，HTTPS的安全基礎是SSL。

8.有一個IP庫，給你一個IP,如何能夠快速的從中查找到對應的IP段？不用資料庫如何實現？要求省空間
9.簡述一致性hash演算法。

1）首先求memcached伺服器（節點）的哈希值，並將其配置到0 232的圓（continuum）。

2）然後採用同樣的方法求出存儲數據的鍵的哈希值，並映射到相同的圓上。

3）然後從數據映射到的位置開始順時針查找，將數據保存到找到的第一個伺服器上。如果超過232仍然找不到伺服器，就會保存到第一台memcached伺服器上。
11.描述一種hash table的實現方法

1） 除法散列法: p ，令 h(k ) = k mod p ，這里， p 如果選取的是比較大的素數，效果比較好。而且此法非常容易實現，因此是最常用的方法。最直觀的一種，上圖使用的就是這種散列法，公式： index = value % 16，求模數其實是通過一個除法運算得到的。

2） 平方散列法 :求index頻繁的操作，而乘法的運算要比除法來得省時。公式： index = (value * value) >> 28 （右移，除以2^28。記法：左移變大，是乘。右移變小，是除）

3） 數字選擇法:如果關鍵字的位數比較多，超過長整型範圍而無法直接運算，可以選擇其中數字分布比較均勻的若干位，所組成的新的值作為關鍵字或者直接作為函數值。

4） 斐波那契（Fibonacci）散列法:平方散列法的缺點是顯而易見的，通過找到一個理想的乘數index = (value * 2654435769) >> 28

沖突處理：令數組元素個數為 S ，則當 h(k) 已經存儲了元素的時候，依次探查 (h(k)+i) mod S , i=1,2,3…… ，直到找到空的存儲單元為止（或者從頭到尾掃描一圈仍未發現空單元，這就是哈希表已經滿了，發生了錯誤。當然這是可以通過擴大數組范圍避免的）。

12、各類樹結構的實現和應用

13、hash，任何一個技術面試官必問（例如為什麼一般hashtable的桶數會取一個素數？如何有效避免hash結果值的碰撞）

不選素數的話可能會造成hash出值的范圍和原定義的不一致

14.什麼是平衡二叉樹?

左右子樹都是平衡二叉樹，而且左右子樹的深度差值的約對值不大於1。

15．數組和鏈表的優缺點

數組，在內存上給出了連續的空間。鏈表，內存地址上可以是不連續的，每個鏈表的節點包括原來的內存和下一個節點的信息(單向的一個，雙向鏈表的話，會有兩個)。

數組優於鏈表的:

A. 內存空間佔用的少。

B. 數組內的數據可隨機訪問，但鏈表不具備隨機訪問性。

C. 查找速度快

鏈表優於數組的:

A. 插入與刪除的操作方便。

B. 內存地址的利用率方面鏈表好。

C. 方便內存地址擴展。

17.最小堆插入，刪除編程實現

18. 4G的long型整數中找到一個最大的，如何做？

每次從磁碟上盡量多讀一些數到內存區，然後處理完之後再讀入一批。減少IO次數，自然能夠提高效率。分批讀入選取最大數，再對緩存的最大數進行快排。

19. 有千萬個string在內存怎麼高速查找，插入和刪除？

對千萬個string做hash，可以實現高速查找，找到了，插入和刪除就很方便了。關鍵是如何做hash，對string做hash，要減少碰撞頻率。

在內存中維護一個大小為10000的最小堆，每次從文件讀一個數，與最小堆的堆頂元素比較，若比堆頂元素大，則替換掉堆頂元素，然後調整堆。最後剩下的堆內元素即為最大的1萬個數，演算法復雜度為O(NlogN)

（1）全局洗牌法

a）首先生成一個數組，大小為54，初始化為1~54

b）按照索引1到54，逐步對每一張索引牌進行洗牌，首先生成一個余數 value = rand %54，那麼我們的索引牌就和這個余數牌進行交換處理

c）等多索引到54結束後，一副牌就洗好了

（2）局部洗牌法：索引牌從1開始，到54結束。這一次索引牌只和剩下還沒有洗的牌進行交換， value = index + rand（） %（54 - index）

演算法復雜度是O(n)

22．請分別用遞歸和非遞歸方法，先序遍歷二叉樹

24.其他各種排序方法

25.哈希表沖突解決方法？

常見的hash演算法如下：

解決沖突的方法：

也叫散列法，主要思想是當出現沖突的時候，以關鍵字的結果值作為key值輸入，再進行處理，依次直到沖突解決

線性地址再散列法

當沖突發生時，找到一個空的單元或者全表

二次探測再散列

沖突發生時，在表的左右兩側做跳躍式的探測

偽隨機探測再散列

同時構造不同的哈希函數

將同樣的哈希地址構造成一個同義詞的鏈表

建立一個基本表和溢出區，凡是和基本元素發生沖突都填入溢出區

六、系統架構

1.設計一個服務，提供遞增的SessionID服務，要求保證服務的高可靠性，有哪些方案？集中式/非集中式/分布式

2.多台伺服器要執行計劃任務，但只有拿到鎖的任務才能執行，有一個中心伺服器來負責分配鎖，但要保證服務的高可靠性。

3.如何有效的判斷伺服器是否存活？伺服器是否踢出集群的決策如何產生？

4.兩個伺服器如何在同一時刻獲取同一數據的時候保證只有一個伺服器能訪問到數據？

可以採用隊列進行處理，寫一個隊列介面保證同一時間只有一個進程能夠訪問到數據，或者對於存取資料庫的來說，資料庫也是可以加鎖處理的

5. 編寫高效伺服器程序，需要考慮的因素

性能對伺服器程序來說是至關重要的了，畢竟每個客戶都期望自己的請求能夠快速的得到響應並處理。那麼影響伺服器性能的首要因素應該是：

（1）系統的硬體資源，比如說CPU個數，速度，內存大小等。不過由於硬體技術的飛速發展，現代伺服器都不缺乏硬體資源。因此，需要考慮的主要問題是如何從「軟環境」來提升伺服器的性能。

伺服器的」軟環境「

（2）一方面是指系統的軟體資源，比如操作系統允許用戶打開的最大文件描述符數量

（3）另一方面指的就是伺服器程序本身，即如何從編程的角度來確保伺服器的性能。

主要就要考慮大量並發的處理這涉及到使用進程池或線程池實現高效的並發模式（半同步/半非同步和領導者/追隨者模式），以及高效的邏輯處理方式--有限狀態機內存的規劃使用比如使用內存池，以空間換時間，被事先創建好，避免動態分配，減少了伺服器對內核的訪問頻率，數據的復制，伺服器程序還應該避免不必要的數據復制，尤其是當數據復制發生在用戶空間和內核空間之間時。如果內核可以直接處理從socket或者文件讀入的數據，則應用程序就沒必要將這些數據從內核緩沖區拷貝到應用程序緩沖區中。這里所謂的「直接處理」，是指應用程序不關心這些數據的具體內容是什麼，不需要對它們作任何分析。比如說ftp伺服器，當客戶請求一個文件時，伺服器只需要檢測目標文件是否存在，以及是否有許可權讀取就可以了，不需要知道這個文件的具體內容，這樣的話ftp伺服器就不需要把目標文件讀入應用程序緩沖區然後調用send函數來發送，而是直接使用「零拷貝」函數sendfile直接將其發送給客戶端。另外，用戶代碼空間的數據賦值也應該盡可能的避免復制。當兩個工作進程之間需要傳遞大量的數據時，我們就應該考慮使用共享內存來在他們直接直接共享這些數據，而不是使用管道或者消息隊列來傳遞。上下文切換和鎖：並發程序必須考慮上下文的切換問題，即進程切換或線程切換所導致的系統開銷。即時I/O密集型伺服器也不應該使用過多的工作線程（或工作進程），否則進程間切換將佔用大量的CPU時間，伺服器真正處理業務邏輯的CPU時間比重就下降了。因此為每個客戶連接都創建一個工作線程是不可取的。應該使用某種高效的並發模式。（半同步半非同步或者說領導者追隨者模式）另一個問題就是共享資源的加鎖保護。鎖通常被認為是導致伺服器效率低下的一個因素，因為由他引入的代碼不僅不處理業務邏輯，而且需要訪問內核資源，因此如果伺服器有更好的解決方案，應該盡量避免使用鎖。或者說伺服器一定非要使用鎖的話，盡量使用細粒度的鎖，比如讀寫鎖，當工作線程都只讀一塊內存區域時，讀寫鎖不會增加系統開銷，而只有當需要寫時才真正需要鎖住這塊內存區域。對於高峰和低峰的伸縮處理，適度的緩存。

6. QQ飛車新用戶注冊時，如何判斷新注冊名字是否已存在？（數量級：幾億)

可以試下先將用戶名通過編碼方式轉換，如轉換64位整型。然後設置N個區間，每個區間為2^64/N的大小。對於新的用戶名，先通過2分尋找該用戶名屬於哪個區間，然後在在這個區間，做一個hash。對於不同的時間復雜度和內存要求可以設置不同N的大小~

加一些基礎的技術面試之外的職業素養的面試問題

1.你在工作中犯了個錯誤，有同事打你小報告，你如何處理？

a.同事之間應該培養和形成良好的同事關系，就是要互相支持而不是互相拆台，互相學習，互相幫助，共同進步。

b.如果小報告里邊的事情都是事實也就是說確實是本人做的不好不對的方面，那麼自己應該有則改之，提高自己。如果小報告里邊的事

情全部不是事實，就是說確實誣陷，那麼應該首先堅持日久見人心的態度，持之以恆的把本職工作做好，然後在必要的時候通過適當的

方式和領導溝通，相信領導會知道的。

2.你和同事合作完成一個任務，結果任務錯過了截止日期，你如何處理？

3.職業規劃？

4.離職原因？

5. 項目中遇到的難題，你是如何解決的?

A．時間 b要求 c.方法

Ⅳ C++有哪些比較大小的排序方法

各種排序演算法

排序演算法是一種基本並且常用的演算法。由於實際工作中處理的數量巨大，所以排序演算法
對演算法本身的速度要求很高。
而一般我們所謂的演算法的性能主要是指演算法的復雜度，一般用O方法來表示。在後面我將
給出詳細的說明。

參考資料：http://cn.codeof.com/articles/programming/vc/1011.htm
介紹了主流的7種排法，有基本實現代碼。

一、排序的基本概念

排序：就是將記錄按關鍵字遞增(遞減)的次序排列起來,形成新的有序序列,稱為排序。設n個記錄的序列為{R1,R2,…,Rn},其相應關鍵字序列為{K1,K2,…,Kn},需確定一種排序P1,P2,…,Pn,使其相應的關鍵字滿足遞增(升序),或遞減(降序)的關系:
Kp1 £ Kp2 £ ...£ Kpn
或
Kp1 ³ Kp2 ³ … ³ Kpn

根據排序元素所在位置的不同,排序分: 內排序和外排序。

http://blog.csdn.net/phpme/archive/2006/06/22/820447.aspx

介紹了5種排法，有設計思想。

Ⅵ hadoop maprece 分桶

老大之前在網路，由於shell 和awk 寫的溜，所以他總是推薦 使用shell 和awk 來跑 hadoop streaming 【hs】，hs還真是一個好東西，不需要編譯，想怎麼執行就怎麼整，還不需要IDE，只要你你記住主要的執行內容就完全沒有問題，hs也支持 python ，這樣一來 hadoop 可以讓所有人都可以使用了。

可以參考這個文章
https://www.programcreek.com/java-api-examples/index.php?api=org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner

https://github.com/roanjain/hadoop-partitioner/blob/master/src/com/mapred/partitioner/PartitionerDemo.java

老大講在網路 執行hs 時經常分桶，用來控制 map 和 Rece 任務的個數，確實還是有幫助的，可以控制 桶的個數，也可以控制資源的使用情況，比如 cpu 和內存

一篇干貨很多的文章可以參考 http://www.cnblogs.com/van19/p/5756448.html

Hadoop用於對key的排序和分桶的設置選項比較多和復雜，目前在公司內主要以KeyFieldBasePartitioner和KeyFieldBaseComparator被hadoop用戶廣泛使用。

基本概念：

Partition：分桶過程，用戶輸出的key經過partition分發到不同的rece里，因而partitioner就是分桶器，一般用平台默認的hash分桶也可以自己指定。
Key：是需要排序的欄位，相同分桶&&相同key的行排序到一起。

下面以一個簡單的文本作為例子，通過搭配不同的參數跑出真實作業的結果來演示這些參數的使用方法。
假設map的輸出是這樣以點號分隔的若干行：

d.1.5.23
e.9.4.5
e.5.9.22
e.5.1.45
e.5.1.23
a.7.2.6
f.8.3.3
我們知道，在streaming模式默認hadoop會把map輸出的一行中遇到的第一個設定的欄位分隔符前面的部分作為key，後面的作為 value，如果輸出的一行中沒有指定的欄位分隔符，則整行作為key，value被設置為空字元串。 那麼對於上面的輸出，如果想用map輸出的前2個欄位作為key，後面欄位作為value，並且不使用hadoop默認的「\t」欄位分隔符，而是根據該 文本特點使用「.」來分割，需要如何設置呢

bin/hadoop streaming -input /tmp/comp-test.txt -output /tmp/xx -mapper cat -recer cat
-jobconf stream.num.map.output.key.fields=2
-jobconf stream.map.output.field.separator=.
-jobconf mapred.rece.tasks=5

結果：

e.9 4.5
f.8 3.3
——————
d.1 5.23
e.5 1.23
e.5 1.45
e.5 9.22
——————
a.7 2.6
總結：
從結果可以看出，在rece的輸出中，前兩列和後兩列用「\t」分隔，證明map輸出時確實把用「.」分隔的前兩列作為key，後面的作為 value。並且前兩列相同的「e.5」開頭的三行被分到了同一個rece中，證明確實以前兩列作為key整體做的partition。
stream.num.map.output.key.fields 設置map輸出的前幾個欄位作為key
stream.map.output.field.separator 設置map輸出的欄位分隔符

KeyFieldBasePartitioner的用法

如果想要靈活設置key中用於partition的欄位，而不是把整個key都用來做partition。就需要使用hadoop中的org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner了。
下面只用第一列作partition，但依然使用前兩列作為key。

bin/hadoop streaming -input /tmp/comp-test.txt -output /tmp/xx -mapper cat -recer cat
-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner
-jobconf stream.num.map.output.key.fields=2
-jobconf stream.map.output.field.separator=.
-jobconf map.output.key.field.separator=.
-jobconf num.key.fields.for.partition=1
-jobconf mapred.rece.tasks=5
結果：

d.1 5.23
——————
e.5 1.23
e.5 1.45
e.5 9.22
e.9 4.5
——————
a.7 2.6
f.8 3.3
總結：
從結果可以看出，這次「e」開頭的行都被分到了一個桶內，證明做partition是以第一列為準的，而key依然是前兩列。並且在同一個 partition內，先按照第一列排序，第一列相同的，按照第二列排序。這里要注意的是使用 map.output.key.field.separator來指定key內欄位的分隔符，這個參數是KeyFieldBasePartitioner 和KeyFieldBaseComparator所特有的。
map.output.key.field.separator 設置key內的欄位分隔符
num.key.fields.for.partition 設置key內前幾個欄位用來做partition

事實上KeyFieldBasePartitioner還有一個高級參數 mapred.text.key.partitioner.options，這個參數可以認為是 num.key.fields.for.partition的升級版，它可以指定不僅限於key中的前幾個欄位用做partition，而是可以單獨指定 key中某個欄位或者某幾個欄位一起做partition。
比如上面的需求用mapred.text.key.partitioner.options表示為
mapred.text.key.partitioner.options=-k1,1
注意mapred.text.key.partitioner.options和num.key.fields.for.partition不需要一起使用，一起使用則以num.key.fields.for.partition為准。

這里再舉一個例子，使用mapred.text.key.partitioner.options

bin/hadoop streaming -input /tmp/comp-test.txt -output /tmp/xx -mapper cat -recer cat
-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner
-jobconf stream.num.map.output.key.fields=3
-jobconf stream.map.output.field.separator=.
-jobconf map.output.key.field.separator=.
-jobconf mapred.text.key.partitioner.options=-k2,3
-jobconf mapred.rece.tasks=5
結果：

e.9.4 5
——————
a.7.2 6
e.5.9 22
——————
d.1.5 23
e.5.1 23
e.5.1 45
f.8.3 3
可見，這次是以前3列作為key的，而partition則以key中的第2-3列，因此以「e」開頭的行被拆散了，但第二三列相同的「5，1」被 分到一個桶內。在同一個桶內，依然是從key的第一列開始排序的，注意，KeyFieldBasePartitioner隻影響分桶並不影響排序。
mapred.text.key.partitioner.options 設置key內某個欄位或者某個欄位范圍用做partition

KeyFieldBaseComparator的用法

首先簡單解釋一下hadoop框架中key的comparator，對於hadoop所識別的所有java的key類型（在框架看來key的類型只 能是java的），很多類型都自定義了基於位元組的比較器，比如Text，IntWritable等等，如果不特別指定比較器而使用這些類型默認的，則會將 key作為一個整體的位元組數組來進行比較。而KeyFieldBaseComparator則相當於是一個可以靈活設置比較位置的高級比較器，但是它並沒 有自己獨有的比較邏輯，而是使用默認Text的基於字典序或者通過-n來基於數字比較。
之前的例子使用KeyFieldBasePartitioner自定義了使用key中的部分欄位做partition，現在我們通過org.apache.hadoop.mapred.lib.KeyFieldBasedComparator來自定義使用key中的部分欄位做比較。

這次把前四列都作為key，前兩列做partition，排序依據優先依據第三列正序(文本序)，第四列逆序(數字序)的組合排序。

bin/hadoop streaming -input /tmpcomp-test.txt -output /tmp/xx -mapper cat -recer cat
-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner
-jobconf mapred.output.key.comparator.class=org.apache.hadoop.mapred.lib.KeyFieldBasedComparator
-jobconf stream.num.map.output.key.fields=4
-jobconf stream.map.output.field.separator=.
-jobconf map.output.key.field.separator=.
-jobconf mapred.text.key.partitioner.options=-k1,2
-jobconf mapred.text.key.comparator.options="-k3,3 -k4nr"
-jobconf mapred.rece.tasks=5
結果：

e.5.1.45
e.5.1.23
d.1.5.23
e.5.9.22
——————
a.7.2.6
——————
f.8.3.3
e.9.4.5
總結：
從結果可以看出，符合預期的按照先第三列文本正序，然後第四列基於數字逆序的排序。
另外注意，如果這種寫法
mapred.text.key.comparator.options=」-k2″
則會從第二列開始，用字典序一直比較到key的最後一個位元組。所以對於希望准確排序欄位的需求，還是使用「k2,2」這種確定首尾范圍的形式更好。另外如果給定的key中某些行需要排序的列數不夠時，會比較到最後一列，缺列的行默認缺少的那一列排序值最小。
mapred.text.key.comparator.options 設置key中需要比較的欄位或位元組范圍

Ⅶ 選擇排序法復雜度

穩定性比較
插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的。
選擇排序、希爾排序、快速排序、堆排序是不穩定的。

時間復雜性比較
插入排序、冒泡排序最優為O(n),最壞為O(n^2),平均O(n^2）；
快速排序最優為O(nlogn),最壞為O(n^2),平均O(nlogn);
堆排序最優為O(nlogn),最壞為O(nlogn),平均O(nlogn);
線形排序的時間復雜性為O(n)。

輔助空間的比較
線形排序、歸並排序的輔助空間為O(n),快速排序的輔助空間為O(logn),其它排序的輔助空間為O(1)。

其它比較
插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。
反而在這種情況下，快速排序反而慢了。當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。
若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許時用桶排序。
當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下宜用歸並排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。

演算法描述太長了。
binary seach 二分查找啊。

6 層排序 乘3加1 Shell Sort Times 3 plus 1

7 層排序 乘4 Shell Sort Times 4
層排序？ 看名字是 希爾排序吧。

還有上面的名字也翻譯錯了。。。
這些演算法都很容易搜到的。

給你個網址吧：

http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

不過是用PASCAL語言描述的，部分C++語言描述。

// 直接插入排序
void insertionSort( int *array )
{
int i, j;
int key;

for( i = 1; i < size; ++i )
{
key = array[i];
j = i - 1;
while( j >= 0 && array[j] > key )
{
array[j+1] = array[j];
--j;
}
array[j+1] = key;
}
}

// 折半插入排序
void binary_insertiont_sort( int *array )
{
for( int i = 1; i < size; ++i )
{
int key = array[i];
int low = 0;
int high = i - 1;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else
low = mid + 1;
}
for( int j = i - 1; j > high + 1; --j )
array[j+1] = array[j];
array[j] = key;
}
}

// 選擇排序
void selectSort( int *array )
{
int i, j, k;

for( i = 0; i < size - 1; ++i )
{
k = i;
for( j = i + 1; j < size; ++j )
if( array[k] > array[j] )
k = j;
if( k != i )
{
j = array[k];
array[k] = array[i];
array[i] = j;
}
}
}

// 二分查找法
void binarySeach( int *array, int key )
{
int low = 0;
int high = n - 1; // n是array的長度
int flag = 0;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else if( array[mid] < key )
low = mid + 1;
else
{
printf( "%d\n", mid+1 );
flag = 1;
break;
}
}
if( !flag )
printf( "NOFOUND!\n" );
}

其他的還沒寫。。