腾讯后台面经

算法题

压缩算法

小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩，对于字符串中连续的m个相同字符串S将会压缩为m|S，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述:

1
2
3
4
5
输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输入

1
HG[3|B[2|CA]]F

输出

1
HGBCACABCACABCACAF
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
public class Main{
    public static String decode(String a){
        char[] c = a.toCharArray();
        Stack<String> rec =new Stack();
        Stack<Integer> mul=new Stack();
        int multi=0;        
        StringBuilder tmp= new StringBuilder();
        for(int i=0;i<c.length;i++){
            if(c[i]=='['){
                rec.push(tmp.toString());
                tmp=new StringBuilder();
            }else if(c[i]==']'){
                StringBuilder temp = new StringBuilder();
                int loop=mul.pop();
                for(int j=0;j<loop;j++){
                    temp.append(tmp);
                }
                tmp=new StringBuilder(rec.pop()+temp);
            }else if(c[i]=='|'){
                mul.push(multi);
                multi=0;
            }else if(c[i]>='0'&&c[i]<='9'){
                multi=multi*10+c[i]-'0';
            }else{
                tmp.append(c[i]+"");
            }
        }
        return tmp.toString();
    }
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        String a = sc.next();
        sc.close();        
        System.out.println(decode(a));
    }
}

每K个节点翻转链表 -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null) return head;
        int len = calLen(head,0);
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        int cyc=len/k;
        ListNode pre=dummy,l1=head,l2=head;
        for(int i=0;i<cyc;i++){            
            for(int j=1;j<k;j++){
                l2=l2.next;
            }
            ListNode next=l2.next;
            l2.next=null;
            ListNode tmp=l1;
            reverse(l1);
            pre.next=l2;
            tmp.next=next;
            pre=tmp;
            l1=next;
            l2=next;
        }
        return dummy.next;
    }
    public int calLen(ListNode head,int res){
        if(head==null) return res;
        return calLen(head.next,res+1);
    }
    public void reverse(ListNode root){
        ListNode head=new ListNode(0);
        while(root!=null){
            ListNode tmp = root.next;
            root.next=head.next;
            head.next=root;
            root=tmp;
        }       
    }

最长不重复子串 -

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map = new HashMap();
        int i=0,j=0,res=0;
        char[] c=s.toCharArray();
        while(i<s.length()){
          if(map.containsKey(c[i])){
              j=Math.max(j,map.get(c[i])+1);              
          }
            map.put(c[i],i);
            res=Math.max(res,i-j+1);
            i++;
        }
        return res;
    }

数据库

mysql主从复制的方式

  • 基于 SQL 语句的复制(statement-based replication, SBR)；
  • 基于行的复制(row-based replication, RBR)；
  • 混合模式复制(mixed-based replication, MBR)；

数据库常见死锁原因及处理

一. 事务之间对资源访问顺序的交替

  1. 出现原因：
    一个用户A 访问表A（锁住了表A），然后又访问表B；另一个用户B 访问表B（锁住了表B），然后企图访问表A；这时用户A由于用户B已经锁住表B，它必须等待用户B释放表B才能继续，同样用户B要等用户A释放表A才能继续，这就死锁就产生了。
  2. 解决方法：
    这种死锁比较常见，是由于程序的BUG产生的，除了调整的程序的逻辑没有其它的办法。仔细分析程序的逻辑，对于数据库的多表操作时，尽量按照相同的顺序进行处理，尽量避免同时锁定两个资源，如操作A和B两张表时，总是按先A后B的顺序处理， 必须同时锁定两个资源时，要保证在任何时刻都应该按照相同的顺序来锁定资源。

1）以固定的顺序访问表和行。即按顺序申请锁，这样就不会造成互相等待的场面。

2）大事务拆小。大事务更倾向于死锁，如果业务允许，将大事务拆小。

3）在同一个事务中，尽可能做到一次锁定所需要的所有资源，减少死锁概率。

4）降低隔离级别。如果业务允许，将隔离级别调低也是较好的选择，比如将隔离级别从RR调整为RC，可以避免掉很多因为gap锁造成的死锁。

5）为表添加合理的索引。如果不走索引将会为表的每一行记录添加上锁，死锁的概率大大增大。

操作系统

操作系统的fork操作，带来的进程问题，通信问题

  • fork（）函数通过系统调用创建一个与原来进程几乎完全相同的进程，也就是两个进程可以做完全相同的事，但如果初始参数或者传入的变量不同，两个进程也可以做不同的事。

什么时候用多线程，什么时候用多进程 √

多进程——计算密集型：大量消耗CPU的数学与逻辑运算，也就是我们这里说的平行计算。

多线程——IO密集型：读取文件，读取网络套接字频繁。

线程切换和进程切换的比较

