[关闭]
@adamhand 2019-03-11T00:56:48.000000Z 字数 14101 阅读 709

若干面试题

25匹马的角逐

问题是这样的：一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问最少得比多少场才能知道跑得最快的5匹马。

注意： "假设每匹马都跑的很稳定" 的意思是在上一场比赛中A马比B马快，则下一场比赛中A马依然比B马快。

稍微想一下，可以采用一种 竞标赛排序(Tournament Sort)的思路。

思路一：一般思路，非最优

1. 第一步
首先将25匹马分成5组，并分别进行5场比赛之后得到的名次排列如下：

          A组：  [A1  A2  A3   A4  A5]

          B组：  [B1  B2  B3   B4  B5]

          C组：  [C1  C2  C3   C4  C5]

          D组：  [D1  D2  D3   D4  D5]

          E组：  [E1  E2  E3   E4  E5]

其中，每个小组最快的马为[A1、B1、C1、D1、E1]。

2. 第二步
将[A1、B1、C1、D1、E1]进行第6场，选出第1名的马，不妨设 A1>B1>C1>D1>E1. 此时第1名的马为A1。

3. 第三步
将[A2、B1、C1、D1、E1]进行第7场，此时选择出来的必定是第2名的马，不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

4. 第四步
进行第8场，选择[A2、B2、C1、D1、E1]角逐出第3名的马。

依次类推，第9，10场可以分别决出第4，5名的马。

因此，依照这种竞标赛排序思想，需要10场比赛是一定可以取出前5名的。

思路二：简化思路

仔细想一下，如果需要减少比赛场次，就一定需要在某一次比赛中同时决出2个名次，而且每一场比赛之后，有一些不可能进入前5名的马可以提前出局。

当然要做到这一点，就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题，希望能够得到解决。

1. 第一步
首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

