面向面试题学习(2) 2019-6-3

字数统计: 4.2k   |   阅读时长≈ 15 分钟

  1. 大数相加
  2. 反转链表
  3. 生产者消费者模式
  4. 阻塞队列
  5. 死锁的SQL
  6. group by having
  7. 网络tcp https
  8. 数据库索引优化
  9. 设计模式

1. 大数相加

方法一：模拟进位

算法

每次处理最后两个字符数字，进行模拟进位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {

    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0; // 进位
        for(int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--){
            int x = i < 0 ? 0 : num1.charAt(i) - '0';
            int y = j < 0 ? 0 : num2.charAt(j) - '0';
            sb.append((x + y + carry) % 10);
            carry = (x + y + carry) / 10;
        }
        return sb.reverse().toString();
    }
}

2. 反转链表

leetcode官方题解 https://leetcode-cn.com/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-by-leetcode/

方法一：迭代

假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

复杂度分析

  • 时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
  • 空间复杂度：O(1)。

方法二：递归

1
2
3
4
5
6
7
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

3. 生产者消费者模式

什么是生产者/消费者模型

一种重要的模型，基于等待/通知机制。生产者/消费者模型描述的是有一块缓冲区作为仓库，生产者可将产品放入仓库，消费者可以从仓库中取出产品，生产者/消费者模型关注的是以下几个点：

  • 生产者生产的时候消费者不能消费
  • 消费者消费的时候生产者不能生产
  • 缓冲区空时消费者不能消费
  • 缓冲区满时生产者不能生产

生产者/模型作为一种重要的模型，它的优点在于：

  • 解耦。因为多了一个缓冲区，所以生产者和消费者并不直接相互调用，这一点很容易想到，这样生产者和消费者的代码发生变化，都不会对对方产生影响，这样其实就把生产者和消费者之间的强耦合解开，变为了生产者和缓冲区/消费者和缓冲区之间的弱耦合
  • 通过平衡生产者和消费者的处理能力来提高整体处理数据的速度，这是生产者/消费者模型最重要的一个优点。如果消费者直接从生产者这里拿数据，如果生产者生产的速度很慢，但消费者消费的速度很快，那消费者就得占用CPU的时间片白白等在那边。有了生产者/消费者模型，生产者和消费者就是两个独立的并发体，生产者把生产出来的数据往缓冲区一丢就好了，不必管消费者；消费者也是，从缓冲区去拿数据就好了，也不必管生产者，缓冲区满了就不生产，缓冲区空了就不消费，使生产者/消费者的处理能力达到一个动态的平衡

4. 阻塞队列

https://juejin.im/post/5aa8dcd1f265da237e096af6

5 死锁的SQL

Mysql并发时经典常见的死锁原因及解决方法

mysql使用kill命令解决死锁问题,杀死某条正在执行的sql语句

在使用mysql运行某些语句时，会因数据量太大而导致死锁，没有反映。这个时候，就需要kill掉某个正在消耗资源的query语句即可，　KILL命令的语法格式如下：

mysql解除死锁

1
2
show processlist
kill 8358

MYSQL出现WAITING FOR TABLE METADATA LOCK的原因和解决方案:

使用管理员权限登录mysql数据库查看未提交的事务：select * from information_schema.innodb_trx

或者select * from information_schema.innodb_trx\G;【纵向查看】

其中字段解释如下：

  • trx_state: 事务状态，一般为RUNNING
  • trx_started: 事务执行的起始时间，若时间较长，则要分析该事务是否合理
  • trx_mysql_thread_id: MySQL的线程ID，用于kill
  • trx_query: 事务中的sql

kill 掉线程ID，问题解决。

6. group by having

1
2
having是分组（group by）后的筛选条件，分组后的数据组内再筛选
where则是在分组前筛选

7. 网络tcp https

TCP、UDP、HTTP与HTTPS的异同

TCP、UDP、HTTP与HTTPS都是通信协议，在这里首先先介绍一下什么是通信协议。

什么是通信协议？

通信协议（communications protocol）是指双方实体完成通信或服务所必须遵循的规则和约定。通过通信信道和设备互连起来的多个不同地理位置的数据通信系统，要使其能协同工作实现信息交换和资源共享，它们之间必须具有共同的语言。交流什么、怎样交流及何时交流，都必须遵循某种互相都能接受的规则。这个规则就是通信协议。

什么是TCP？

