待解決題：

selenium的機制。Socket編程，http，web Service

例如你認為最成功的項目是？為什么？

你的優缺點？（我就倒在了這個上邊）

百度貼吧，你怎么進行測試？

百度的登錄你怎么測試？

項目中有什么困難？如何克服的？

海量數據

• http://blog.csdn.net/v_july_v/article/details/7382693

• 如果日志文件足夠的大，大到不能完全加載到內存中的話。
  那么可以考慮分而治之的策略，按照 關鍵詞 地址的hash(關鍵詞)%1024值，將海量日志存儲到1024個小文件中。每個小文件最多包含4M個 關鍵詞 。 對于每個小文件，可以構建一個 關鍵詞 作為key，出現次數作為value的hash_map，并記錄當前出現次數最多的1個 關鍵詞 。 有了1024個小文件中的出現次數最多的 關鍵詞 ，我們就可以輕松得到總體上出現次數最多的 關鍵詞 。

• 搜索大文件放不下時，可以按照規則將大文件分割成內存可以放下的小文件，然后依次將小文件調入內存，進行搜索。如果對于搜索結果有一定限制，比如找到出現次數最多的關鍵字，分隔文件時hash將相同關鍵字放到同一文件，對每一小文件統計最多次數，然后再比較所有小文件。

  一個非常大的文件（50億，總之就是不能一次讀取到內存中去），里邊存儲這各種數字。要求除去文件中所有重復的。

編程題， log2n = M, 求n的整數部分。

字符串按字母a-z排序

為二叉樹中每一個節點簡歷他的右鄰居節點

已解決題：

21、

20、http返回碼類型

• 1×× 　　保留
  
• 2×× 　　表示請求成功地接收。 200
• 3×× 　　為完成請求客戶需進一步細化請求
  
• 4×× 　　客戶錯誤。400bad request；404notfound
• 5×× 　　服務器錯誤。500

19、已知一個亂序的整數數組,求該數組排序相鄰兩數的最大間隔, 要求時間復雜度為O（n）

• 要求時間復雜度，無法用其他排序，采用桶排序的思路
• 遍歷找到數列最大值最小值（min,max)，則所求gap>=(max-min)/(n-1)，以gap=(max-min)/(n-1)建立n個桶，將數組按照所在區間存入桶中，找出每個桶中的最大值最小值，然后按順序對每個相鄰的桶進行區間比較，取最大值。
• 若要求求最小間隔？用桶排序，然后找間隔最小值

18、求兩個相同大小已排序數組的中位數

http://blog.csdn.net/alexingcool/article/details/7932441

• 引申：給定一個未排序的整數數組，找到其中位數。

17、 10進制數轉2進制數的方法數，0、1、2

• 二進制考慮：
• 當為奇數時，二進制的最末位數一定為1，則表達方式等于除最低位后的其他位，其他位可以用該數-1后除以2得到，即奇數時，f(n)=f((n-1)/2)
• 當為偶數時，二進制的最末位數可為0或2，則表達方式等于除最低位后的其他位，其他位可以用該數除以2或-2除以2得到，即偶數時，f(n)=f(n/2)+f((n-2)/2)

16、兩個字符串，判斷其中一個字符串是不是另一個字符串的右移子串。如cda是abcd的右移子串。

我們判斷s2是否可以通過s1循環移位得到包含，則只需要判斷s1s1中是否含有s2即可以。
用提高空間復雜度來換取時間復雜度的減低的目的。
java代碼如下：

public class StrigMove{ public static void main (String[] args) { String s1="AABCD"; String s2="CDAA"; if(s1.concat(s1).indexOf(s2)!=-1){ System.out.println ("true"); }else{ System.out.println ("false"); } } }

15、一幢 100 層的大樓,給你兩個雞蛋. 如果在第 n 層扔下雞蛋,雞蛋不碎,那么從前 n-1 層扔雞蛋都不碎. 這兩只雞蛋一模一樣,不碎的話可以扔無數次. 已知雞蛋在0層扔不會碎.

• http://ppwwyyxx.com/2013/Problem-of-Two-Eggs/
• 如果第一次扔在k層, 第二次應該高k?1層, 這可以有直觀一點的理解: 每扔一次, 就要更保守一些, 所以讓區間長度少1. 可以繼續得到, 下一次應該增高k?2, 再下一次應該增高k?3. 考慮:

k+(k?1)+?+1=k(k+1)2=100?k≈14

14、最長連續子序列之和，環形數組的最大子序列之和,一個數列，要求求出最大的連續子序列。

最長連續子序列之和

• 問題描述：一個整型數組，數組里有正數也有負數。數組中連續的一個或多個整數組成一個子數組，每個子數組都有一個和，求所有子數組的和的最大值。注意：當全是負數的情況時，返回最大的那個負數
• 這個問題的思路其實非常簡單，從左到右掃描數組，在掃描過程中，記錄數組的負數的個數和掃描過中數據中的最大值，并累加每個掃描到的數據的和，假設用變量thisSum（初值為0）保存，如果當前的累加值大于之前的累加值的最大值 （例如用變量sum記錄，初值為0），則把當前的最大值保存為最大值（sum = thisSum），如果thisSum小于0，則把thisSum設置為0并重新進行累加。一直這樣掃描數組，直到把數組掃描完。

由于thisSum已經小于0，也就是說之前統計的和可以舍棄，因為把當前的元素累加之后，結果反而小了。例如把數組分成三部分AiB，因為A的值大于0，A+i的值小于0，所以如果從B開始從新累加，則其值一定比包括i然后去累加B的結果大，因為i小于0，而B中的和卻不一定比在A之前累加的和大。