2. 第二步
第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马(A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论：有一些马在前6场比赛之后就决定出局的命运了(下面绿色字体标志出局)。



3. 第三步
第7场比赛是关键，能否同时决出第2，3名的马呢？我们首先做下分析：

在上面的方法中，第7场比赛[A2、B1、C1、D1、E1]是为了决定第2名的马。但是在第6场比赛中我们已经得到(B1>C1>D1>E1)，试问，有B1在的比赛，C1、D1、E1还有可能争夺第2名吗？ 当然不可能，也就是说第2名只能在A2、B1中出现。实际上只需要2条跑道就可以决出第2名，剩下C1、D1、E1的3条跑道都只能用来凑热闹的吗？

能够优化的关键出来了，我们是否能够通过剩下的3个跑道来决出第3名呢？当然可以，我们来进一步分析第3名的情况：

  ● 如果A2>B1(即第2名为A2)，那么根据第6场比赛中的(B1>C1>D1>E1)。 可以断定第3名只能在A3和B1中产生。
  ● 如果B1>A2(即第2名为B1)，那么可以断定的第3名只能在A2, B2,C1 中产生。

好了，结论也出来了，只要我们把[A2、B1、A3、B2、C1]作为第7场比赛的马，那么这场比赛的第2，3名一定是整个25匹马中的第2，3名。

我们在这里列举出第7场的2，3名次的所有可能情况：
  ① 第2名=A2，第3名=A3
  ② 第2名=A2，第3名=B1
  ③ 第2名=B1，第3名=A2
  ④ 第2名=B1，第3名=B2
  ⑤ 第2名=B1，第3名=C1

4. 第四步
第8场比赛很复杂，我们要根据第7场的所有可能的比赛情况进行分析。

① 第2名=A2，第3名=A3。那么此种情况下第4名只能在A4和B1中产生。

  ● 如果第4名=A4，那么第5名只能在A5、B1中产生。
  ● 如果第4名=B1，那么第5名只能在A4、B2、C1中产生。

不管结果如何，此种情况下，第4、5名都可以在第8场比赛中决出。其中比赛马匹为[A4、A5、B1、B2、C1]。

② 第2名=A2，第3名=B1。那么此种情况下第4名只能在A3、B2、C1中产生。

  ● 如果第4名=A3，那么第5名只能在A4、B2、C1中产生。
  ● 如果第4名=B2，那么第5名只能在A3、B3、C1中产生。
  ● 如果第4名=C1，那么第5名只能在A3、B2、C2、D1中产生。

那么，第4、5名需要在马匹[A3、B2、B3、C1、A4、C2、D1]七匹马中产生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

③ 第2名=B1，第3名=A2。那么此种情况下第4名只能在A3、B2、C1中产生。

情况和②一样，必须角逐第9场

④ 第2名=B1，第3名=B2。 那么此种情况下第4名只能在A2、B3、C1中产生。

  ● 如果第4名=A2，那么第5名只能在A3、B3、C1中产生。
  ● 如果第4名=B3，那么第5名只能在A2、B4、C1中产生。
  ● 如果第4名=C1，那么第5名只能在A2、B3、C2、D1中产生。

那么，第4、5名需要在马匹[A2、B3、B4、C1、A3、C2、D1]七匹马中产 生，则必须比赛两场才行，也就是到第9场角逐出全部的前5名。

⑤ 第2名=B1，第3名=C1。那么此种情况下第4名只能在A2、B2、C2、D1中产生。

  ● 如果第4名=A2，那么第5名只能在A3、B2、C2、D1中产生。
  ● 如果第4名=B2，那么第5名只能在A2、B3、C2、D1中产生。
  ● 如果第4名=C2，那么第5名只能在A2、B2、C3、D1中产生。
  ● 如果第4名=D1，那么第5名只能在A2、B2、C2、D2、E2中产生。

那么，第4、5名需要在马匹[A2、B2、C2、D1、A3、B3、C3、D2、E1]九匹马中 产 生，因此也必须比赛两场，也就是到第9长决出胜负

总结：最好情况可以在第8场角逐出前5名，最差也可以在第9场搞定。

参考

25匹马的角逐

微信扫二维码过程，后台的实现

参考 微信扫码登录实现原理

电脑的开机过程

电脑的开机过程可以分为四个阶段：BIOS启动、主引导记录、硬盘启动和操作系统启动。

第一阶段：BIOS启动

BIOS是一种固件，被写在ROM中，计算机通电后，第一件事就是读取它。

硬件自检

BIOS程序首先检查，计算机硬件能否满足运行的基本条件，这叫做"硬件自检"（Power-On Self-Test），缩写为POST。

如果硬件出现问题，主板会发出不同含义的蜂鸣，启动中止。如果没有问题，屏幕就会显示出CPU、内存、硬盘等信息。

启动顺序

硬件自检完成后，BIOS把控制权转交给下一阶段的启动程序。

第二阶段：主引导记录

BIOS按照"启动顺序"，把控制权转交给排在第一位的储存设备。

这时，计算机读取该设备的第一个扇区，也就是读取最前面的512个字节。如果这512个字节的最后两个字节是0x55和0xAA，表明这个设备可以用于启动；如果不是，表明设备不能用于启动，控制权于是被转交给"启动顺序"中的下一个设备。

这最前面的512个字节，就叫做"主引导记录"（Master boot record，缩写为MBR）。

第三阶段：硬盘启动

到了这个时期，计算机的控制权就要转交给硬盘的某个分区了，这里又分成三种情况。

第四阶段：操作系统

控制权转交给操作系统后，操作系统的内核首先被载入内存。

以Linux系统为例，先载入/boot目录下面的kernel。内核加载成功后，第一个运行的程序是/sbin/init。它根据配置文件（Debian系统是/etc/initab）产生init进程。这是Linux启动后的第一个进程，pid进程编号为1，其他进程都是它的后代。

然后，init线程加载系统的各个模块，比如窗口程序和网络程序，直至执行/bin/login程序，跳出登录界面，等待用户输入用户名和密码。

至此，全部启动过程完成。

参考：
计算机是如何启动的？

0 1概率问题

给一个函数，返回 0 和 1，概率为 p 和 1-p，请你实现一个函数，使得返回 01 概率一样。

假如说给定的函数为random()，i=random()，j=random()。则i=0的概率为p,i=1的概率为1-p,j也是如此。如果想构造一个相等概率，可以考虑将p和1-p相乘。如下：

  1. 11  p*p        10  p*(1-p)
  3. 01 (1-p)*p   00 (1-p)*(1-p)
  1. public int random_1(){
  2.     int i = random();
  3.     int j = random();
  4.     int result;
  6.     while(true){
  7.         if(i == 0 && j == 1){
  8.             result = 0;
  9.             break;
  10.         }else if(i == 1 && j == 0){
  11.             result = 1;
  12.             break;
  13.         }else{
  14.             continue;
  15.         }
  16.     }
  17.     return result;
  18. }

url去重

题目一：给定a、b两个文件，各存放50亿个url，每个url各占用64字节，内存限制是4G，如何找出a、b文件共同的url？

可以估计每个文件的大小为5G*64=300G，远大于4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

具体做法是：

a文件有10 亿个 url，每个 url 大小小于 56B，要求去重，内存只给你4G

同样估算一下，需要的存储空间:10G*56B=56G，4G也是放不下的，所以开始考虑分治。

“软链接”和“硬链接”的区别

首先得看一下inode的概念，inode 是 UNIX 操作系统中的一种数据结构，其本质是结构体，可以将其类比做C语言中的指针，它指向了物理硬盘的一个区块，每当创建一个文件的时候，就会为文件创建一个inode，标志着该文件的物理位置。inode相同的节点被Unix视为同一个文件。

参考：linux硬链接和软链接的区别 5分钟让你明白“软链接”和“硬链接”的区别 硬链接和软链接的区别

写一段程序连接数据库并查询一条语句

  1. public class javaTest {
  3.     public static void main(String[] args) throws ClassNotFoundException, SQLException  {
  4.         String URL="jdbc:mysql://127.0.0.1:3306/imooc?useUnicode=true&characterEncoding=utf-8";
  5.         String USER="root";
  6.         String PASSWORD="tiger";
  7.         //1.加载驱动程序
  8.         Class.forName("com.mysql.jdbc.Driver");
  9.         //2.获得数据库链接
  10.         Connection conn=DriverManager.getConnection(URL, USER, PASSWORD);
  11.         //3.通过数据库的连接操作数据库，实现增删改查（使用Statement类）
  12.         Statement st=conn.createStatement();
  13.         ResultSet rs=st.executeQuery("select * from user");
  14.         //4.处理数据库的返回结果(使用ResultSet类)
  15.         while(rs.next()){
  16.             System.out.println(rs.getString("user_name")+" "
  17.                           +rs.getString("user_password"));
  18.         }
  20.         //关闭资源
  21.         rs.close();
  22.         st.close();
  23.         conn.close();
  24.     }
  25. }

死锁和银行家算法

死锁

要想说银行家，首先得说死锁问题，因为银行家算法就是为了死锁避免提出的。那么，什么是死锁？简单的举个例子：俩人吃饺子，一个人手里拿着酱油，一个人手里拿着醋，拿酱油的对拿着醋的人说：“你把醋给我，我就把酱油给你”；拿醋的对拿着酱油的人说：“不，你把酱油给我，我把醋给你。”

于是，俩人就这样杠上了，永远吃不上饺子了。这就是死锁。

说的学术化一点，发生死锁必须满足四个条件：

注：所有4个条件必须同时满足才会出现死锁。循环等待意味着占有并等待，这样四个条件并不完全独立。

那么，为啥这个算法叫银行家算法？因为这个算法同样可以用于银行的贷款业务。让我们考虑下面的情况。

一个银行家共有20亿财产
第一个开发商：已贷款15亿，资金紧张还需3亿。
第二个开发商：已贷款5亿，运转良好能收回。
第三个开发商：欲贷款18亿

一个常规的想法就是先等着第二个开发商把钱收回来，然后手里有了5个亿，再把3个亿贷款给第一个开发商，等第一个开发商收回来18个亿，然后再把钱贷款给第三个开发商。

第一个例子中：醋和酱油是资源，这俩吃饺子的是进程；第二个例子中：银行家是资源，开发商是进程。在操作系统中，有内存，硬盘等等资源被众多进程渴求着，那么这些资源怎么分配给他们才能避免“银行家破产”的风险？

银行家算法

当一个进程申请使用资源的时候，银行家算法通过先 试探 分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

安全序列

安全序列是指对当前申请资源的进程排出一个序列，保证按照这个序列分配资源完成进程，不会发生“酱油和醋”的尴尬问题。

假设有进程P1,P2,.....Pn，则安全序列要求满足：Pi(1<=i<=n)需要资源 <= 剩余资源 + 分配给Pj(1 <= j < i)资源

为什么等号右边还有已经被分配出去的资源？想想银行家那个问题，分配出去的资源就好比第二个开发商，人家能还回来钱，咱得把这个考虑在内。

定义下面的数据结构

  1. int n,m;                   //系统中进程总数n和资源种类总数m
  2. int Available[1..m];       //资源当前可用总量
  3. int Allocation[1..n,1..m]; //当前给分配给每个进程的各种资源数量
  4. int Need[1..n,1..m];       //当前每个进程还需分配的各种资源数量
  5. int Work[1..m];            //当前可分配的资源
  6. bool Finish[1..n];         //进程是否结束

安全判定算法

  1. Work = Available（动态记录当前剩余资源）
  2. Finish[i] = false（设定所有进程均未完成）
  1. Finish[i] = false          
  2. Need[i] <= Work 
  3. 如果没有这样的进程Pi，则跳转到第4步
  1. Finish[i] = true           
  2. Work = Work +Allocation[i]
  3. GOTO 第2步，继续查找

伪代码:

  1. Boolean Found;
  2. Work = Available; Finish[1..n] = false; 
  3. while(true){
  4.     //不断的找可执行进程
  5.    Found = false;
  6.    for(i=1; i<=n; i++){
  7.      if(Finish[i]==false && Need[i]<=Work){
  8.         Work = Work + Allocation[i];//把放出去的贷款也当做自己的资产
  9.         Finish[i] = true; 
  10.         Found = true;
  11.       }
  12.     }
  13.    if(Found==false)break;
  14.  }
  15. for(i=1;i<=n;i++) 
  16.   if(Finish[i]==false)return “deadlock”; //如果有进程是完不成的，那么就是有死锁

例子

举个实际例子，假设下面的初始状态：

process Allocation Need Available
A B C A B C A B C
P0 0 1 0 7 4 3 3 3 2
P1 2 0 0 1 2 2
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1

上表中process表示需要申请资源的进程，allocation表示已经分配的资源，need表示进程还需要的资源，available表示可用的资源。一共有三个资源A、B、C，五个进程P0、P1、P2、P3、P4。

至此，算法运行完毕。找到安全序列<P1,P3,P4,P0,P2>，证明此时没有死锁危险。(安全序列未必唯一)

资源请求算法

之前说完了怎么判定当前情况是否安全，下面就是说当有进程新申请资源的时候如何处理。我们将第i个进程请求的资源数记为Requests[i]

算法流程：

  1. Available = Available -Requests[i]
  2. Allocation = Allocation[i]+Requests[i]
  3. Need[i]=Need[i]-Requests[i]
  4. 调用安全判定算法，检查是否安全
  5. if(安全)
  6. {
  7.     申请成功，资源分配
  8. }
  9. else
  10. {
  11.     申请失败，资源撤回。第三步前几个操作进行逆操作
  12. }

参考 一句话+一张图说清楚——银行家算法 银行家算法学习笔记 银行家算法---------概念&举例 [OS] 死锁相关知识点以及银行家算法详解

TCP SYN洪泛攻击的原理及防御方法

SYN Flood (SYN洪水) 是种典型的DoS (Denial of Service，拒绝服务，攻击者使用某种方式让目标机器停止提供服务；还有一种DDoS(Distributed Denial of Service)) 攻击。SYN洪泛攻击的基础是依靠TCP建立连接时三次握手的设计。

描述如下：

假设B通过某TCP端口提供服务，B在收到A的SYN消息时，积极的反馈了SYN-ACK消息，使连接进入半开状态，因为B不确定自己发给A的SYN-ACK消息或A反馈的ACK消息是否会丢在半路，所以会给每个待完成的半开连接都设一个Timer，如果超过时间还没有收到A的ACK消息，则重新发送一次SYN-ACK消息给A，直到重试超过一定次数时才会放弃。

B为帮助A能顺利连接，需要分配内核资源维护半开连接，那么当B面临海量的大忽悠A时，SYN Flood攻击就形成了。攻击方A可以控制肉鸡向B发送大量SYN消息但不响应ACK消息，或者干脆伪造SYN消息中的Source IP，使B反馈的SYN-ACK消息石沉大海，导致B被大量注定不能完成的半开连接占据，直到资源耗尽，停止响应正常的连接请求。

可行的解决方案：

参考 服务器遭到SYN攻击怎么办？如何防御SYN攻击？ 什么是SYN Flood攻击? TCP SYN洪泛攻击的原理及防御方法

mybatis缓存

mybatis和mysql8.0之前的缓存机制有点像。

mybatis的缓存分为两级：一级缓存、二级缓存

一级缓存：

mybatis的一级缓存是SqlSession级别的缓存，在操作数据库的时候需要先创建SqlSession会话对象，在对象中有一个HashMap用于存储缓存数据，此HashMap是当前会话对象私有的，别的SqlSession会话对象无法访问。

  1. public class PerpetualCache implements Cache{
  2.     private String id;
  3.     private Map<Object, Object> cache = new HashMap<Object, Object>();
  4.     ...
  5. }

具体流程：

注意事项：

二级缓存：

二级缓存是mapper级别的缓存，也就是同一个namespace的mappe.xml，当多个SqlSession使用同一个Mapper操作数据库的时候，得到的数据会缓存在同一个二级缓存区域

二级缓存默认是没有开启的。需要在setting全局参数中配置开启二级缓存

  1. conf.xml：
  2. <settings>
  3.         <setting name="cacheEnabled" value="true"/>默认是false：关闭二级缓存
  4. <settings>

在userMapper.xml中配置：

  1. <cache eviction="LRU" flushInterval="60000" size="512" readOnly="true"/>当前mapper下所有语句开启二级缓存

这里配置了一个LRU缓存，并每隔60秒刷新，最大存储512个对象，而却返回的对象是只读的

若想禁用当前select语句的二级缓存，添加useCache="false"修改如下：

  1. <select id="getCountByName" parameterType="java.util.Map" resultType="INTEGER" statementType="CALLABLE" useCache="false">

具体流程：

注意事项：

参考 mybatis缓存机制详解

Redis 与 Memcached的区别

正向代理和反向代理的区别

为什么使用代理服务器？

正向代理

正向代理（forward proxy），一个位于客户端和原始服务器之间的服务器，为了从原始服务器取得内容，客户端向代理发送一个请求并制定目标（原始服务器），然后代理向原始服务器转发请求并将获得的内容返回给客户端，客户端才能使用正向代理。我们平时说的代理就是指正向代理。

简单一点：A向C借钱，由于一些情况不能直接向C借钱，于是A想了一个办法，他让B去向C借钱，这样B就代替A向C借钱，A就得到了C的钱，C并不知道A的存在，B就充当了A的代理人的角色。

反向代理

反向代理（Reverse Proxy），以代理服务器来接受internet上的连接请求，然后将请求转发给内部网络上的服务器，并将从服务器上得到的结果返回给internet上请求的客户端，此时代理服务器对外表现为一个反向代理服务器。

理解起来有些抽象，可以这么说：A向B借钱，B没有拿自己的钱，而是悄悄地向C借钱，拿到钱之后再交给A,A以为是B的钱，他并不知道C的存在。



正向代理–HTTP代理为多个人提供翻墙服务；反向代理–百度外卖为多个商户提供平台给某个用户提供外卖服务。

正向代理和反向代理的区别

正向代理的应用

反向代理的应用

参考：谈一谈正向代理和反向代理

sql注入

什么是sql注入

所谓SQL注入式攻击，就是攻击者把SQL命令插入到Web表单的输入域或页面请求的查询字符串，欺骗服务器执行恶意的SQL命令。

举个例子，假如有一个网站登录时需要用户名和密码，不难想象后台查询的sql语法为:

  1. select * from table where name='xx' and password='xxx';

这时，如果在用户名栏中填入' or 1=1; --，密码栏随便填，后台语法将变为：

  1. select * from table where name='' or 1=1; --and password='xxx';

--在是sql语句的注释符号，同样#也是，所以上述语句其实就等同于：

  1. select * from table where name='' or 1=1;

即使name字段为空，但是1=1总是成立的，所以总能返回数据，此时如果程序员在程序中根据结果是否为空来作为用户是否存在的判断，那么势必会出错。

防sql注入原理

使用转义字符

Mysql特殊字符指在mysql中具有特殊含义的字符，除了%和_是mysql特有的外，其他的和我们在C语句中接触的特殊字符一样。

特殊字符 转义字符 特殊意义
\0 \0 字符串结束符NUL
' \' 单引号
" \" 双引号
\b \b 退格
\n \n 换行
\r \r 回车
\Z \Z Control+Z
\ \ 反斜杠
% \% 百分号，模糊查询中匹配任意个任意字符
_ _ 下划线，模糊查询中匹配单个任意字符

对于%和_这2个只在模糊查询条件中有特殊含义，而在普通字符串中没有其他含义的字符，需要根据字符使用在SQL语句中的具体位置来决定是否需要处理。如我们要查询memberName包含t_st的用户信息：

  1. select * from member where memberName like '%t_st%;

如果不对_进行转义处理则会查询出：

  1. test
  2. tast
  3. tbst
  4. t_st

Prepared SQL Statement（预处理语句）

语:法

  1. # 定义预处理语句
  2. PREPARE stmt_name FROM preparable_stmt;
  3. # 执行预处理语句
  4. EXECUTE stmt_name [USING @var_name [, @var_name] ...];
  5. # 删除(释放)定义
  6. {DEALLOCATE | DROP} PREPARE stmt_name;

PREPARE用来发送一条sql给mysql服务器，mysql服务器会解析这条sql。
EXECUTE用来将参数传递给PREPARE语句，mysql服务器不会解析这条sql，只会把execute的参数当做纯参数赋值给语句一。哪怕参数中有sql命令也不会被执行，从而实现防治sql注入。

  1. SET @sql = "SELECT * FROM member WHERE memberName like ?";
  2. SET @param = '%t_st%';
  4. PREPARE stmt FROM @sql;
  5. EXECUTE stmt using @param;
  6. DEALLOCATE PREPARE stmt;

使用这种方法需要注意以下2点：

  1. SET @sql = "SELECT * FROM member WHERE memberName like '%?%'";
  2. SET @param = 't_st';
  4. PREPARE stmt FROM @sql;
  5. EXECUTE stmt using @param;
  6. DEALLOCATE PREPARE stmt;

参考：
sql注入，一个例子让你知道什么是sql注入
什么是SQL注入
MySQL数据库防SQL注入原理
SQL注入原理及防范
MySQL的SQL预处理(Prepared)
MySQL pdo预处理能防止sql注入的原因

面试中关于HashMap的时间复杂度O(1)的思考

面试中关于HashMap的时间复杂度O(1)的思考

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注