TCP是Transmission Control Protocol的缩写，也就是传输控制协议。它是一种面向连接的、可靠的、基于字节流的[传输层]通信协议。主要解决数据如何在网络中如何传输的，是一种长连接。建立一个TCP连接需要有三次握手，而终止一个TCP连接需要有4次握手，这是由TCP的半关闭（half-close）造成的。TCP包头的最小长度为20字节。

建立连接的三次握手

第一次握手：客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认;
第二次握手：服务器收到syn包，必须确认客户的SYN(ack=j+1)，同时自己也发送一个SYN包(syn=k)，即SYN+ACK包，此时服务器进入SYN_RECV状态;
第三次握手：客户端收到服务器的SYN+ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。
握手过程中传送的包里不包含数据，三次握手完毕后，客户端与服务器才正式开始传送数据。
TCP一旦连接起来，在客户端和服务端任何一方主动关闭连接之前，TCP连接都将被一直保持下去。
断开连接时，服务器和客户端都可以主动发起断开TCP连接的请求。
简单来说，第一次握手就是客户端向服务器问我可以发送数据吗；第二次握手就是服务器回答说可以；第三次握手就是客户端向服务器说那我要开始发送数据了，此时客户端和服务器都准备好传输数据了，三次握手就完成了。

断开连接的四次握手

(1) 某个应用进程首先调用close，称该端执行“主动关闭”（active close）。该端的TCP于是发送一个FIN分节，表示数据发送完毕。
(2) 接收到这个FIN的对端执行 “被动关闭”（passive close），这个FIN由TCP确认。
注意：FIN的接收也作为一个文件结束符（end-of-file）传递给接收端应用进程，放在已排队等候该应用进程接收的任何其他数据之后，因为，FIN的接收意味着接收端应用进程在相应连接上再无额外数据可接收。
(3) 一段时间后，接收到这个文件结束符的应用进程将调用close关闭它的套接字。这导致它的TCP也发送一个FIN。
(4) 接收这个最终FIN的原发送端TCP（即执行主动关闭的那一端）确认这个FIN。
既然每个方向都需要一个FIN和一个ACK，因此通常需要4个分节。

什么是UDP？

UDP是User Datagram Protocol的缩写，也就是用户数据报协议。它与TCP相对应，是一种面向无连接的、不可靠的数据报传输协议，即不与对方建立连接，就直接就把数据包发送过去，因此缺乏可靠性。由于缺乏可靠性，UDP应用一般必须允许一定量的丢包、出错和复制。
UDP简单总结起来就是下面的几点：
（1） UDP是一个非连接的协议，传输数据之前源端和终端不建立连接，当它想传送时就简单地去抓取来自应用程序的数据，并尽可能快地把它扔到网络上。在发送端，UDP传送数据的速度仅仅是受应用程序生成数据的速度、计算机的能力和传输带宽的限制；在接收端，UDP把每个消息段放在队列中，应用程序每次从队列中读一个消息段。
（2） 由于传输数据不建立连接，因此也就不需要维护连接状态，包括收发状态等，因此一台服务机可同时向多个客户机传输相同的消息。
（3） UDP信息包的标题很短，只有8个字节，相对于TCP的20个字节信息包的额外开销很小。
（4） 吞吐量不受拥挤控制算法的调节，只受应用软件生成数据的速率、传输带宽、源端和终端主机性能的限制。
（5）UDP使用尽最大努力交付，即不保证可靠交付，因此主机不需要维持复杂的链接状态表（这里面有许多参数）。
（6）UDP是面向报文的。发送方的UDP对应用程序交下来的报文，在添加首部后就向下交付给IP层。既不拆分，也不合并，而是保留这些报文的边界，因此，应用程序需要选择合适的报文大小。
我们经常使用“ping”命令来测试两台主机之间TCP/IP通信是否正常，其实“ping”命令的原理就是向对方主机发送UDP数据包，然后对方主机确认收到数据包，如果数据包是否到达的消息及时反馈回来，那么网络就是通的。

TCP与UDP的区别

（1）TCP是需要连接的传输协议（长连接），UDP是不需要连接的传输协议；
（2）TCP对系统资源要求较多，UDP要求较少；
（3）TCP的程序结构较复杂，UDP程序结构较简单；
（4）TCP是流模式，UDP是数据报模式 ；
（5）TCP保证数据正确性，UDP可能丢包，TCP保证数据顺序，UDP不保证。

什么是HTTP？