由于如果數組全是負數時，要返回最大的負數，而從上面所說的說法中，我們可以看到當前累加總和（thisSum）總是與0進行比較，如果小于0則把thisSum置為0，所以當數組全是負數時，thisSum和數組的最大子序列之和（sum）總是為0，而與現實有點不一樣，所以就要記錄負數的數量，當負數的數量等于元素的個數（即全是負數）時，就要把最大連續子序列和置為最大的負數。這也是前面所說的，在掃描過程中記錄負數的個數和最大元素的作用。

int MaxSum(int* a,int n) { int sum = 0; //用于記錄最大的連續子數組和 int flag = 0;//用于記錄負數的個數 int MaxNum = *a;//用于記錄數組中最大的數 int ThisSum = 0;//用于記錄當前的連續子數組和 for(int i = 0; i < n; ++i) { if(a[i] < 0) //如果無素為負數，則把flag的值加1 ++flag; if(MaxNum < a[i]) //記錄數組當前的最大值 MaxNum = a[i]; ThisSum += a[i]; //累加更新當前的子數組之和 if(ThisSum > sum) { //若當前連續子數組之和大于記錄的子數組之和 //則設置最大連續子數組之和為當前的和 sum = ThisSum; } else if(ThisSum < 0) { //如果當前連續子數組之和小于0，則拋棄之前的連續子數組， //從此元素的下一個元素重新計算連續子數組之和 ThisSum = 0; } } //若全是負數，最大值為數組中的最大無素 if(flag == n) sum = MaxNum; return sum; }

求最小子數組和

import lib.StdIn; import lib.StdOut;/*** Created by ting on 16/3/29.*/ public class minSum {public static int minSumOfArray(int[] a, int n){int sum = 0;int flag = 0;int minNum = a[0];int thisSum = 0;for(int i = 0; i < n; ++i){if(a[i] > 0) ++flag;if(minNum > a[i]) minNum = a[i];thisSum += a[i];if(thisSum < sum){sum = thisSum;}else if(thisSum > 0){thisSum = 0;}}if(flag == n) sum = minNum;return sum;}public static void main(String[] args){int[] a = new int[6];for (int i =0; i < 6; i ++)a[i] = StdIn.readInt();StdOut.println(minSumOfArray(a, 6));} }

環形數組的最大子序列之和

• 解法一：

把該環形數組從某一點展開，連寫兩遍（復制一份接到自己后面），然后當成無環的數組求最大子數組和，但這里要限制一個條件，就是最大子數組的長度不可以超過n，所以求的時候要注意判斷。 例如：上圖中展開寫兩遍為a1,a2,a3,a4,a1,a2,a3,a4。 這種情況下限定最大子數組的長度不可以超過n的作用：假如數組為{-1,2,3,4}，則展開復制一份接到自己后面為-1,2,3,4,-1,2,3,4，此時若直接求則為2,3,4,-1,2,3,4，很明顯不對了，所以要限定最大子數組的長度不可以超過n。

• 解法二：

這個問題的最優解一定是以下兩種可能。 可能一：最優解沒有跨過a[n-1]到a[0]，即和非環形數組一樣了。 可能二：最優解跨過a[n-1]到a[0]，新問題。 對于第一種情況，我們可以按照非環形數組求法來求，為max1；對于第二種情況，可以將原問題轉化為數組的最小子數組和問題，再用數組全部元素的和減去最小子數組和，那么結果一定是跨過a[n-1]到a[0]情況中最大的子數組和，設為max2。最終結果即為max1與max2中較大的那個。 例1：有數組6、-1、-6、8、2 求得max1=10，max2=16，則取較大的max2作為結果。 例2：有數組-6、8、2、6、-1 求得max1=16，max2=15，則取較大的max1作為結果。 為什么這樣求：數組元素“sum - 最小子數組和 = 跨過a[n-1]到a[0]情況中的最大子數組和”這一點有些疑問。我們可以這樣理解：n個數的和是一定的，那么如果我們在這n個數中找到連續的一段數，并且這段數是所有連續的數的和最小的，那么“sum-最小子段和”的結果一定最大。故求得：跨過a[n-1]到a[0]情況中的最大子數組和。

13、回文數算法

判斷是否為回文數

static boolean isPN(int num) {int o = num;int tmp = 0;//使用循環把數字順序反轉while(num != 0) {tmp *= 10;tmp += num % 10;num /= 10;}//如果原始數與反轉后的數相等則返回trueif(tmp == o) return true;return false; }

查詢第n個回文數

• 解法一：從1開始，判斷該數是否是回文數，然后用一個計數器記下回文數，一直到計數器得到N，返回第N個回文數。（性能差）

• 解法二：
  回文數的個數其實是有規律的。如：

  1位回文數： 9個

  2位回文數： 9個

  3位回文數： 90個

  4位回文數： 90個

  5位回文數： 900個

  6位回文數： 900個

  …

  我們看到9、90、900，是不是很有規律，那是什么原因？很簡單，我們把回文數拆開兩半[123321]來看。兩半的變化一樣的，那我們只算其中一半就行了。首位不能是0，所以左半最小為100，最大為999，共有999-100=900個，如此類推。

  所以我們可以基于以下原則：

  1、 回文數的數位每增長2，回文數的個數為原來的10倍。如從個位回文數到百位回文數，個數從9個變為90個。

  2、 個位回文數的個數是9，1、2、3、…、9。

  總之理解原理后一切好辦，步驟就偷懶不寫了，看代碼吧！

核心代碼： static long find(int index) {int count = 0; int number = 9; //記錄數位上的回文數，如個位回文數為9int w = 0; //記錄數位long half; //保存回文數的左半邊的結果long h = 1; //回文數的左半邊的起始基數long res; //結果while(true) {if(w > 0 && w%2 == 0) { //每進兩個數位，回文數乘以10number *= 10;}w++; //數位加一if(count + number > index) //回文數大于查找的回數,跳出break;count += number; //回文數加上當前數位上的回文數}index -= count; //在當前數位上的位置。如w=5,index=50,則萬位上的第50個回文數是我們所求for(int i = 0; i < (w-1) / 2; i++) { //求回文數的左半邊的基數，如回文數在萬位上，則為100h *= 10;}half = h + index; //回文數的左半邊，如100 + 50 = 150res = half;if(w%2 != 0) //如果為奇數，則中間那個數不必算入右半邊了！half /=10;while(half != 0) { //拼接回文數res = res *10 + half % 10;half /= 10;}return res;}

12、get和post的區別

• 我們可以這樣認為：一個URL地址，它用于描述一個網絡上的資源，而HTTP中的GET，POST，PUT，DELETE就對應著對這個資源的查，改，增，刪4個操作。
• 根據HTTP規范，GET用于信息獲取，而且應該是安全的和冪等的。
• 根據HTTP規范，POST表示可能修改變服務器上的資源的請求。
• GET請求的數據會附在URL之后（就是把數據放置在HTTP協議頭中），以?分割URL和傳輸數據，參數之間以&相連，如：login.action?name=hyddd&password=idontknow&verify=%E4%BD%A0%E5%A5%BD。如果數據是英文字母/數字，原樣發送，如果是空格，轉換為+，如果是中文/其他字符，則直接把字符串用BASE64加密，得出如：%E4%BD%A0%E5%A5%BD，其中％XX中的XX為該符號以16進制表示的ASCII。POST把提交的數據則放置在是HTTP包的包體中。
• POST的安全性要比GET的安全性高。注意：這里所說的安全性和上面GET提到的“安全”不是同個概念。上面“安全”的含義僅僅是不作數據修改，而這里安全的含義是真正的Security的含義，比如：通過GET提交數據，用戶名和密碼將明文出現在URL上，因為(1)登錄頁面有可能被瀏覽器緩存，(2)其他人查看瀏覽器的歷史紀錄，那么別人就可以拿到你的賬號和密碼了，除此之外，使用GET提交數據還可能會造成Cross-site request forgery攻擊。

11、給出一個字符串，求最長對稱子字符串的長度，如輸入google，則輸出為4。

• （1）怎樣判斷一個字符串是不是對稱的字符串?我們可以用兩個指針分別指向字符串的第一個字符和最后一個字符，判斷是否相等，如果不等直接返回false，如果為真則接著比較下一對字符。（2）如果遍歷遍歷原字符串的所有子串，首先我們讓一個指針從頭至尾遍歷，對于這個指針的每一個字符，我們在用另一個指針逐一指向它后面的每一個字符即可。
• 如果我們從內向外比較字符，那么對于aba型的字符串，如果我們判斷了b是對稱的，只需要再左右各移一位就可以判斷下一個字符串是否是對稱的，這樣我們就能避免重復；然而我們需要注意的是，對于原字符串中每一個字符有兩種情況，一種是子串是以單個字符為中心對稱分布的，換句話說，子串的長度是奇數；另一種情況是子串以兩個字符串為中心，即子串的長度是偶數。

10、有這樣一個數組A，大小為n，相鄰元素差的絕對值都是1。如：A={4,5,6,5,6,7,8,9,10,9}。現在，給定A和目標整數t，請找到t在A中的位置。

數組第一個數為array[0], 要找的數為y，設t = abs(y - array[0])。由于每個相鄰的數字之差的絕對值為1。故第t個位置之前的數肯定都比y小。因此直接定位到array[t]，重新計算t，t = abs(y – array[t])，再重復上述步驟即可。這種算法主要利用了當前位置的數與查找數的差來實現跨越式搜索。算法效率要比遍歷數組的算法要高一些，并且易于實現。

9、現在有一個數組，已知一個數出現的次數超過了一半，請用O(n)的復雜度的算法找出這個數。

答案1：

• 創建一個hash_map，key為數組中的數，value為此數出現的次數。遍歷一遍數組，用hash_map統計每個數出現的次數，并用兩個值存儲目前出現次數最多的數和對應出現的次數。
  這樣可以做到O(n)的時間復雜度和O(n)的空間復雜度，滿足題目的要求。
  但是沒有利用“一個數出現的次數超過了一半”這個特點。也許算法還有提高的空間。

答案2：

• 使用兩個變量A和B，其中A存儲某個數組中的數，B用來計數。開始時將B初始化為0。
  遍歷數組，如果B=0，則令A等于當前數，令B等于1；如果當前數與A相同，則B=B+1；如果當前數與A不同，則令B=B-1。遍歷結束時，A中的數就是要找的數。
  這個算法的時間復雜度是O(n)，空間復雜度為O(1)。
  這道題也可以這么解，先兩兩比較，如果相同則留下，如果不同則兩個都刪除，則一遍之后，那個多于一半的數在剩下的里面還是多于一半，然后再重復上述過程，直到最后
  由于出現過半，所求數肯定是出現次數最多的數，即轉化為“求出現次數最多的數”，利用hashmap， O(N)時間內可以求得。

8、兩個白帽兩個黑帽

第二個人

7、兩個單鏈表判斷是否相交

判斷兩個鏈表是否相交有什么用呢？這是因為一旦兩個鏈表出現相交的情況，就可能發生這樣的情況，程序釋放了鏈表La的所有節點，這樣就導致了另外一個與之有相交節點的鏈表Lb中的節點也釋放了，而Lb的使用者，可能并不知道事實的真相，這會帶來很大的麻煩。

1.問題分析

　　看看兩個鏈表相交到底是怎么回事吧，有這樣的的幾個事實：（假設鏈表中不存在環）

　　（1）一旦兩個鏈表相交，那么兩個鏈表中的節點一定有相同地址。

　　（2）一旦兩個鏈表相交，那么兩個鏈表從相交節點開始到尾節點一定都是相同的節點。

　　分析出來了問題的本質，那么思路也就自然有了。

2.問題解法

2.1 哈希解法：

　　既然連個鏈表一旦相交，相交節點一定有相同的內存地址，而不同的節點內存地址一定是不同的，那么不妨利用內存地址建立哈希表，如此通過判斷兩個鏈表中是否存在內存地址相同的節點判斷兩個鏈表是否相交。具體做法是：遍歷第一個鏈表，并利用地址建立哈希表，遍歷第二個鏈表，看看地址哈希值是否和第一個表中的節點地址值有相同即可判斷兩個鏈表是否相交。

　　時間復雜度O(length1 + length2)

　　空間復雜度O(length1)

　　分析：時間復雜度是線性的，可以接受，并且可以順便找到第一個相交節點，但是卻增加了O（length1）的空間復雜度，這顯然不能令人滿意。

2.2 問題化

　　如果兩個鏈表中存在相交節點，那么將第二個鏈表接到第一個鏈表的后面，然后從第二個鏈表的表頭開始遍歷，如果存在環，則遍歷過程一定會回到鏈表二的表頭節點。可是這種方法似乎并不能找到第一個相交節點。怎么辦呢？怎樣才能判斷鏈表中是否存在環，并且找到環的開始節點呢？

　　網上看到了這樣的一個解法：設置兩個指針fast和slow，初始值都指向頭，slow每次前進一步，fast每次前進二步，如果鏈表存在環，則fast必定先進入環，而slow后進入環，兩個指針必定相遇。(當然，fast先行頭到尾部為NULL，則為無環鏈表)

　　下面看看怎么找環的入口，當fast與slow相遇時，slow肯定沒有走遍歷完鏈表，而fast已經在環內循環了n圈(1<=n)。假設slow走了s步，則fast走了2s步（fast步數還等于s 加上在環上多轉的n圈），設環長為r，則： 2s = s + nr s= nr 設整個鏈表長L，入口環與相遇點距離為x，起點到環入口點的距離為a。 a + x = nr a + x = (n – 1)r +r = (n-1)r + L - a a = (n-1)r + (L – a – x) (L – a – x)為相遇點到環入口點的距離，由此可知，從鏈表頭到環入口點等于(n-1)循環內環+相遇點到環入口點（從相遇點向后遍歷循環回到入口點的距離），于是我們從鏈表頭、與相遇點分別設一個指針，每次各走一步，兩個指針必定相遇，且相遇點為環入口點，也即為兩個鏈表的第一個相同節點。

2.3 抓住要點

　　不妨遍歷每個鏈表保存最后一個節點，看看最后一個節點是否是同一個節點，這種情況時間復雜度是O（length1 + length2）。基本也不需要什么空間，似乎是一個不錯的想法哦，那么怎么找到第一個相交節點呢？可以遍歷的過程中記錄鏈表的長度L1和L2(假設L1>L2)這是遍歷找到第一個鏈表中的第L1 - L2節點，然后鏈表一從第L1-L2個節點開始遍歷，鏈表二從第一個節點遍歷，每次前進一步，直到找到第一個相同的節點，則可以認為兩個鏈表存在相交節點，并且該點即為第一個相交節點（原來這里寫錯了，感謝Ider指出這個錯誤）。這種解法的時間復雜度也是線性的，但是如果兩個鏈表長度相差不多時，時間復雜度還是不錯的。

2.4 baidu曾經出過這樣的一個筆試題目，歸根到底也是找到兩個鏈表是否存在相同的節點，但是數據量很大，即鏈表長度是上億的。想想那么應該怎么處理呢？

6、靜態測試和動態測試

靜態方法是指不運行被測程序本身，僅通過分析或檢查源程序的語法、結構、過程、接口等來檢查程序的正確性。對需求規格說明書、軟件設計說明書、源程序做結構分析、流程圖分析、符號執行來找錯。靜態方法通過程序靜態特性的分析，找出欠缺和可疑之處，例如不匹配的參數、不適當的循環嵌套和分支嵌套、不允許的遞歸、未使用過的變量、空指針的引用和可疑的計算等。靜態測試結果可用于進一步的查錯，并為測試用例選取提供指導。
動態測試方法是指通過運行被測程序，檢查運行結果與預期結果的差異，并分析運行效率和健壯性等性能，這種方法由三部分組成：構造測試實例、執行程序、分析程序的輸出結果。

5、關于四棵樹，怎么栽種這四棵樹可以使任意兩棵之間的舉例都相等

• 空間問題，一個三棱柱

4、寫一個程序，判斷單鏈表中是否有環。

1、如何判斷是否存在環？
2、如何知道環的長度？
3、如何找出環的連接點在哪里？
4、帶環鏈表的長度是多少？

• 1、對于問題1，使用追趕的方法，設定兩個指針slow、fast，從頭指針開始，每次分別前進1步、2步。如存在環，則兩者相遇；如不存在環，fast遇到NULL退出。
• 2、對于問題2，記錄下問題1的碰撞點p，slow、fast從該點開始，再次碰撞所走過的操作數就是環的長度s。
• 3、問題3：有定理：碰撞點p到連接點的距離=頭指針到連接點的距離，因此，分別從碰撞點、頭指針開始走，相遇的那個點就是連接點。(證明在后面附注)
• 4、問題3中已經求出連接點距離頭指針的長度，加上問題2中求出的環的長度，二者之和就是帶環單鏈表的長度

3、N個臺階，一次可以走一步或者兩步，求走這n個臺階有多少種方法。

斐波那契數列

• 一次可以走一步、兩步...N步，求有多少種方法

2、在瀏覽器中輸入url回車后，整個處理流程是如何的？

作為一個軟件開發者，你一定會對網絡應用如何工作有一個完整的層次化的認知，同樣這里也包括這些應用所用到的技術：像瀏覽器，HTTP，HTML，網絡服務器，需求處理等等。
本文將更深入的研究當你輸入一個網址的時候，后臺到底發生了一件件什么樣的事～

首先嘛，你得在瀏覽器里輸入要網址:

瀏覽器查找域名的IP地址
導航的第一步是通過訪問的域名找出其IP地址。DNS查找過程如下：

• 瀏覽器緩存 – 瀏覽器會緩存DNS記錄一段時間。 有趣的是，操作系統沒有告訴瀏覽器儲存DNS記錄的時間，這樣不同瀏覽器會儲存個自固定的一個時間（2分鐘到30分鐘不等）。
• 系統緩存 – 如果在瀏覽器緩存里沒有找到需要的記錄，瀏覽器會做一個系統調用（windows里是gethostbyname）。這樣便可獲得系統緩存中的記錄。
• 路由器緩存 – 接著，前面的查詢請求發向路由器，它一般會有自己的DNS緩存。
  ISP DNS 緩存 – 接下來要check的就是ISP緩存DNS的服務器。在這一般都能找到相應的緩存記錄。

• 遞歸搜索 – 你的ISP的DNS服務器從跟域名服務器開始進行遞歸搜索，從.com頂級域名服務器到Facebook的域名服務器。一般DNS服務器的緩存中會有.com域名服務器中的域名，所以到頂級服務器的匹配過程不是那么必要了。
  

• DNS有一點令人擔憂，這就是像wikipedia.org或者facebook.com這樣的整個域名看上去只是對應一個單獨的IP地址，不過事實上后面可能對應著多個ip地址（也是學習到了，一個ip地址可以對應多個域名聽說一個IP可以綁定多個域名，那么…? - 互聯網，一個域名也可以對應多個ip地址負載均衡實現，一個域名對應多個IP地址，cry！）還好，有幾種方法可以消除這個瓶頸：
  • 循環 DNS 是DNS查找時返回多個IP時的解決方案。舉例來說，Facebook.com 實際上就對應了四個IP地址。
• 負載平衡器 是以一個特定IP地址進行偵聽并將網絡請求轉發到集群服務器上的硬件設備。 一些大型的站點一般都會使用這種昂貴的高性能負載平衡器。地理 DNS根據用戶所處的地理位置，通過把域名映射到多個不同的IP地址提高可擴展性。這樣不同的服務器不能夠更新同步狀態，但映射靜態內容的話非常好。

• Anycast是一個IP地址映射多個物理主機的路由技術。 美中不足，Anycast與TCP協議適應的不是很好，所以很少應用在那些方案中。
  大多數DNS服務器使用Anycast來獲得高效低延遲的DNS查找。

關于DNS的獲取流程，我想再補充些知識： DNS是應用層協議，事實上他是為其他應用層協議工作的，包括不限于HTTP和SMTP以及FTP，用于將用戶提供的主機名解析為ip地址。 具體過程如下： ①用戶主機上運行著DNS的客戶端，就是我們的PC機或者手機客戶端運行著DNS客戶端了 ②瀏覽器將接收到的url中抽取出域名字段，就是訪問的主機名，比如 http://www.baidu.com/ , 并將這個主機名傳送給DNS應用的客戶端 ③DNS客戶機端向DNS服務器端發送一份查詢報文，報文中包含著要訪問的主機名字段（中間包括一些列緩存查詢以及分布式DNS集群的工作） ④該DNS客戶機最終會收到一份回答報文，其中包含有該主機名對應的IP地址 ⑤一旦該瀏覽器收到來自DNS的IP地址，就可以向該IP地址定位的HTTP服務器發起TCP連接

DNS服務的體系架構是怎樣的？

DNS domain name system 主要作用就是將主機域名轉換為ip地址

假設運行在用戶主機上的某些應用程序（如Webl瀏覽器或者郵件閱讀器）需要將主機名轉換為IP地址。這些應用程序將調用DNS的客戶機端，并指明需要被轉換的主機名。（在很多基于UNIX的機器上，應用程序為了執行這種轉換需要調用函數gethostbyname（））。用戶主機的DNS客戶端接收到后，向網絡中發送一個DNS查詢報文。所有DNS請求和回答報文使用的UDP數據報經過端口53發送（至于為什么使用UDP，請參看為什么域名根服務器只能有13臺呢？ - 郭無心的回答）經過若干ms到若干s的延時后，用戶主機上的DNS客戶端接收到一個提供所希望映射的DNS回答報文。這個查詢結果則被傳遞到調用DNS的應用程序。因此，從用戶主機上調用應用程序的角度看，DNS是一個提供簡單、直接的轉換服務的黑盒子。但事實上，實現這個服務的黑盒子非常復雜，它由分布于全球的大量DNS服務器以及定義了DNS服務器與查詢主機通信方式的應用層協議組成。

瀏覽器給web服務器發送一個HTTP請求

因為像Facebook主頁這樣的動態頁面，打開后在瀏覽器緩存中很快甚至馬上就會過期，毫無疑問他們不能從中讀取。
所以，瀏覽器將把一下請求發送到Facebook所在的服務器：

GET http://facebook.com/ HTTP/1.1 Accept: application/x-ms-application, image/jpeg, application/xaml+xml, [...] User-Agent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; WOW64; [...] Accept-Encoding: gzip, deflate Connection: Keep-Alive Host: facebook.com Cookie: datr=1265876274-[...]; locale=en_US; lsd=WW[...]; c_user=2101[...]

GET 這個請求定義了要讀取的URL：
“http://facebook.com/”
。 瀏覽器自身定義 (User-Agent 頭)， 和它希望接受什么類型的相應 (Accept and Accept-Encoding 頭). Connection頭要求服務器為了后邊的請求不要關閉TCP連接。
請求中也包含瀏覽器存儲的該域名的cookies。可能你已經知道，在不同頁面請求當中，cookies是與跟蹤一個網站狀態相匹配的鍵值。這樣cookies會存儲登錄用戶名，服務器分配的密碼和一些用戶設置等。Cookies會以文本文檔形式存儲在客戶機里，每次請求時發送給服務器。

用來看原始HTTP請求及其相應的工具很多。作者比較喜歡使用fiddler，當然也有像FireBug這樣其他的工具。這些軟件在網站優化時會幫上很大忙。

除了獲取請求，還有一種是發送請求，它常在提交表單用到。發送請求通過URL傳遞其參數
(e.g.: RoboZZle stats for puzzle 85)
。發送請求在請求正文頭之后發送其參數。
像
“http://facebook.com/”
中的斜杠是至關重要的。這種情況下，瀏覽器能安全的添加斜杠。而像
“http: //example.com/folderOrFile”
這樣的地址，因為瀏覽器不清楚folderOrFile到底是文件夾還是文件，所以不能自動添加 斜杠。這時，瀏覽器就不加斜杠直接訪問地址，服務器會響應一個重定向，結果造成一次不必要的握手。

facebook服務的永久重定向響應

Facebook服務器發回給瀏覽器的響應：
HTTP/1.1 301 Moved Permanently Cache-Control: private, no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Expires: Sat, 01 Jan 2000 00:00:00 GMT Location: http://www.facebook.com/ P3P: CP="DSP LAW" Pragma: no-cache Set-Cookie: made_write_conn=deleted; expires=Thu, 12-Feb-2009 05:09:50 GMT; path=/; domain=.facebook.com; httponly Content-Type: text/html; charset=utf-8 X-Cnection: close Date: Fri, 12 Feb 2010 05:09:51 GMT Content-Length: 0 服務器給瀏覽器響應一個301永久重定向響應，這樣瀏覽器就會訪問“http://www.facebook.com/” 而非“http://facebook.com/”。

為什么服務器一定要重定向而不是直接發會用戶想看的網頁內容呢？這個問題有好多有意思的答案。
其中一個原因跟搜索引擎排名有 關。你看，如果一個頁面有兩個地址，就像
http://www.igoro.com/ 和http://igoro.com/
，搜索引擎會認為它們是兩個網站，結果造成每一個的搜索鏈接都減少從而降低排名。而搜索引擎知道301永久重定向是 什么意思，這樣就會把訪問帶www的和不帶www的地址歸到同一個網站排名下。
還有一個是用不同的地址會造成緩存友好性變差。當一個頁面有好幾個名字時，它可能會在緩存里出現好幾次。

瀏覽器跟蹤重定向地址

現在，瀏覽器知道了
“http://www.facebook.com/”
才是要訪問的正確地址，所以它會發送另一個獲取請求：

GET http://www.facebook.com/ HTTP/1.1Accept: application/x-ms-application, image/jpeg, application/xaml+xml, [...]Accept-Language: en-USUser-Agent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; WOW64; [...]Accept-Encoding: gzip, deflateConnection: Keep-AliveCookie: lsd=XW[...]; c_user=21[...]; x-referer=[...]Host: www.facebook.com

頭信息以之前請求中的意義相同。

服務器“處理”請求

服務器接收到獲取請求，然后處理并返回一個響應。
這表面上看起來是一個順向的任務，但其實這中間發生了很多有意思的東西- 就像作者博客這樣簡單的網站，何況像facebook那樣訪問量大的網站呢！
Web 服務器軟件
web服務器軟件（像IIS和阿帕奇）接收到HTTP請求，然后確定執行什么請求處理來處理它。請求處理就是一個能夠讀懂請求并且能生成HTML來進行響應的程序（像ASP.NET,PHP,RUBY…）。舉 個最簡單的例子，需求處理可以以映射網站地址結構的文件層次存儲。像
http://example.com/folder1/page1.aspx
這個地 址會映射/httpdocs/folder1/page1.aspx這個文件。web服務器軟件可以設置成為地址人工的對應請求處理，這樣 page1.aspx的發布地址就可以是
http://example.com/folder1/page1。

請求處理
請求處理閱讀請求及它的參數和cookies。它會讀取也可能更新一些數據，并講數據存儲在服務器上。然后，需求處理會生成一個HTML響應。
所 有動態網站都面臨一個有意思的難點 -如何存儲數據。小網站一半都會有一個SQL數據庫來存儲數據，存儲大量數據和/或訪問量大的網站不得不找一些辦法把數據庫分配到多臺機器上。解決方案 有：sharding （基于主鍵值講數據表分散到多個數據庫中），復制，利用弱語義一致性的簡化數據庫。

委 托工作給批處理是一個廉價保持數據更新的技術。舉例來講，Fackbook得及時更新新聞feed，但數據支持下的“你可能認識的人”功能只需要每晚更新 （作者猜測是這樣的，改功能如何完善不得而知）。批處理作業更新會導致一些不太重要的數據陳舊，但能使數據更新耕作更快更簡潔。

服務器發回一個HTML響應

圖中為服務器生成并返回的響應：

HTTP/1.1 200 OKCache-Control: private, no-store, no-cache, must-revalidate, post-check=0,pre-check=0Expires: Sat, 01 Jan 2000 00:00:00 GMTP3P: CP="DSP LAW"Pragma: no-cacheContent-Encoding: gzipContent-Type: text/html; charset=utf-8X-Cnection: closeTransfer-Encoding: chunkedDate: Fri, 12 Feb 2010 09:05:55 GMT2b3Tn@[...]

整個響應大小為35kB，其中大部分在整理后以blob類型傳輸。
內容編碼頭告訴瀏覽器整個響應體用gzip算法進行壓縮。解壓blob塊后，你可以看到如下期望的HTML：
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

...
關于壓縮，頭信息說明了是否緩存這個頁面，如果緩存的話如何去做，有什么cookies要去設置（前面這個響應里沒有這點）和隱私信息等等。

請注意報頭中把Content-type設置為“text/html”。報頭讓瀏覽器將該響應內容以HTML形式呈現，而不是以文件形式下載它。瀏覽器會根據報頭信息決定如何解釋該響應，不過同時也會考慮像URL擴展內容等其他因素。

瀏覽器開始顯示HTML
在瀏覽器沒有完整接受全部HTML文檔時，它就已經開始顯示這個頁面了：

瀏覽器發送獲取嵌入在HTML中的對象

在瀏覽器顯示HTML時，它會注意到需要獲取其他地址內容的標簽。這時，瀏覽器會發送一個獲取請求來重新獲得這些文件。
下面是幾個我們訪問http://facebook.com時需要重獲取的幾個URL：
圖片
http://static.ak.fbcdn.net/rsrc.php/z12E0/hash/8q2anwu7.gif
http://static.ak.fbcdn.net/rsrc.php/zBS5C/hash/7hwy7at6.gif
…
CSS 式樣表
http://static.ak.fbcdn.net/rsrc.php/z448Z/hash/2plh8s4n.css
http://static.ak.fbcdn.net/rsrc.php/zANE1/hash/cvtutcee.css
…
JavaScript 文件
http://static.ak.fbcdn.net/rsrc.php/zEMOA/hash/c8yzb6ub.js
http://static.ak.fbcdn.net/rsrc.php/z6R9L/hash/cq2lgbs8.js
…
這些地址都要經歷一個和HTML讀取類似的過程。所以瀏覽器會在DNS中查找這些域名，發送請求，重定向等等…
但 不像動態頁面那樣，靜態文件會允許瀏覽器對其進行緩存。有的文件可能會不需要與服務器通訊，而從緩存中直接讀取。服務器的響應中包含了靜態文件保存的期限 信息，所以瀏覽器知道要把它們緩存多長時間。還有，每個響應都可能包含像版本號一樣工作的ETag頭（被請求變量的實體值），如果瀏覽器觀察到文件的版本 ETag信息已經存在，就馬上停止這個文件的傳輸。

試著猜猜看“http://fbcdn.net”在地址中代表什么？聰明的答案是”Facebook內容分發網絡”。Facebook利用內容分發網絡（CDN）分發像圖片，CSS表和JavaScript文件這些靜態文件。所以，這些文件會在全球很多CDN的數據中心中留下備份。
靜態內容往往代表站點的帶寬大小，也能通過CDN輕松的復制。通常網站會使用第三方的CDN。例如，Facebook的靜態文件由最大的CDN提供商Akamai來托管。
舉例來講，當你試著ping http://static.ak.fbcdn.net的時候，可能會從某個http://akamai.net服務器上獲得響應。有意思的是，當你同樣再ping一次的時候，響應的服務器可能就不一樣，這說明幕后的負載平衡開始起作用了。

瀏覽器發送異步（AJAX）請求

在Web 2.0偉大精神的指引下，頁面顯示完成后客戶端仍與服務器端保持著聯系。
以 Facebook聊天功能為例，它會持續與服務器保持聯系來及時更新你那些亮亮灰灰的好友狀態。為了更新這些頭像亮著的好友狀態，在瀏覽器中執行的 JavaScript代碼會給服務器發送異步請求。這個異步請求發送給特定的地址，它是一個按照程式構造的獲取或發送請求。還是在Facebook這個例 子中，客戶端發送給
http://www.facebook.com/ajax/chat/buddy_list.php
一個發布請求來獲取你好友里哪個 在線的狀態信息。
提起這個模式，就必須要講講”AJAX”– “異步JavaScript 和 XML”，雖然服務器為什么用XML格式來進行響應也沒有個一清二白的原因。再舉個例子吧，對于異步請求，Facebook會返回一些JavaScript的代碼片段。

除了其他，fiddler這個工具能夠讓你看到瀏覽器發送的異步請求。事實上，你不僅可以被動的做為這些請求的看客，還能主動出擊修改和重新發送它們。AJAX請求這么容易被蒙，可著實讓那些計分的在線游戲開發者們郁悶的了。（當然，可別那樣騙人家~）

Facebook聊天功能提供了關于AJAX一個有意思的問題案例：把數據從服務器端推送到客戶端。因為HTTP是一個請求-響應協議，所以聊天服務器不能把新消息發給客戶。取而代之的是客戶端不得不隔幾秒就輪詢下服務器端看自己有沒有新消息。
這些情況發生時長輪詢是個減輕服務器負載挺有趣的技術。如果當被輪詢時服務器沒有新消息，它就不理這個客戶端。而當尚未超時的情況下收到了該客戶的新消息，服務器就會找到未完成的請求，把新消息做為響應返回給客戶端。

1、C/S和B/S模式的區別以及各自特點?

• 為了區別于傳統的C/S模式，才特意將其稱為B/S模式。認識到這些結構的特征，對于系統的選型而言是很關鍵的。
• 系統的性能
  • 在系統的性能方面，B/S占有優勢的是其異地瀏覽和信息采集的靈活性。任何時間、任何地點、任何系統，只要可以使用瀏覽器上網，就可以使用B/S系統的終端。
  • 采用B/S結構，客戶端只能完成瀏覽、查詢、數據輸入等簡單功能，絕大部分工作由服務器承擔，這使得服務器的負擔很重。采用C/S結構時，客戶端和服務器端都能夠處理任務，這雖然對客戶機的要求較高，但因此可以減輕服務器的壓力。而且，由于客戶端使用瀏覽器，使得網上發布的信息必須是以HTML格式為主，其它格式文件多半是以附件的形式存放。而HTML格式文件（也就是Web頁面）不便于編輯修改，給文件管理帶來了許多不便。
• 系統的開發
  • C/S結構是建立在中間件產品基礎之上的，要求應用開發者自己去處理事務管理、消息隊列、數據的復制和同步、通信安全等系統級的問題。這對應用開發者提出了較高的要求，而且迫使應用開發者投入很多精力來解決應用程序以外的問題。這使得應用程序的維護、移植和互操作變得復雜。如果客戶端是在不同的操作系統上，C/S結構的軟件需要開發不同版本的客戶端軟件。但是，與B/S結構相比，C/S技術發展歷史更為“悠久”。從技術成熟度及軟件設計、開發人員的掌握水平來看，C/S技術應是更成熟、更可靠的。
• 系統的升級維護
  • C/S系統的各部分模塊中有一部分改變，就要關聯到其它模塊的變動，使系統升級成本比較大。B/S與C/S處理模式相比，則大大簡化了客戶端，只要客戶端機器能上網就可以。對于B/S而言，開發、維護等幾乎所有工作也都集中在服務器端，當企業對網絡應用進行升級時，只需更新服務器端的軟件就可以，這減輕了異地用戶系統維護與升級的成本。如果客戶端的軟件系統升級比較頻繁，那么B/S架構的產品優勢明顯——所有的升級操作只需要針對服務器進行，這對那些點多面廣的應用是很有價值的，例如一些招聘網站就需要采用B/S模式，客戶端分散，且應用簡單，只需要進行簡單的瀏覽和少量信息的錄入。
• C/S模式的優點和缺點
  • ★C/S模式的優點
  • 由于客戶端實現與服務器的直接相連，沒有中間環節，因此響應速度快。
  • 操作界面漂亮、形式多樣，可以充分滿足客戶自身的個性化要求。
  • C/S結構的管理信息系統具有較強的事務處理能力，能實現復雜的業務流程。
  • ★C/S模式的缺點
  • 需要專門的客戶端安裝程序，分布功能弱，針對點多面廣且不具備網絡條件的用戶群體，不能夠實現快速部署安裝和配置。
  • 兼容性差，對于不同的開發工具，具有較大的局限性。若采用不同工具，需要重新改寫程序。
  • 開發成本較高，需要具有一定專業水準的技術人員才能完成。
• B/S模式的優點和缺點
  • ★B/S模式的優點
  • 具有分布性特點，可以隨時隨地進行查詢、瀏覽等業務處理。
  • 業務擴展簡單方便，通過增加網頁即可增加服務器功能。
  • 維護簡單方便，只需要改變網頁，即可實現所有用戶的同步更新。
  • 開發簡單，共享性強。
  • ★B/S模式的缺點
  • 個性化特點明顯降低，無法實現具有個性化的功能要求。
  • 操作是以鼠標為最基本的操作方式，無法滿足快速操作的要求。
  • 頁面動態刷新，響應速度明顯降低。
  • 無法實現分頁顯示，給數據庫訪問造成較大的壓力。
  • 功能弱化，難以實現傳統模式下的特殊功能要求。
• 近年來，隨著軟硬件技術發展和人們意識的提高，Web應用得到廣泛的普及，一方面在互聯網浪潮的推動下，基于互聯網的信息共享和電子商務不斷發展，像新浪、搜狐、8848等大型網站不斷涌現出來，另一方面隨著Java、CGI等網絡技術的成熟，基于B/S結構的大型軟件逐漸顯示出巨大的優勢。同時，也就產生了一個焦點問題，什么樣的服務器能夠滿足不同用戶的需求，怎么能夠保證Web服務器能夠長期穩定地運行，為了滿足這樣的需求Web測試也就同樣變得十分重要。

轉載于:https://www.cnblogs.com/suntingme/p/5392270.html

總結

以上是生活随笔為你收集整理的测试开发面试-技术题持续累积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。