线程切换 与 进程切换的比较。进程切换分为两步：

1）切换虚拟地址

2）切换内核栈和硬件上下文。

线程只有一步：切换内核栈和硬件上下文。

切换页目录的开销很大。

为什么虚拟地址切换很慢？

每个进程都有自己的虚拟地址空间，每个进程都有自己的页表。 切换进程后，页表也要进行切换，TLB就失效了（页表缓冲），cache失效导致命中率降低，虚拟地址转换为物理地址就会很慢。

孤儿进程和僵尸进程 √

一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。

即子进程先于父进程退出后，子进程的PCB需要其父进程释放（调用wait或者waitpid），但是父进程并没有释放子进程的PCB，这样的子进程就称为僵尸进程，僵尸进程实际上是一个已经死掉的进程。

进程调度方法详细介绍 √

1）程序任务有三种:CPU计算密集型、IO密集型与平衡型。2）调度算法：（1） 先来先去服务算法：其优点就是简单且实现容易，缺点则是短的工作有可能变得很慢，因为其前面有很长的工作在执行，这样就会造成用户的交互式体验也比较差。
（2）时间片轮转算法：　时间片轮转是对FCFS算法的一种改进，其主要目的是改善短程序的响应时间，实现方式就是周期性地进行进程切换。时间片轮转的重点在于时间片的选择，需要考虑多方因素：如果运行的进程多时，时间片就需要短一些；进程数量少时，时间片就可以适当长一些。
（3）短任务优先：短任务的优先级比长任务的高，而我们总是安排优先级高的任务先运行。①抢占式：抢占式则是每增加一个新的进程就需要对所有进程（包括正在CPU上运行的进程）进行检查，谁的时间短就运行谁。②非抢占式：非抢占式当已经在CPU上运行的任务结束或阻塞时，从候选任务中选择执行时间最短的进程来执行优点：系统平均响应时间在以上几种算法中是最优的缺点：一是可能造成长任务无法得到CPU时间从而导致“肌饿”。二是如何知道每个进程还需要运转多久？
（4）优先级调度算法：优先级调度算法给每个进程赋予一个优先级，每次需要进程切换时，找一个优先级最高的进程进行调度。优点在于可以赋予重要的进程以高优先级以确保重要任务能够得到CPU时间，其缺点则有二：一是低优先级的进程可能会“饥饿”，二是响应时间无法保证。
（5）混合调度算法：将所有进程分为不同的大类，每个大类为一个优先级。如果两个进程处于不同的大类，则处于高优先级大类的进程优先执行；如果处于同一个大类，则采用时间片轮转算法来执行。

页面置换方法详细介绍 √

页帧：分页式内存管理将物理内存分为等大的小块。

页：逻辑内存（使用虚拟内存技术扩大的内存，可认为其位于硬盘上），也被分为了等大的小块，称为页。（且页和页帧的大小一定是一样的，它是写入真实内存和写回硬盘最小单位。）页面置换算法：页帧被写满，但需要用新的页。需要进行置换。

2.1 Optimal算法（最优算法）　　首先介绍最优算法，它需要知道以后要被用到的页，然后将不会被用到的页换出内存；如果所有页都会被用到，就把需要使用时间离现在最长的页换出，以尽量使不好的情况晚发生。（不可能实现）

2.2 FIFO（First-In First-Out，先进先出）算法　　FIFO算法的思想很简单，就是置换出当前已经待在内存里时间最长的那个页。FIFO算法的运行速度很快，不需要考虑其他的因素，需要的开销很少。

2.3 Second Chance（第二次机会）算法　　为了避免FIFO算法将重要的页换出内存，Second Chance算法提供了一些改进。Second Chance算法在将页面换出内存前检查其使用位（使用位前文有介绍），如果其使用位为1，证明此页最近有被使用，猜测它还可能被使用，于是不把它置换出内存，但是把其使用位置为0，随后检查下一个页面，直到发现某页的使用位为0，将此页置换出内存。

2.4 Clock算法（时钟轮转法）　　为了节约Second Chance算法一个接着一个检查使用位的开销，时钟轮转法又提出了改进。时钟轮转法将所有的页组成一个圆，圆心的指针指向下一个要被置换的页面，置换前同样检查使用位，如果使用位为1，同样将其使用位置为0，随后将顺指针旋转，检查下一个页面，直到发现某页的使用位为0，将此页置换出内存。很容易理解此算法为什么叫“时钟”轮转法。imgimg此时2号页是下一个要被置换出内存的页，置换时如果发现其使用位为1，则将使用位置0后顺时针旋转指针检查1号页。

2.5 LRU（Least Recent Used, 最近最少使用）算法　　为获得对最优算法的模拟，提出了LRU算法。由于当前时间之后需要用到哪些页无法提前获知，于是记录当前时间之前页面的使用情况，认为之前使用过的页面以后还会被用到。在置换时，将最近使用最少的页面换出内存。此种方法的开销比较大。