HTTP是HyperText Transfer Protocol的缩写，也就是超文本传输协议。HTTP是Web联网的基础，也是手机联网常用的协议之一，HTTP协议是建立在TCP协议之上的一种应用。HTTP连接最显著的特点是客户端发送的每次请求都需要服务器回送响应，在请求结束后，会主动释放连接。从建立连接到关闭连接的过程称为“一次连接”。
HTTP协议的主要特点可概括如下：
1.支持客户/服务器模式。
2.简单快速：客户向服务器请求服务时，只需传送请求方法和路径。请求方法常用的有GET、HEAD、POST。每种方法规定了客户与服务器联系的类型不同。由于HTTP协议简单，使得HTTP服务器的程序规模小，因而通信速度很快。
3.灵活：HTTP允许传输任意类型的数据对象。正在传输的类型由Content-Type加以标记。
4.无连接：无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求，并收到客户的应答后，即断开连接。采用这种方式可以节省传输时间。
5.无状态：HTTP协议是无状态协议。无状态是指协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息，则它必须重传，这样可能导致每次连接传送的数据量增大。另一方面，在服务器不需要先前信息时它的应答就较快。

HTTP协议之Get和Post

Http协议定义了很多与服务器交互的方法，最基本的有4种，分别是GET,POST,PUT,DELETE. 一个URL地址用于描述一个网络上的资源，而HTTP中的GET, POST, PUT, DELETE就对应着对这个资源的查，改，增，删4个操作。 我们最常见的就是GET和POST了。GET一般用于获取/查询资源信息，而POST一般用于更新资源信息.

GET和POST的区别
  1. GET提交的数据会放在URL之后，以问号（？）分割URL和传输数据，参数之间以符号&相连，如EditPosts.aspx?name=test1&id=123456. POST方法是把提交的数据放在HTTP包的Body中。
  2. GET提交的数据大小有限制（因为浏览器对URL的长度有限制），而POST方法提交的数据没有限制。
  3. GET方式需要使用Request.QueryString来取得变量的值，而POST方式通过Request.Form来获取变量的值，也就是说Get是通过地址栏来传值，而Post是通过提交表单来传值。
  4. GET方式提交数据，会带来安全问题，比如一个登录页面，通过GET方式提交数据时，用户名和密码将出现在URL上，如果页面可以被缓存或者其他人可以访问这台机器，就可以从历史记录获得该用户的账号和密码，相比之下POST更安全。

什么是HTTPS？

HTTP是Secure Hypertext Transfer Protocol的缩写，也就是安全超文本传输协议。它是一个安全通信通道，它基于HTTP开发，用于在客户计算机和服务器之间交换信息。它使用安全套接字层(SSL)进行信息交换，简单来说它是HTTP的安全版。

HTTP与HTTPS的区别

一、HTTPS协议需要到CA申请证书，一般免费证书很少，需要交费。
二、HTTP是超文本传输协议信息是明文传输，HTTPS则是具有安全性的ssl加密传输协议。
三、HTTP和HTTPS使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
四、HTTP的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比HTTP协议安全。
五、在OSI 网络模型中，HTTP和HTTPS都工作于应用层。

Socket

Socket是为了实现通信过程而建立成来的通信管道，其真实的代表是客户端和服务器端的一个通信进程，双方进程通过Socket进行通信，而通信的规则采用指定的协议。Socket只是一种连接模式，不是协议，TCP、UDP，简单的说（虽然不准确）是两个最基本的协议,很多其它协议都是基于这两个协议如，HTTP就是基于TCP的，.用Socket可以创建TCP连接，也可以创建UDP连接，这意味着，用Socket可以创建任何协议的连接，因为其它协议都是基于此的。
实际上，传输层的TCP是基于网络层的IP协议的，而应用层的HTTP协议又是基于传输层的TCP协议的，而Socket本身不算是协议，就像上面所说，它只是提供了一个针对TCP或者UDP编程的接口。

TCP/IP

TCP/IP是一个协议组，分为网络层、传输层、应用层。
在网络层有IP协议、ICMP协议、ARP协议、RARP协议和BOOTP协议。
在传输层有TCP协议和UDP协议。
在应用层有FTP、HTTP、TELNET、SMTP、DNS等协议。

作者：神SKY

链接：https://www.jianshu.com/p/f4005c1c728f

8. 数据库索引优化

阿里P8架构师谈：MySQL慢查询优化、索引优化、以及表等优化总结

美团技术团队：

MySQL索引原理及慢查询优化

9. 设计模式

设计模式常见面试题

常见设计模式笔试面试题

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2023 高行行
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信