剑指Offer——滴滴笔试题+知识点总结

剑指Offer——滴滴笔试题+知识点总结

情景回顾

• 时间:2016.9.18 15：00-17：00

• 地点:山东省网络环境智能计算技术重点实验室

• 事件:滴滴笔试

  总体来说，滴滴笔试内容体量不算多，主要分为19道选择题、1道多选题，2道编程题、1道简答题(也不简单)。

选择题

  考查知识点：二叉树某层中节点个数(2i-1)、费波纳茨数列应用(上9级台阶的方法-分1步、2步)、Linux下文件软、硬链接。还有各种计算题(10个人握手，每个人都握一遍，总共握了多少次？12个黑球，个白球，数到13时取出为白球的取法；A,B打乒乓球五局三胜，A赢得概率为0.6，B赢的概率为0.4，A赢了前2局，问A最终获胜的概率…这些题目自己都是蒙的……)。

Linux链接

 Linux链接分两种，一种被称为硬链接（Hard Link），另一种被称为符号链接（Symbolic Link）。默认情况下，ln命令产生硬链接。

1. 硬链接：新建的文件是已经存在的文件的一个别名，当原文件删除时，新建的文件仍然可以使用.
2. 软链接：也称为符号链接，新建的文件以“路径”的形式来表示另一个文件，和Windows的快捷方式十分相似，新建的软链接可以指向不存在的文件.

  下面详细介绍一下硬链接和软连接之间的区别.

1. 硬链接和原来的文件没有什么区别，而且共享一个 inode 号（文件在文件系统上的唯一标识）；而软链接不共享 inode，也可以说是个特殊的 inode，所以和原来的 inode 有区别。
2. 若原文件删除了，则该软连接则不可以访问，而硬连接则是可以的。
3. 由于符号链接的特性，导致其可以跨越磁盘分区，但硬链接不具备这个特性.

编程题

小青蛙走迷宫

  这道题与之前所做的网易“地牢逃脱”题同属于迷宫问题，均需要使用递归+回溯法解决。而自己真的不会做…..需要继续学习…..这也给自己提了个醒，这些题并不是说做过了就做过了，不去总结这些知识点，收效甚微，也无法为之后的企业笔试有所准备。之前地牢逃脱的题目，自己就直接放过去了，可惜，可气，可悲，可怜…..

末尾0的个数

  实现计算末尾中0的个数，这道编程题之前以选择题的形式做过，好在自己深入研究了一下。这才很顺利的AC一道题目。但是按照之前的思路解决时，通过率为80%，参考别人的之后才全部通过。自己需要仔细查看一下自己的代码情况。

        // 80%
/*  int b = 5;
        while(a > b){
            cnt += a / b;
            b *= 5;
        }*/
        while (a > 0)
        {
              cnt += a / 5;
              a /= 5;
              System.out.println(a);
        }

  以上为通过80%与AC的代码对比。部分不通过的示例为a=5时，上面的计算结果为0,显然计算错误。故循环条件应改为a >= b所以，在做编程题时应首先设计好测试案例，要设计完善的测试案例。包括边界值的测试案例（此例就是典型的边界值遗漏情况）。

简答题

   这道简答题并不简单，考察的知识点涉及网络底层、服务器端、前端等一栈式知识点。自己只是大概的答了一下。还需要认真总结。

  通过网上搜索之后发现这道题原来是百度的一道面试题。搜索内容百篇一律，结合自己的理解整理后详细讲解如下:

  导航的第一步是通过访问的域名找出其IP地址。DNS查找过程如下：

  浏览器缓存–浏览器会缓存DNS记录一段时间。有趣的是，操作系统没有告诉浏览器储存DNS记录的时间，这样不同浏览器会储存各自固定的一个时间（2分钟到30分钟不等）。

  系统缓存–如果在浏览器缓存里没有找到需要的记录，浏览器会做一个系统调用（windows里是gethostbyname）。这样便可获得系统缓存中的记录。

  路由器缓存–接着，前面的查询请求发向路由器，它一般会有自己的DNS缓存。

ISP DNS 缓存–接下来要check的就是ISP缓存DNS的服务器。在这一般都能找到相应的缓存记录。

  递归搜索

  在web服务器端收到请求后，通过读取配置文件中监听器的设置。

  Tomcat Server处理一个http请求的过程

  假设来自客户的请求为：

  http://localhost:8080/wsota/wsota_index.jsp

  1) 请求被发送到本机端口8080，被在那里侦听的Coyote HTTP/1.1 Connector获得

  2) Connector把该请求交给它所在的Service的Engine来处理，并等待来自Engine的回应

  3) Engine获得请求localhost/wsota/wsota_index.jsp，匹配它所拥有的所有虚拟主机Host

  4) Engine匹配到名为localhost的Host（即使匹配不到也把请求交给该Host处理，因为该Host被定义为该Engine的默认主机）

  5) localhost Host获得请求/wsota/wsota_index.jsp，匹配它所拥有的所有Context

  6) Host匹配到路径为/wsota的Context（如果匹配不到就把该请求交给路径名为”“的Context去处理）

  7) path=”/wsota”的Context获得请求/wsota_index.jsp，在它的mapping table中寻找对应的servlet

  8) Context匹配到URL PATTERN为*.jsp的servlet，对应于JspServlet类

  9) 构造HttpServletRequest对象和HttpServletResponse对象，作为参数调用JspServlet的doGet或doPost方法

  10)Context把执行完了之后的HttpServletResponse对象返回给Host

  11)Host把HttpServletResponse对象返回给Engine

  12)Engine把HttpServletResponse对象返回给Connector

  13)Connector把HttpServletResponse对象返回给客户browser