死锁

1）必要条件：

①互斥：某种资源一段时间内只允许一个进程访问。

②占有并等待：一个进程占有了一种资源，并在等待其他进程释放需要的另外资源。

③不可抢占：一个进程占有的资源，其他进程需要也不饿能抢占，只能等待。

④循环等待：存在一个进程链，每个进程占有上一个进程需要的某种资源。

2）检测死锁的方法有两个容器，一个用于保存线程正在请求的锁，一个用于保存线程已经持有的锁。每次加锁之前都会做如下检测:

1)检测当前正在请求的锁是否已经被其它线程持有,如果有，则把那些线程找出来

2)遍历第一步中返回的线程，检查自己持有的锁是否正被其中任何一个线程请求， 如果第二步返回真,表示出现了死锁

3）如何避免死锁

（1）死锁预防

a、破坏“占有且等待”条件

​ 方法1：所有的进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源。

​ 方法2： 允许进程只获得运行初期需要的资源，便开始运行，在运行过程中逐步释放掉分配到的已经使用完毕的资源，然后再去请求新的资源。

b、破坏“不可抢占”条件

当一个已经持有了一些资源的进程在提出新的资源请求没有得到满足时，它必须释放已经保持的所有资源，待以后需要使用的时候再重新申请。

c、破坏“循环等待”条件

可以通过定义资源类型的线性顺序来预防，可将每个资源编号，当一个进程占有编号为i的资源时，那么它下一次申请资源只能申请编号大于i的资源。

计算机网络

TCP/IP中的攻击

  • flood攻击

  • 连接耗尽类攻击，与被攻击方，完成三次握手后不再发送报文，一直维持连接， 或者立即发送FIN报文，断开后又立即连接。 消耗TCP连接资源。

  • 流量控制相关的攻击：通告窗口较小，传输减慢，长时间占用资源。

Http1.0和Http1.1的主要区别 √

  • Http1.1默认使用长连接keep-alive，而http1.0默认短连接，也就是每次请求都要重新建立一次连接。每一次建立或者断开连接，都需要三次握手四次挥手的开销，如果每次请求都要这样的话，开销会比较大。

  • 增加了错误代码：如410（gone）：表示服务器上某个资源被永久删除。

  • 节约带宽：http 1.1支持只发送header信息(不带任何body信息)，如果服务器认为客户端有权限请求服务器，则返回100，否则返回401。客户端如果接收到100，才开始把请求body发送到服务器。

  • host域：设置虚拟站点

http1.1与http 2.0的主要区别 -

  • http2.0使用了多路复用的技术，做到同一个连接并发处理多个请求，而且并发请求的数量比http1.1大了好几个数量级。

RTT和RTO √

RTO：从上一次发送数据，因为长期没有收到ACK响应，到下一次重发之间的时间。就是重传间隔。

RTT：数据从发送到接收到对方响应之间的时间间隔，即数据报在网络中一个往返用时。大小不稳定。

