待解决题：

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;    }    //如果原始数与反转后的数相等则返回true    if(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;                        //记录数位上的回文数，如个位回文数为9        int w = 0;                            //记录数位                long half;                            //保存回文数的左半边的结果        long h = 1;                            //回文数的左半边的起始基数        long res;                            //结果                while(true) {            if(w > 0 && w%2 == 0) {            //每进两个数位，回文数乘以10                number *= 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++) {    //求回文数的左半边的基数，如回文数在万位上，则为100            h *= 10;        }                half = h + index;                        //回文数的左半边，如100 + 50 = 150                res = 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 + nrs= nr设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。a + x = nra + x = (n – 1)r +r = (n-1)r + L - aa = (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，网络服务器，需求处理等等。

本文将更深入的研究当你输入一个网址的时候，后台到底发生了一件件什么样的事～

1. 首先嘛，你得在浏览器里输入要网址:

2. 浏览器查找域名的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服务器与查询主机通信方式的应用层协议组成。

3. 浏览器给web服务器发送一个HTTP请求

   因为像Facebook主页这样的动态页面，打开后在浏览器缓存中很快甚至马上就会过期，毫无疑问他们不能从中读取。

   所以，浏览器将把一下请求发送到Facebook所在的服务器：

   GET http://facebook.com/ HTTP/1.1Accept: 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, deflateConnection: Keep-AliveHost: facebook.comCookie: 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到底是文件夹还是文件，所以不能自动添加 斜杠。这时，浏览器就不加斜杠直接访问地址，服务器会响应一个重定向，结果造成一次不必要的握手。

4. 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的地址归到同一个网站排名下。
   还有一个是用不同的地址会造成缓存友好性变差。当一个页面有好几个名字时，它可能会在缓存里出现好几次。

5. 浏览器跟踪重定向地址

现在，浏览器知道了

“http://www.facebook.com/”

才是要访问的正确地址，所以它会发送另一个获取请求：

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

头信息以之前请求中的意义相同。

1. 服务器“处理”请求

服务器接收到获取请求，然后处理并返回一个响应。

这表面上看起来是一个顺向的任务，但其实这中间发生了很多有意思的东西- 就像作者博客这样简单的网站，何况像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，但数据支持下的“你可能认识的人”功能只需要每晚更新 （作者猜测是这样的，改功能如何完善不得而知）。批处理作业更新会导致一些不太重要的数据陈旧，但能使数据更新耕作更快更简洁。

1. 服务器发回一个HTML响应

图中为服务器生成并返回的响应：

HTTP/1.1 200 OK Cache-Control: private, no-store, no-cache, must-revalidate, post-check=0, pre-check=0 Expires: Sat, 01 Jan 2000 00:00:00 GMT P3P: CP="DSP LAW" Pragma: no-cache Content-Encoding: gzip Content-Type: text/html; charset=utf-8 X-Cnection: close Transfer-Encoding: chunked Date: Fri, 12 Feb 2010 09:05:55 GMT 2b3Tn@[...]

整个响应大小为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扩展内容等其他因素。

1. 浏览器开始显示HTML

   在浏览器没有完整接受全部HTML文档时，它就已经开始显示这个页面了：

2. 浏览器发送获取嵌入在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一次的时候，响应的服务器可能就不一样，这说明幕后的负载平衡开始起作用了。

1. 浏览器发送异步（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测试也就同样变得十分重要。