通常每次重传RTO是前一次重传间隔的两倍，计量单位通常是RTT。例：1RTT，2RTT，4RTT，8RTT……
重传次数到达上限之后停止重传。(一般初始是2倍MSL）

拥塞控制

慢开始门限ssthreth状态变量，当cwnd < ssthreth时，使用慢开始算法；当cwnd > ssthrerth时，使用拥塞控制算法；如果两者相等，两个都可以使用。

慢启动阶段是指数级上升cwnd（拥塞窗口） x倍的最大报文段MSS

1）何时结束慢启动？

(1)发生一个由超时指示的丢包事件，将ssthresh状态变量设为cwnd值的一半，cwnd将设为1个MSS，并重新开始慢启动。

(2)当cwnd的值到达或超过ssthresh时，结束慢启动，TCP转移到拥塞避免模式。

(3)若检测到3个冗余ACK，TCP执行一种快速重传，并进入快速恢复状态。

拥塞避免

线性增长阶段称之为拥塞避免

当达到最大值MAX之后，我们该怎么办呢？

何时结束拥塞避免的线性增长？
（1）出现超时，ssthresh被设置为cwnd的一半，cwnd的值被置为1个MSS，进入慢启动。

​ （2）收到3个冗余ACK，ssthresh被设置为cwnd的一半，cwnd为原来的一半加上3个MSS，，启动快速重传，并进入快速恢复状态。

快速恢复

我们就回到最初的最初的状态，也就是说从1，2，4，8…..开始,不过这个时候我们还会把ssthresh调小，调为MAX值的一半，即ssthresh = MAX / 2。

快速重传机制

即当接收端收到比期望序号大的报文段时，便会重复发送最近一次确认的报文段的确认信号，我们称之为冗余ACK，如果发送端在超时重传定时器溢出之前，接收到连续的三个重复冗余ACK就重发该报文段。

流量控制

滑动窗口

当发送方收到接受窗口 win = 0 时，这时发送方停止发送报文，并且同时开启一个定时器，每隔一段时间就发个测试报文去询问接收方，打听是否可以继续发送数据了，如果可以，接收方就告诉他此时接受窗口的大小；如果接受窗口大小还是为0，则发送方再次刷新启动定时器。

1）目的：接受方通过TCP头窗口字段告知发送方可接收的最大数据量——解决发送速率过快导致接受方无法接收的问题。 流量控制 —— 对点控制
2）TCP是双工协议，双方可以同时通信，发送方和接受方各自维护一个发送窗和接收窗。发送窗：限制发送方可以发送的数据大小。接收窗：用来标记可以接收的数据大小。

TCP如何提供可靠数据传输

建立连接（标志位）：通信前确认通信实体存在。

序号机制（序号、确认号）：确保了数据是按序、完整到达。

数据校验（校验和）：CRC校验全部数据。

超时重传（定时器）：保证因链路故障未能到达数据能够被多次重发。

窗口机制（窗口）：提供流量控制，避免过量发送。

拥塞控制：同上。

如何区分流量控制和拥塞控制？

流量控制属于通信双方协商；拥塞控制涉及通信链路全局。流量控制需要通信双方各维护一个发送窗、一个接收窗，对任意一方，接收窗大小由自身决定，发送窗大小由接收方响应的TCP报文段中窗口值确定；拥塞控制的拥塞窗口大小变化由试探性发送一定数据量数据探查网络状况后而自适应调整。实际最终发送窗口 = min{流控发送窗口，拥塞窗口}。

操作系统

select epoll poll

Select：是一个阻塞函数，如果一直没有fd发生事件，程序会一直阻塞在select函数那一行。

缺点：①1024 bitmap ②FDset不可重用 ③用户态《——》内核态 切换开销 ④O(n)的轮询

POLL：与select工作原理很像，但是用 pollfds取代了bitmap，pollfd以链表形式存在，所以理论上是无上线的。

Poll解决的问题：①pollfd 大小不止 1024 ②pollfd可以重用

EPOLL：基于事件的回调

默认LT模式，高速ET模式

①执行epoll_create时，创建了红黑树

②执行epoll_ctl（配置需要监听的fd及其事件）时，创建就绪List链表，如果增加fd添加到红黑树上，然后向内核注册 有事件到来时的回调函数 ， 当设备上的中断事件来临时，回调函数会向list链表中插入就绪的fd并唤醒epoll_wait进程。

③执行epoll_wait时，立刻返回准备就绪链表里的数据即可。

解决问题：①不需要切换 用户内核态拷贝开销 ②遍历复杂度是O(1)

如果采用EPOLLLT模式的话，系统中一旦有大量你不需要读写的就绪文件描述符，它们每次调用epoll_wait都会返回，这样会大大降低处理程序检索自己关心的就绪文件描述符的效率.。而采用EPOLLET这种边沿触发模式的话，当被监控的文件描述符上有可读写事件发生时，epoll_wait()会通知处理程序去读写。如果这次没有把数据全部读写完(如读写缓冲区太小)，那么下次调用epoll_wait()时，它不会通知你，也就是它只会通知你一次，直到该文件描述符上出现第二次可读写事件才会通知你！！！这种模式比水平触发效率高，系统不会充斥大量你不关心的就绪文件描述符

http keep-alive与tcp keep-alive

链接建立之后，如果应用程序或者上层协议一直不发送数据，或者隔很长时间才发送一次数据，当链接很久没有数据报文传输时如何去确定对方还在线，到底是掉线了还是确实没有数据传输，链接还需不需要保持，这种情况在TCP协议设计中是需要考虑到的。

http keep-alive与tcp keep-alive，不是同一回事，意图不一样。http keep-alive是为了让tcp活得更久一点，以便在同一个连接上传送多个http，提高socket的效率。而tcp keep-alive是TCP的一种检测TCP连接状况的保鲜机制。

Redis实习缓存同步

实际问题

怎么解决bug问题，有用日志吗？

使用jstack通过pid去dump出堆栈信息

使用slf4j框架，内部使用logback

其他

哈希冲突法

​ 1.开放地址法

　　　按顺序决定哈希值时，如果某数据的哈希值已经存在，则在原来哈希值的基础 上往后加一个单位，直至不发生哈希冲突。

  1. 拉链法

    HashMap的方法

  2. 再哈希法

    对于冲突的哈希值使用其他哈希法哈希，直至没有哈希冲突。

  3. 建立公共溢出区

    建立公共溢出区存储所有哈希冲突的数据。