TP 面经

Longest Increasing Subsequence
Medium

5310

115

Add to List

Share
Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0||nums==null) return 0;
        int[] dp=new int[nums.length];
        for(int i=0;i<nums.length;i++){
            dp[i]=1;
        }
        int res =1;
        for(int i=1;i<nums.length;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]&&dp[j]+1>dp[i]){
                    dp[i]=dp[j]+1;
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

https://blog.csdn.net/qq_37774171/article/details/81203890

#include <iostream>  
using namespace std;  
#define len(a) (sizeof(a) / sizeof(a[0])) //数组长度  
int lis(int arr[], int len)  
{  
    int longest[len];  
    for (int i=0; i<len; i++)  
        longest[i] = 1;  
  
    for (int j=1; j<len; j++) {  
        for (int i=0; i<j; i++) {  
            if (arr[j]>arr[i] && longest[j]<longest[i]+1){ //注意longest[j]<longest[i]+1这个条件，不能省略。  
                longest[j] = longest[i] + 1; //计算以arr[j]结尾的序列的最长递增子序列长度  
            }  
        }  
    }  
  
    int max = 0;  
    for (int j=0; j<len; j++) {  
        cout << "longest[" << j << "]=" << longest[j] << endl;  
        if (longest[j] > max) max = longest[j];  //从longest[j]中找出最大值  
    }  
    return max;  
}  
  
int main()  
{  
    int arr[] = {1, 4, 5, 6, 2, 3, 8}; //测试数组  
    int ret = lis(arr, len(arr));  
    cout << "max increment substring len=" << ret << endl;  
    return 0;  
}

6、编译和链接是什么？
编译

将预处理生成的文件，经过词法分析、语法分析、语义分析以及优化后编译成若干个目标模块。可以理解为将高级语言翻译为计算机可以理解的二进制代码，即机器语言。

链接

由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的载入模型。链接主要解决模块间的相互引用问题。分为地址和空间分配，符号解析和重定位几个步骤。在编译阶段生成目标文件时，会暂时搁置那些外部引用，而这些外部引用就是在链接时进行确定的，链接器在链接时，会根据符号名称去相应模块中寻找对应符号。待符号确定之后，链接器会重写之前那些未确定的符号的地址，这个过程就是重定位。链接一般分为静态链接、载入时动态链接以及运行时动态链接三种。

作者：linjw1008
链接：https://www.nowcoder.com/discuss/502074?type=post&order=time&pos=&page=0&channel=1009&source_id=search_post
来源：牛客网

第一部分：基础问题
1、C语言栈与堆的区别？
1、栈

什么是栈，它是你的电脑内存的一个特别区域，它用来存储被每一个function（包括mian（）方法）创建的临时变量。栈是FILO，就是先进后出原则的结构体，它密切的被CPU管理和充分利用。每次function声明一个新的变量，它就会被“推”到栈中。然后每次一个function退出时，所有关于这个函数中定义的变量都会被释放（换句话说就是删除）。一旦栈中的变量释放，这块区域就会变成可用的，提供给其他栈中的变量。

用栈存储变量的好处是，内存是被你管理的。你不用手动的创建内存，不用当你不在需要它的时候手动释放内存。另外，由于CPU组织栈内存很高效。读出和写入栈变量是很快的。

理解栈的关键是理解概念，当一个function退出时，所有它的变量都会从栈中弹出,以后都会永远消失。因此栈中的变量本质是局部的。这和我们原来理解为变量作用域或者本地或者全局变量是相关的。在C中，一个公共的bug 是从你程序中的一个function外尝试访问一个在栈中的这个function的变量（在该function已经退出后）。

关于栈的另一个特点我们应该记住，就是存储再栈中的变量的大小有限制。而堆上创建变量不用考虑。

总结栈：

a、栈的生长和伸缩就是函数压入或者推出局部变量。

b、我们不用自己去管理内存，变量创建和释放都是自动的。

c、栈中的变量只有在函数创建运行时存在。

2、堆

堆也是我们的计算机内存中的一个区域，但是他不是自动管理的。而且也不是被CPU密切的管理着。它是一片更加自由的内存区域（很大）。要想在堆上创建内存，我们必须使用malloc() 或者calloc（），他们都是C语言编译的。一旦你在堆上分配内存，当你不在需要的时候你必须用free()去销毁。如果你不销毁或者销毁失败，你的程序就会有内存泄露。换句话说就是堆内存会一直在，其他进程无法使用。我们将会再调试部分看到，那里有一个叫做Valgrind的东西，它可以帮助你发现内存泄露。

不像栈，堆没有变量大小的限制（除了你电脑的物理限制条件外）。堆内存读出和写入都比较慢，因为它必须使用指针图访问堆内存。我们将会下面讲解指针。

3、栈和堆的优缺点

栈：

a、快速访问。

b、没有必要明确的创建分类变量，因为它是自动管理的。

c、空间被CPU高效地管理着，内存不会变成碎片。

d、只有局部变量

e、受限于栈大小(取决于操作系统)

f、变量不能调整大小。

堆：

a、变量可以被全局访问

b、没有内存大小限制

c、（相对）访问比较慢

d、没有高效地使用空间，随着块内存的创建和销毁，内存可能会变成碎片。

e、你必须管理内存（变量的创建和销毁你必须要负责）

f、变量大小可以用realloc( )调整

2、什么是死锁？如何避免？
线程死锁描述的是这样一种情况：多个线程同时被阻塞，它们中的一个或者全部都在等待某个资源被释放。由于线程被无限期地阻塞，因此程序不可能正常终止。

如下图所示，线程 A 持有资源 2，线程 B 持有资源 1，他们同时都想申请对方的资源，所以这两个线程就会互相等待而进入死锁状态。
在这里插入图片描述
学过操作系统的朋友都知道产生死锁必须具备以下四个条件：

互斥条件：该资源任意一个时刻只由一个线程占用。
请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件:线程已获得的资源在末使用完之前不能被其他线程强行剥夺，只有自己使用完毕后才释放资源。
循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
8.2. 如何避免线程死锁?
我上面说了产生死锁的四个必要条件，为了避免死锁，我们只要破坏产生死锁的四个条件中的其中一个就可以了。现在我们来挨个分析一下：

破坏互斥条件：这个条件我们没有办法破坏，因为我们用锁本来就是想让他们互斥的（临界资源需要互斥访问）。
破坏请求与保持条件：一次性申请所有的资源。
破坏不剥夺条件：占用部分资源的线程进一步申请其他资源时，如果申请不到，可以主动释放它占有的资源。
破坏循环等待条件：靠按序申请资源来预防。按某一顺序申请资源，释放资源则反序释放。破坏循环等待条件。

3、一个链表如何判断是否有环？

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
        return false;
    }

4、常见排序算法有哪些？

在这里插入图片描述

5、快速排序的算法复杂度是多少？

举个例子
待排数组 6 9 9 10 11
我们选择第一个9作为主元（过程是随机的），若把小于等于放在主元的左边，则第二个9就跑到第一个9左面了，从而导致不稳定
主元的选择是随机的，导致不稳定的原因在于我们无法保证每次都是稳定的，所以它是不稳定的。
6、tcp四次挥手过程？
在这里插入图片描述
第一次挥手：Client将FIN置为1，发送一个序列号seq给Server；进入FIN_WAIT_1状态；
第二次挥手：Server收到FIN之后，发送一个ACK=1，acknowledge number=收到的序列号+1；进入CLOSE_WAIT状态。此时客户端已经没有要发送的数据了，但仍可以接受服务器发来的数据。
第三次挥手：Server将FIN置1，发送一个序列号给Client；进入LAST_ACK状态；
第四次挥手：Client收到服务器的FIN后，进入TIME_WAIT状态；接着将ACK置1，发送一个acknowledge number=序列号+1给服务器；服务器收到后，确认acknowledge number后，变为CLOSED状态，不再向客户端发送数据。客户端等待2*MSL（报文段最长寿命）时间后，也进入CLOSED状态。完成四次挥手。
为什么不能把服务器发送的ACK和FIN合并起来，变成三次挥手（CLOSE_WAIT状态意义是什么）？
展开
因为服务器收到客户端断开连接的请求时，可能还有一些数据没有发完，这时先回复ACK，表示接收到了断开连接的请求。等到数据发完之后再发FIN，断开服务器到客户端的数据传送。

如果第二次挥手时服务器的ACK没有送达客户端，会怎样？
展开
客户端没有收到ACK确认，会重新发送FIN请求。

客户端TIME_WAIT状态的意义是什么？
展开
第四次挥手时，客户端发送给服务器的ACK有可能丢失，TIME_WAIT状态就是用来重发可能丢失的ACK报文。如果Server没有收到ACK，就会重发FIN，如果Client在2*MSL的时间内收到了FIN，就会重新发送ACK并再次等待2MSL，防止Server没有收到ACK而不断重发FIN。

MSL(Maximum Segment Lifetime)，指一个片段在网络中最大的存活时间，2MSL就是一个发送和一个回复所需的最大时间。如果直到2MSL，Client都没有再次收到FIN，那么Client推断ACK已经被成功接收，则结束TCP连接。

作者：qiaoqiaoer
链接：https://www.nowcoder.com/discuss/442024?type=post&order=time&pos=&page=2&channel=1009&source_id=search_post
来源：牛客网

1.自我介绍
2.说说项目以及由项目发问的问题
多线程：
进程与线程
进程是程序的一次动态执行过程，它需要经历从代码加载，代码执行到执行完毕的一个完整的过程，这个过程也是进程本身从产生，发展到最终消亡的过程。多进程操作系统能同时达运行多个进程（程序），由于 CPU 具备分时机制，所以每个进程都能循环获得自己的CPU 时间片。由于 CPU 执行速度非常快，使得所有程序好像是在同时运行一样。

多线程是实现并发机制的一种有效手段。进程和线程一样，都是实现并发的一个基本单位。线程是比进程更小的执行单位，线程是进程的基础之上进行进一步的划分。所谓多线程是指一个进程在执行过程中可以产生多个更小的程序单元，这些更小的单元称为线程，这些线程可以同时存在，同时运行，一个进程可能包含多个同时执行的线程。进程与线程的区别如图所示：
Java中线程实现的方式
在 Java 中实现多线程有两种手段，一种是继承 Thread 类，另一种就是实现 Runnable 接口。下面我们就分别来介绍这两种方式的使用。

实现 Runnable 接口
从程序可以看出，现在的两个线程对象是交错运行的，哪个线程对象抢到了 CPU 资源，哪个线程就可以运行，所以程序每次的运行结果肯定是不一样的，在线程启动虽然调用的是 start() 方法，但实际上调用的却是 run() 方法定义的主体。

Thread 类和 Runnable 接口

通过 Thread 类和 Runable 接口都可以实现多线程，那么两者有哪些联系和区别呢？下面我们观察 Thread 类的定义。

public class Thread extends Object implements Runnable
从 Thread 类的定义可以清楚的发现，Thread 类也是 Runnable 接口的子类，但在Thread类中并没有完全实现 Runnable 接口中的 run() 方法，下面是 Thread 类的部分定义。
线程的状态变化
要想实现多线程，必须在主线程中创建新的线程对象。任何线程一般具有5种状态，即创建，就绪，运行，阻塞，终止。下面分别介绍一下这几种状态：

创建状态

在程序中用构造方法创建了一个线程对象后，新的线程对象便处于新建状态，此时它已经有了相应的内存空间和其他资源，但还处于不可运行状态。新建一个线程对象可采用Thread 类的构造方法来实现，例如 “Thread thread=new Thread()”。

就绪状态

新建线程对象后，调用该线程的 start() 方法就可以启动线程。当线程启动时，线程进入就绪状态。此时，线程将进入线程队列排队，等待 CPU 服务，这表明它已经具备了运行条件。

运行状态

当就绪状态被调用并获得处理器资源时，线程就进入了运行状态。此时，自动调用该线程对象的 run() 方法。run() 方法定义该线程的操作和功能。

阻塞状态

一个正在执行的线程在某些特殊情况下，如被人为挂起或需要执行耗时的输入/输出操作，会让 CPU 暂时中止自己的执行，进入阻塞状态。在可执行状态下，如果调用sleep(),suspend(),wait() 等方法，线程都将进入阻塞状态，发生阻塞时线程不能进入排队队列，只有当引起阻塞的原因被消除后，线程才可以转入就绪状态。

死亡状态

线程调用 stop() 方法时或 run() 方法执行结束后，即处于死亡状态。处于死亡状态的线程不具有继续运行的能力。

在这里插入图片描述

3.线程池的种类
ThreadPoolExecutor 3 个最重要的参数：

corePoolSize : 核心线程数线程数定义了最小可以同时运行的线程数量。
maximumPoolSize : 当队列中存放的任务达到队列容量的时候，当前可以同时运行的线程数量变为最大线程数。
workQueue: 当新任务来的时候会先判断当前运行的线程数量是否达到核心线程数，如果达到的话，新任务就会被存放在队列中。
ThreadPoolExecutor其他常见参数:

keepAliveTime:当线程池中的线程数量大于 corePoolSize 的时候，如果这时没有新的任务提交，核心线程外的线程不会立即销毁，而是会等待，直到等待的时间超过了 keepAliveTime才会被回收销毁；
unit : keepAliveTime 参数的时间单位。
threadFactory :executor 创建新线程的时候会用到。
handler :饱和策略。关于饱和策略下面单独介绍一下。ThreadPoolExecutor 饱和策略定义:

如果当前同时运行的线程数量达到最大线程数量并且队列也已经被放满了任务时，ThreadPoolTaskExecutor 定义一些策略:

ThreadPoolExecutor.AbortPolicy：抛出 RejectedExecutionException来拒绝新任务的处理。
ThreadPoolExecutor.CallerRunsPolicy：调用执行自己的线程运行任务，也就是直接在调用execute方法的线程中运行(run)被拒绝的任务，如果执行程序已关闭，则会丢弃该任务。因此这种策略会降低对于新任务提交速度，影响程序的整体性能。如果您的应用程序可以承受此延迟并且你要求任何一个任务请求都要被执行的话，你可以选择这个策略。
ThreadPoolExecutor.DiscardPolicy：不处理新任务，直接丢弃掉。
ThreadPoolExecutor.DiscardOldestPolicy：此策略将丢弃最早的未处理的任务请求。
FixedThreadPool 被称为可重用固定线程数的线程池
SingleThreadExecutor 是只有一个线程的线程池。下面看看SingleThreadExecutor
CachedThreadPool 是一个会根据需要创建新线程的线程池
4.如何创建线程

5.java多态的体现

二面什么鬼d(ŐдŐ๑)
一道智力题：赛马选前三快前五快
一道滑动窗口的编程题
二面面的不好，智力题一下子懵掉了，在老师引导下做出来一部分，编程题想的比较快，但编程上有点漏洞（是白板编程，用的记事本）

然后是几道智力题:1.给你一个整数n，怎么用一行代码判断是不是3的幂次方(脑子一懵答调用log3()函数，惭愧)

public boolean isPowerOf3_3(int n) {
        return n > 0 && 1162261467 % n == 0;
    }

2.上楼梯，一次一级或两级，一百层多少种

作者：塔洛克
链接：https://www.nowcoder.com/discuss/498900?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

3，session和cookie的区别，登录信息放在session还是cookie中，为什么刷新网页登录状态还在，关闭浏览器就要重新登录。
Cookie 和 Session都是用来跟踪浏览器用户身份的会话方式，但是两者的应用场景不太一样。

Cookie 一般用来保存用户信息比如①我们在 Cookie 中保存已经登录过得用户信息，下次访问网站的时候页面可以自动帮你登录的一些基本信息给填了；②一般的网站都会有保持登录也就是说下次你再访问网站的时候就不需要重新登录了，这是因为用户登录的时候我们可以存放了一个 Token 在 Cookie 中，下次登录的时候只需要根据 Token 值来查找用户即可(为了安全考虑，重新登录一般要将 Token 重写)；③登录一次网站后访问网站其他页面不需要重新登录。Session 的主要作用就是通过服务端记录用户的状态。典型的场景是购物车，当你要添加商品到购物车的时候，系统不知道是哪个用户操作的，因为 HTTP 协议是无状态的。服务端给特定的用户创建特定的 Session 之后就可以标识这个用户并且跟踪这个用户了。

Cookie 数据保存在客户端(浏览器端)，Session 数据保存在服务器端。

Cookie 存储在客户端中，而Session存储在服务器上，相对来说 Session 安全性更高。如果要在 Cookie 中存储一些敏感信息，不要直接写入 Cookie 中，最好能将 Cookie 信息加密然后使用到的时候再去服务器端解密。

4，如何使用多线程，为什么还需要继承Thread类的方式去实现多线程。CAS循环性能开销大如何解决。

ABA问题
因为CAS需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A。

从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

循环时间长开销大
自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。

只能保证一个共享变量的原子操作
当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作。
5，为什么不用DFS去实现最短路径算法。
6，SQL注入是个啥
　1、检查变量数据类型和格式

如果你的SQL语句是类似where id={$id}这种形式，数据库里所有的id都是数字，那么就应该在SQL被执行前，检查确保变量id是int类型；如果是接受邮箱，那就应该检查并严格确保变量一定是邮箱的格式，其他的类型比如日期、时间等也是一个道理。总结起来：只要是有固定格式的变量，在SQL语句执行前，应该严格按照固定格式去检查，确保变量是我们预想的格式，这样很大程度上可以避免SQL注入攻击。
　　比如，我们前面接受username参数例子中，我们的产品设计应该是在用户注册的一开始，就有一个用户名的规则，比如5-20个字符，只能由大小写字母、数字以及一些安全的符号组成，不包含特殊字符。此时我们应该有一个check_username的函数来进行统一的检查。不过，仍然有很多例外情况并不能应用到这一准则，比如文章发布系统，评论系统等必须要允许用户提交任意字符串的场景，这就需要采用过滤等其他方案了。

2、过滤特殊符号

对于无法确定固定格式的变量，一定要进行特殊符号过滤或转义处理。

3、绑定变量，使用预编译语句

MySQL的mysqli驱动提供了预编译语句的支持，不同的程序语言，都分别有使用预编译语句的方法

实际上，绑定变量使用预编译语句是预防SQL注入的最佳方式，使用预编译的SQL语句语义不会发生改变，在SQL语句中，变量用问号?表示，黑客即使本事再大，也无法改变SQL语句的结构
没了。。。看得出面试官很急

作者：Rannie
链接：https://www.nowcoder.com/discuss/498464?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

面试的开始时间拖延了40min
介绍项目1，相关问题
介绍项目2，相关问题
用户态和内核态的区别
根据进程访问资源的特点，我们可以把进程在系统上的运行分为两个级别：

用户态(user mode) : 用户态运行的进程或可以直接读取用户程序的数据。
系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。
说了用户态和系统态之后，那么什么是系统调用呢？

我们运行的程序基本都是运行在用户态，如果我们调用操作系统提供的系统态级别的子功能咋办呢？那就需要系统调用了！

也就是说在我们运行的用户程序中，凡是与系统态级别的资源有关的操作（如文件管理、进程控制、内存管理等)，都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。

信号量，互斥量用在什么时候
👨‍💻面试官：进程间的通信常见的的有哪几种方式呢?

🙋 我：大概有 7 种常见的进程间的通信方式。

下面这部分总结参考了:《进程间通信 IPC (InterProcess Communication)》这篇文章，推荐阅读，总结的非常不错。

管道/匿名管道(Pipes) ：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
有名管道(Names Pipes) : 匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。
信号(Signal) ：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生；
消息队列(Message Queuing) ：消息队列是消息的链表,具有特定的格式,存放在内存中并由消息队列标识符标识。管道和消息队列的通信数据都是先进先出的原则。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显示地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取.比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺。
信号量(Semaphores) ：信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
共享内存(Shared memory) ：使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据的更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
套接字(Sockets) : 此方法主要用于在客户端和服务器之间通过网络进行通信。套接字是支持 TCP/IP 的网络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的端点，简单的说就是通信的两方的一种约定，用套接字中的相关函数来完成通信过程。
2.4 线程间的同步的方式
👨‍💻面试官：那线程间的同步的方式有哪些呢?

🙋 我：线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。操作系统一般有下面三种线程同步的方式：

互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。比如 Java 中的 synchronized 关键词和各种 Lock 都是这种机制。
信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量
事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操
ping baidu会发生什么
ping我们可以认为是通过发送icmp包来探测主机状态.
ping程序需要发送icmp协议，该协议位于IP协议之上,所以我们要知道源IP和目的IP并封装到IP报文中，这时用到了DNS解析结果: 119.75.216.20
IP报文到达二层之后，需要封装源主机和"目的主机"(下一跳地址,并不是2中提到的目的地址)的MAC地址,成为帧.
通过物理链路传输
经过多个路由的转发到达119.75.216.20，转发过程中重新封装帧.
作者：甘神的烦恼
链接：https://www.nowcoder.com/discuss/441565?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

意向岗位：杭州软开

4 怎么判断链表有环
5 浏览器输入url都客户端显示页面的过程
1、要解析域名转换成对应的公网IP；

                  2、根据公网IP通过庞大的互联网路由到对应的服务器上；

                  3、建立可靠的TCP数据连接；

                  4、服务器对该URL中的请求进行处理分发，返回一个html；

                  5、浏览器或者客户端对该HTML进行渲染；

6 说一下二叉搜索树还有应用情景(忘记了具体情景，说了个哈夫曼编码给自己挖坑了？？？）
7 哈夫曼编码了解吗（不了解…）

8 有找其他实习（有，导师不放）
9 没有反问环节

面试官挺好的，没戴口罩，整体聊得还挺开心的，就是自己的项目一些没考虑到的点没回答好，也没想到面试官会这样问
整体20分钟不到，许愿能过一面

作者：牛客171542306号
链接：https://www.nowcoder.com/discuss/445214?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

一面很水，问题重复度很高，建议多看几篇面经，大概率会涵盖所有一面问题。
流程:
1、自我介绍，问考研保研；
2、问实验室项目，介绍分工和自己参与的工作；
3、问学习方式，问自己做的java项目；
4、问数据结构：常见的数据结构有哪些，然后会问一个简单的算法题，我的是单链表判断有环，我看别的面经还有可能问快排；
5、TCP、UDP区别，TCP三次握手；
TCP是面向连接的，UDP是无连接的；
什么叫无连接？
TCP是可靠的，UDP不可靠；
什么叫不可靠？
TCP只支持点对点通信，UDP支持一对一、一对多、多对一、多对多；
TCP是面向字节流的，UDP是面向报文的；
什么意思？
TCP有拥塞控制机制，UDP没有。网络出现的拥塞不会使源主机的发送速率降低，这对某些实时应用是很重要的，比如媒体通信，游戏；
TCP首部开销（20字节）比UDP首部开销（8字节）要大
UDP 的主机不需要维持复杂的连接状态表
什么时候选择TCP，什么时候选UDP？
展开
对某些实时性要求比较高的情况，选择UDP，比如游戏，媒体通信，实时视频流（直播），即使出现传输错误也可以容忍；其它大部分情况下，HTTP都是用TCP，因为要求传输的内容可靠，不出现丢失
HTTP可以使用UDP吗？
展开
HTTP不可以使用UDP，HTTP需要基于可靠的传输协议，而UDP不可靠
面向连接和无连接的区别
展开
无连接的网络服务（数据报服务）-- 面向连接的网络服务（虚电路服务）

虚电路服务：首先建立连接，所有的数据包经过相同的路径，服务质量有较好的保证；

数据报服务：每个数据包含目的地址，数据路由相互独立（路径可能变化）；网络尽最大努力交付数据，但不保证不丢失、不保证先后顺序、不保证在时限内交付；网络发生拥塞时，可能会将一些分组丢弃；

TCP如何保证传输的可靠性
数据包校验
对失序数据包重新排序（TCP报文具有序列号）
丢弃重复数据
应答机制：接收方收到数据之后，会发送一个确认（通常延迟几分之一秒）；
超时重发：发送方发出数据之后，启动一个定时器，超时未收到接收方的确认，则重新发送这个数据；
流量控制：确保接收端能够接收发送方的数据而不会缓冲区溢出

6、多线程：临界资源，锁
节奏很快，切忌拖泥带水，面试官会打断直接问下一个问题。

二面“视频”面，果然二面“视频/技术”面试有很大区别，上来啥技术问题都不问，扯些跟一面差不多的问题，感觉面试官毫无提问的兴趣，妥妥的走流程，也是难为面试官了。
作者：球球给我个offer叭！！！
链接：https://www.nowcoder.com/discuss/448956?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

昨天收到短信通知今天下午四点二面，因为在实习所以问hr能不能调整时间，最后给调到了上午9点，上班前面完😐
这一轮按hr的说法是高管面终面🍜
1.自我介绍
2.又问了本科成绩考研保研的问题
3.本科毕设做的什么
4.什么时候开始接触的java
5.学过哪些计算机相关的课程
6.用过java的哪些库哪些机制对于哪些数据结构的底层实现有了解自己写过数据结构吗
7.研究生课题用了哪些通信相关的数据
8.对网络协议了解吗，tcp的流量控制拥塞控制，还有ARP ICMP。没细问，就大概问了一下。

使用滑动窗口协议实现流量控制。防止发送方发送速率太快，接收方缓存区不够导致溢出。接收方会维护一个接收窗口 receiver window（窗口大小单位是字节），接受窗口的大小是根据自己的资源情况动态调整的，在返回ACK时将接受窗口大小放在TCP报文中的窗口字段告知发送方。发送窗口的大小不能超过接受窗口的大小，只有当发送方发送并收到确认之后，才能将发送窗口右移。

拥塞控制主要由四个算法组成：慢启动（Slow Start）、拥塞避免（Congestion voidance）、快重传（Fast Retransmit）、快恢复（Fast Recovery）

慢启动：刚开始发送数据时，先把拥塞窗口（congestion window）设置为一个最大报文段MSS的数值，每收到一个新的确认报文之后，就把拥塞窗口加1个MSS。这样每经过一个传输轮次（或者说是每经过一个往返时间RTT），拥塞窗口的大小就会加倍
slow start

拥塞避免：当拥塞窗口的大小达到慢开始门限(slow start threshold)时，开始执行拥塞避免算法，拥塞窗口大小不再指数增加，而是线性增加，即每经过一个传输轮次只增加1MSS.
无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认），就要把慢开始门限ssthresh设置为出现拥塞时的发送方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。（这是不使用快重传的情况）

快重传：快重传要求接收方在收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己发送数据时捎带确认。快重传算法规定，发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置的重传计时器时间到期。
快重传

快恢复：当发送方连续收到三个重复确认时，就把慢开始门限减半，然后执行拥塞避免算法。不执行慢开始算法的原因：因为如果网络出现拥塞的话就不会收到好几个重复的确认，所以发送方认为现在网络可能没有出现拥塞。
也有的快重传是把开始时的拥塞窗口cwnd值再增大一点，即等于 ssthresh + 3*MSS 。这样做的理由是：既然发送方收到三个重复的确认，就表明有三个分组已经离开了网络。这三个分组不再消耗网络的资源而是停留在接收方的缓存中。可见现在网络中减少了三个分组。因此可以适当把拥塞窗口扩大些。

发送窗口的上限为接受窗口和拥塞窗口中的较小值。接受窗口表明了接收方的接收能力，拥塞窗口表明了网络的传送能力。
9.对岗位的要求只考虑java吗，C C++这些呢
10.场景题有个文件里存储了url的访问记录如何统计出top N访问量的url，如果文件很大怎么考虑。
11.反问
作者：橘子桔子不知道
链接：https://www.nowcoder.com/discuss/443826?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

更新一下整个面试流程，为自己攒人品

6.14笔试感觉做得一般，具体题也记不清楚了

一面：

6.17

主要就是语言基础，操作系统，计算机网络相关的知识

讲研究生的项目（室内定位），问我挺细的，大概因为用了wifi信号？

然后问操作系统，我说我还没学，就简单讲了一下进程间的通信

TCP四次挥手

二面（技术面）：

6.19

有两个面试官，没有让我自我介绍，上来就直接开始说考我一些题，一共考了4道智力题，1道编程题。

智力题：

1 A.B两个人抛硬币，A先抛B后抛，如果A抛到正面A吃苹果，如果B抛到正面B吃苹果，如果两个人都是反面又继续下一轮，问A吃到苹果的概率

2 1000瓶试剂，其中一瓶有毒，稀释试剂不影响毒性，问至少多少只小白鼠才能找到有毒的试剂

3 25匹马赛跑，赛道每次只能容纳5匹，没有计时工具，问至少需要多少轮比赛才能找出前三名

4 有五个相邻狐狸洞，狐狸每晚一定会到旁边相邻的一个洞去，白天可以选择一个洞查看，问如何查看能抓住狐狸

编程题：

剑指offer的原题，有一段楼梯，每次可以上1阶，可以上2阶，问有多少种上楼梯的方法。

大家加油鸭～
作者：甘神的烦恼
链接：https://www.nowcoder.com/discuss/445242?type=post&order=time&pos=&page=2&channel=1009&source_id=search_post
来源：牛客网

时间线：

3 一轮视频面：固定问题，无关技术的比如自我介绍、专业背景、保研考研、有没有学过计算机专业课程、毕设项目和计算机是否相关，简历上的项目，有没有其他实习offer；基础问题：计算机网络，操作系统，线程，java基础、C++基础，都不难；算法：多为链表和二叉树，leetcode简单类型。每个问题他们都会打分，按照分数进行排序，只有分数打到一定分值，他们才会进行后续面试。这也可以解释，有的小伙伴一面二面就隔了1天，有的小伙伴6.17或18一面，6.29之后才二面。
“TP-LINK最看重的是专业背景，首先的是理工科，其次是实习，研究方向，TP-LINK认为基本所有的人都不满足公司的干活要求，公司得培养。”——来自一位猫头老哥
也根据分值，后面的面试开始出现了区别：二轮视频面 or 二轮技术面

二轮技术面一般是sp，后面还有hr面+第三轮面试；二轮视频面是白菜，按照牛客小伙伴的说法，应该是终面，后续没有面试。
根据牛客小伙伴的情况，二轮视频面不是凉凉也不是陪跑，只是白菜，还是会有offer的，大家别慌！

一轮视频面（java）渣渣的面经 https://www.nowcoder.com/discuss/441565?source_id=profile_create&channel=1004
计算机网络常见面试题：
a tcp/udp区别
b 三次握手/ 四次挥手

c tcp如何实现可靠传输
数据包校验
对失序数据包重新排序（TCP报文具有序列号）
丢弃重复数据
应答机制：接收方收到数据之后，会发送一个确认（通常延迟几分之一秒）；
超时重发：发送方发出数据之后，启动一个定时器，超时未收到接收方的确认，则重新发送这个数据；
流量控制：确保接收端能够接收发送方的数据而不会缓冲区溢出
d 长连接和短连接
在HTTP/1.0中默认使用短连接。也就是说，客户端和服务器每进行一次HTTP操作，就建立一次连接，任务结束就中断连接。当客户端浏览器访问的某个HTML或其他类型的Web页中包含有其他的Web资源（如JavaScript文件、图像文件、CSS文件等），每遇到这样一个Web资源，浏览器就会重新建立一个HTTP会话。

而从HTTP/1.1起，默认使用长连接，用以保持连接特性。使用长连接的HTTP协议，会在响应头加入这行代码：

Connection:keep-alive
Copy to clipboardErrorCopied
在使用长连接的情况下，当一个网页打开完成后，客户端和服务器之间用于传输HTTP数据的TCP连接不会关闭，客户端再次访问这个服务器时，会继续使用这一条已经建立的连接。Keep-Alive不会永久保持连接，它有一个保持时间，可以在不同的服务器软件（如Apache）中设定这个时间。实现长连接需要客户端和服务端都支持长连接。

HTTP协议的长连接和短连接，实质上是TCP协议的长连接和短连接。
e tcp滑动窗口机制

f 介绍osi七层网络模型和各层协议，并说说你熟悉哪些协议

g 说说tcp滑动窗口和拥塞窗口的联系与区别
解为接收方的缓存)可以缓解这一个问题。具体的操作是接收方会向发送方通知自己可以接受数据的大小，而发送方会根据这个数值，发送数据。
2.拥塞窗口用控制全局网络的拥塞情况。通过控制发送方每次发送的流量的多少，用来逐渐试探整体网络的拥塞程度。如果没有拥塞控制，发送方每次发送的数据大小为滑动窗口，在只有2台主机的时候确实是没有问题的，但是如果放到现实的网络大环境中来说是行不通的。因为如果每台主机都发送的窗口大小的数据，那么整个网络系统必然会瘫痪。所以通过在发送方设置拥塞窗口，可以有效缓解网络压力。
h 浏览器输入网址到客户端显示出网页的具体过程

4 二轮面试
4.1 二轮技术面：智力题+算法
总结的帖子 https://www.nowcoder.com/discuss/444340?channel=1004&source_id=home_feed
二轮技术面考核如果评价是不推荐SP的话，三轮面试又有了分支，三轮技术面和三轮视频面
三轮技术面就是sp了，三轮视频面又变成白菜了

4.2 二轮视频面：和一轮视频面相似，项目+基础，有的小伙伴还有算法。
后续可能没有面试，和春招的两轮面试情况相似，直接等offer吧。
offer应该是分批发的，有快有慢。
（很多个学弟春招2轮视频后，整整2周才收到offer，所以大家耐心等待，仅供参考）

5 hr面：常见问题，一般都会过。

6 三轮面试
6.1 三轮技术面（主管面）：简历、项目、实习、聊人生

6.1 三轮视频面：同上，but是白菜

分析本渣一面凉的原因：
1 专业不符，新东方厨师专业，虽然也是C7本硕，理工科背景，但和计算机相关度太低
2 半路出家，项目经验较少，且不够深入，对于很多技术问题停留在表面（虽然问得也不深入）
3 今年提前批招聘成本低，都是线上面试，报的人太多，大佬也多，按照分数排名，渣渣排名很低，今年提前批不再是双C7水水稳稳过
4 和2重了，我太菜了！！！

所以本渣渣秋招和春招再试一下，提前批，注定本渣渣提前退出！

去做毕设去了！
作者：我是个小小小菜
链接：https://www.nowcoder.com/discuss/442055?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

6-19一面
上来不废话直接问
怎么判断链表有环？
如何逆序打印链表
如何反转链表
epoll原理，和select不同之处
线程池相关
http报文（还问了一点项目相关的）

在这里插入图片描述

tcp位于哪一层，三次握手
聊了一点项目
到了20分钟面试的小哥突然说我这边的面试结束了，拜拜，没给反问机会，然后就着急忙慌的断开连接了。
求个二面吧。

6-24二面
自我介绍
问项目
线程池相关
tcp拥塞控制
进程间通信
以下是闲聊
研究生主要干什么
成绩怎么样（保研率多少）
性格是怎么样的
面试这个岗位的优势和劣势（建议我加深基础学习）
接受深圳岗位吗（接受接受，要我就成）
反问
求过
作者：hitxqy
链接：https://www.nowcoder.com/discuss/443343?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

tplink提前批一面面经
1、一开始自我介绍
2、然后询问本科成绩
3、介绍你的项目，面试官针对我的项目问了大部分时间，可能比较感兴趣把，简历上写的项目一定要了解清楚
4、介绍快排，快排为什么不稳定，介绍TCP三次握手，说Java关键字final的作用
5、找了一道笔试里的题目详细问了问

作者：FrankYoung12138
链接：https://www.nowcoder.com/discuss/445379?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

面试官人很nice，开始我很紧张，有些问题没有get到面试官的意思，面试官会换一种说法再委婉问一遍，慢慢就不紧张了。

对了我是深圳嵌入式软开

面试全程大概25分钟？流程大概如下：

自我介绍

根据自我介绍中的一些描述问了一些关于技术栈的问题

保研？排名怎么样？

是否熟悉网络编程？答有写web服务器，

简单介绍，并针对定时器和IO模型提问

平时用C多还是Cpp多

是否熟悉hashmap底层实现

学过什么课程，计网熟悉吧，描述一下ARP

如何实现ARP高速缓存表

PS：成都嵌入式开发
9号笔试 11号一面 13号二面目前等通知中，可能有些凉，各位加油。
😁😁😁

作者：现实理想青年
链接：https://www.nowcoder.com/discuss/443659?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

6.24 下午 14：20 二面（终面）一个面试官技术+hr

提前一天收到二面通知，准备了很多智力题都没用上…😂😂😂
1.你哪里人？四川哪儿的？
四川…想留成都
2.我看你本硕都是…，考研还是保研？本科成绩？
3.问项目
这里底层通信协议是啥？怎么做的？
项目里面的秒级响应怎么体现的？
如何搭建数据库，用来做什么？
……记不清了
4.我看你这个技能写的Java多，但是嵌入式多是C语言，你怎么看？
5.你一面的时候我看有一个16进制字符串转数字，没写完？讲一下思路吧。
6.谈一谈Java里面的引用？
7.用C语言实现，判断两个二进制数有多少位不同，感觉很简单呀。（去掉符号位，异或，再数1？）
8.反问环节
确认了一下这个是终面，听说之后还有测评。
问了进去做什么。
我说我这边有什么不足的，能不能麻烦面试官点评建议一下，被拒绝hhh😂😂😂😂

整个面试31分钟，emmm 体验还阔以😂
许愿许愿许愿测评～
给面试机会的第一家，不管过不过都锻炼了一下，挺好的～😆😅

————————————
————————————
6.19 下午五点一面

全程只问了项目，一些技术细节，确定是你自己做的。
比赛一共是几个人，自己负责哪一部分？怎么分工？
最后撸一个16进制字符串转数字，太紧张，时间内没写出来😢😢😢
————————————

二面
有两个人，一个没说话
一共三道题
1.两个人轮流抛硬币，抛到正面的赢，先抛硬的概率
2.1000瓶药里一瓶毒药，一天检测完最少几只老鼠
3.数组里01序列，可以填充K个，问填充后最长的连续1的个数。先说思路再本地IDE写。
然后就结束里很迷。。

一面
面试的小哥听声音很年轻，上来喊我复盘笔试代码。笔试都一个月了。。。真不记得。
然后介绍项目，说了大概20分钟吧。
最后经典三问
C++内存哪些东西
进程线程区别
TCP/UDP区别

许愿。。

###一面分割线 6.18###
1、聊项目，因为自我介绍说了比较多项目内容，后续有将近十分钟都在讲项目的实现细节
2、因为楼主用的C++，所以开始问C++编程相关的东西
（1）static关键字有什么作用
（2）c++避免内存泄露的方式有哪些
（3）如何判断一个链表是环链表
（4）多进程和多线程的区别
（5）进程之间如何通信
（6）构造函数的调用顺序是怎样的
（7）产生死锁的原因
（8）二叉树的遍历方式
（9）快排的原理

11.智力题：20个小球中有一个小球是轻的，找出来，最少几次？

1。分三组7，7，6
两组7上天平称，最坏的情况是不一样重（一样重的话次品在6个中）
2。取轻的那一组，再分三组 1，3，3
两组3上天平称，最坏的情况是不一样重（一样重的话次品就是那个剩的）
2。在3个中随便拿2个称，不一样重轻的那个是次品，一样重剩下那个是次品
12.智力题：小鼠毒药问题，百度可搜到，面试前刚看了，押中了题。
13.另一个面试官（一直没说上话）：算法：爬楼梯。简单，口述一下没实际撸代码。

作者：mzpt丶
链接：https://www.nowcoder.com/discuss/443172?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

一面 2020-06-19

自我介绍
本科成绩排名
是考研的吗
选择一个项目介绍下流程，我提到前期有调研过程，于是问了调研了什么
介绍项目过程中提到了退避机制，于是问TCP的退避机制，拥塞控制
问OS的用户态和内核态的区别，什么情况下会触发从用户态到内核态的切换

这些系统调用按功能大致可分为如下几类：

设备管理。完成设备的请求或释放，以及设备启动等功能。
文件管理。完成文件的读、写、创建及删除等功能。
进程控制。完成进程的创建、撤销、阻塞及唤醒等功能。
进程通信。完成进程之间的消息传递或信号传递等功能。
内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能。
7. C和C++的区别
8. 名空间的作用
9. 快排为什么快？我介绍了一下快排的方法，然后说是O(NlogN)，于是问相比于其他O(NlogN)的排序，快排为什么更快
10. 问怎么求一棵二叉树的最大路径和，只需要说思路，不需要写代码

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        helper(root, res);
        return res;
    }
    int helper(TreeNode* node, int& res) {
        if (!node) return 0;
        int left = max(helper(node->left, res), 0);
        int right = max(helper(node->right, res), 0);
        res = max(res, left + right + node->val);
        return max(left, right) + node->val;
    }
};

一面是严格20分钟，面试官准时到，20分钟准时结束，没有给反问的机会

二面 2020-06-22
没有自我介绍环节，两个面试官，首先向我介绍了面试流程，说大约需要30-40分钟，是他们出题
12. 抛硬币吃苹果，抛到正面的人可以吃苹果，问先手的人吃到苹果的概率
13. 手撕代码，求一棵二叉树中两个节点的最近公共祖先，首先说思路，问了普通二叉树和搜索二叉树两种情况，说完思路就用本地IDE写代码
leetcode上做过，两道题十几分钟就做完了，然后面试官就说面试结束了

作者：皮皮欣
链接：https://www.nowcoder.com/discuss/442179?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

饿死我了从17:20等到18:00.。。。。。。。。
面经：
1、我同学他们都问了成绩，而我没有问。。。
2、我项目是通信相关，介绍了一堆，感觉有点乱，被面试官问了奇怪的问题。。。
3、static关键字，我c忘记了，胡扯了一下c++的
4、快排原理，时间复杂度，最差情况是什么情况，时间复杂度变多少
5、TCP三次握手，详细到SYN和ACK
6、进程间通信方式都有哪些
7、管道介绍一下，无名和有名的说了一下，高级管道具体细节忘记了
8、堆栈都放些什么
9、如何确定无符号数的二进制中1的个数。。。。（n&n-1）

#include <stdint.h>

int count1(uint32_t x){
    int count=0;
    while(x){
        if(x&0x1)
            ++count;
        x=(x>>1);
    }
    return count;
}

10、口头描述了一个struct，一个char和一个int的成员，占多少空间
11、没有反问环节。。。

有木有发现我被问到的都是这几天大家被问到过的！！！！

作者：真不想丢人啊
链接：https://www.nowcoder.com/discuss/442982?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

完全二叉树
哈夫曼编码

二面
自我介绍，项目，课程，家乡，爱好，语言使用情况。
最后问了一下是不是没面试了，面试官亲切的回答，对，等着就行了😑ok我是一棵白菜🤔

作者：201908231929463
链接：https://www.nowcoder.com/discuss/442951?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

6.22
自我介绍
问define和inline哪个好
静态变量和局部变量
虚基类
项目问几下
反问
结束
7.2
时隔十天进行了二面，问下项目没有深问，就业地域选择，兴趣爱好，最大的缺点，结束。
项目太水，面试官有一面的记录，应该是备胎了。
1.自我介绍
2.专业
3.简单的项目了解
4.中断机制（答得马马虎虎），上下文（不会）
5.TCP滑动窗口
6.TCP拥塞控制
7.static关键字
8.检测链表中是否有环
9.还有什么问题

分享一波在牛客上收集到的二轮技术面的算法和智力题：

3.数组里01序列，可以填充K个，问填充后最长的连续1的个数。先说思路再本地IDE写。
9、如何确定无符号数的二进制中1的个数。。。。（n&n-1）
算法题：

1 爬楼梯 LeetCode 70

class Solution {
    
    public int climbStairs(int n) {
        int[]  f = new int[n+1];
        if(n == 1) return 1;
        f[1] = 1;
        f[2] = 2;
        for(int i=3; i<=n;i++){
            f[i] = f[i-1] + f[i-2];
        }
        return f[n];
    }
    
    
}

2 二叉树最长同值路径 LeetCode 687

class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        int res = 0;
        if (root) helper(root, root->val, res);
        return res;
    }
    int helper(TreeNode* node, int parent, int& res) {
        if (!node) return 0;
        int left = helper(node->left, node->val, res);
        int right = helper(node->right, node->val, res);
        res = max(res, left + right);
        if (node->val == parent) return max(left, right) + 1;
        return 0;
    }
};

3 路径总和 leetcode 112 113 437

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null && root.right == null && sum == root.val) return true;
        return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        DFS(root,sum,res,path);
        return res;
    }
    public void DFS(TreeNode root, int sum,List<List<Integer>> res,List<Integer> path) {
       if(root == null) return;
        path.add(root.val);
        if(root.left == null&&root.right==null&&sum == root.val){
            res.add(new ArrayList<>(path));
            path.remove(path.size()-1);
            return;
        }
        DFS(root.left, sum-root.val,res,path);
        
        DFS(root.right, sum-root.val,res,path);
        path.remove(path.size()-1);
       
    }
}

4 扔鸡蛋，100层楼，2个鸡蛋，找出最坏情况下的扔的次数 leetcode 887

这道题归纳法求出二元一次方程即可

5 一个文件存储着8位数的电话号码，求不同电话号码的个数

思路是bitmap

6 一排座位有人为1，空为0，求离最近人的最远距离 leetcode849

7 最大连续1的个数 III leetcode 1004

 public int longestOnes(int[] A, int K) {
        int i = 0, j;
        for (j = 0; j < A.length; ++j) {
            if (A[j] == 0) K--;
            if (K < 0 && A[i++] == 0) K++;
        }
        return j - i;
    }

8 二叉树的最近公共祖先 leetcode 236

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q==root) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left!=null && right!=null) return root;
        return left!=null ? left : right;
        
    }
}

二叉搜索树的最近公共祖先 leetcode 235

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val < Math.min(p.val,q.val)){
            return lowestCommonAncestor(root.right, p, q);
        }else if(root.val > Math.max(p.val,q.val)){
            return lowestCommonAncestor(root.left, p, q);
        }else {
            return root;
        }
    }
}

9 给你一个整数n，怎么用一行代码判断是不是3的幂次方

10 生成1000个1000以内的随机整数，排序后去重

11 找出一个字符串所有连续子串中字典排序最大的子串 leetcode 1163

要求字典序最大的子串，那么一定是该字符串的一个后缀子串，因为如果是中间的一个字串的话，那么只要向它后面添加字母，它的字典序一定会更大。从前往后遍历，遇到更大的字符交换指针。遇到相同的字符，先比较它后面的一个字符是否是一样的，一样的就continue，直到不一样或者到头了，再进行下一位的比较。

题目结果一定是最大字母到结尾的字符串。
使用双指针进行遍历，对比双指针向右偏移x的字母，直到 s[i+x] != s[j+x]。
若s[i+x] < s[j+x]则将i指向j的位置，直至到最后一个字符，s.substring(i)即为所求答案。

 string lastSubstring(string s) {
        int st = 0;
        int len = s.size();
        for(int i = 1; i < len; i++) {
            int sz = 0;
            while(i+sz < len && s[st + sz] == s[i + sz]) {
                sz++;
            }
            if(s[i + sz] > s[st + sz]) st = i;
            if(i+sz == len) break;
        }
        return s.substr(st);
    }

12 反转句子里面的单词 leetcode 151 双指针法

class Solution {
    public String reverseWords(String s) {
        String[] words = s.trim().split(" +");
        Collections.reverse(Arrays.asList(words));
        return String.join(" ",words);
    }
}

13 字典序第K小的数字 leetcode 440

class Solution {
public:
    int findKthNumber(int n, int k) {
        int cur = 1;
        --k;
        while (k > 0) {
            long long step = 0, first = cur, last = cur + 1;
            while (first <= n) {
                step += min((long long)n + 1, last) - first;
                first *= 10;
                last *= 10;
            }
            if (step <= k) {
                ++cur;
                k -= step;
            } else {
                cur *= 10;
                --k; 
            }
        }
        return cur;
    }
};

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> res(n);
        int cur = 1;
        for (int i = 0; i < n; ++i) {
            res[i] = cur;
            if (cur * 10 <= n) {
                cur *= 10;
            } else {
                if (cur >= n) cur /= 10;
                cur += 1;
                while (cur % 10 == 0) cur /= 10;
            }
        }
        return res;
    }
};

14 二维数组中的查找剑指offer 04

15 和相同的二元子数组 leetcode 930

class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int res = 0, sum = 0, left = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            sum += A[i];
            while (left < i && sum > S) sum -= A[left++];
            if (sum < S) continue;
            if (sum == S) ++res;
            for (int j = left; j < i && A[j] == 0; ++j) {
                ++res;
            }
        }
        return res;
    }
};

16 求第K大的数字

例如剑指offer54 leetcode 215 快速选择算法

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left = 0,right = nums.length-1;
        while(true){
            int pos = partition(nums,left,right);
            if(pos == k-1) return nums[pos];
            else if(pos>k-1){
                right = pos-1;
            }else{
                left = pos+1;
            }
        }
       
       
    }
    
   
    public int partition(int[] nums, int left,int right) {
         int temp = nums[left];
         while(left < right){
             while(left < right && nums[right]<=temp) right--;
             nums[left] = nums[right];
             while(left < right && nums[left]>=temp) left++;
             nums[right] = nums[left];
         }
         nums[left] = temp;
         return left;
        
    }
}

17 括号匹配 leetcode 22

18 链表找交点 leetcode 160

智力题：

1 公交车（房间）能装多少个乒乓球

公交车 12m×2.5m×3m 乒乓球直径40mm

房间 2.8m×2.5m×3m

2 老鼠找毒药问题

3 rand5 生成rand7函数
http://www.nowamagic.net/librarys/veda/detail/2172

4 抛硬币吃苹果（等比数列求和）

5 称天平

6 25匹赛马选最快前3匹的最少方法
笔试题：25匹马，找出最快的3匹，但是只有5个赛道，每次比赛只能得到5匹马的速度排序，那么最少需要多少次比赛
答案：7

分析：
1-5 场：

将25匹马分为5组，每组5匹，得到下面的排序，每组最快的马在左侧，即X1、X6、X11、X16、X21分别是每组中最快的。

组1：X1 X2 X3 X4 X5
组2：X6 X7 X8 X9 X10
组3：X11 X12 X13 X14 X15
组4：X16 X17 X18 X19 X20
组5：X21 X22 X23 X24 X25

但是，现在还不能说最快的3匹马在X1、X6、X11、X16、X21中，因为有可能最快的3匹马全部分在第一组中，即有可能出现X2比X6快。

但是我们肯定可以知道，每组的最后2名肯定不会是最快的3匹马，那么排除X4、X5；X9、X10；X14、X15；X19、X20；X24、X25；

第6场：

X1 X2 X3
X6 X7 X8
X11 X12 X13
X16 X17 X18
X21 X22 X23

参赛的为每组的第1名：X1、X6、X11、X16、X21，假设速度排序为X1、X6、X11、X16、X21。

那么我们可以知道，X16、X21及其后面的X17、X18；X22、X23均不可能是最快的3匹马。

第7场：

X1 X2 X3
X6 X7 X8
X11 X12 X13

目前，我们可以知道，X1是25匹马中最快的，但是X2、X6、X3、X7、X11之间的速度还不确定，需要再一次比赛，而X8、X12、X13不可能是最快的前3名。

参赛的为：X2、X6、X3、X7、X11，速度最快的2匹加上X1构成最快的3匹马。

因此一共需要7次比赛。
7 五个洞捉狐狸

五个洞从左到右排成一排，按顺序分别是12345号，其中有一个洞里有一只狐狸。每天晚上，狐狸都会跳到一个相邻的洞里，每个白天，你只能允许检查其中的一个洞，要求在一个星期以内确保狐狸被抓住，请问应该用什么方法来检查洞
1234234的顺序检查
下面是如果第一天狐狸在奇数洞
1抓到
32抓到
343抓到
3454抓到
543抓到
5454抓到
可以看到在第一天在奇数洞一定被抓到，如果没找到必然第五天在偶数洞，那么从第五天排列

2抓到
43抓到
454抓到

8 有100盏灯，只有开关两种状态。开始都是关着的状态，然后有100个人，第一个人把100盏灯的开关都拨一遍，第二个人，拨第2,4,6,8…盏灯的开关，第三个人拨第3,6,9,12…盏灯的开关，后面的人依此类推，问最后哪些灯是亮着的，哪些灯是灭了的。

9 蜡烛（绳子）燃烧问题：两根蜡烛，燃烧完都需要1小时，怎么确定15分钟是多久？
2根香为A和B

1 将A的两端，B的一端3个端点同时点燃；

2 A燃尽时开始计时并将B的另一端点燃；得15分钟

持续更新中……

作者：求份offer压压惊
链接：https://www.nowcoder.com/discuss/443391?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

在看到各位大佬陆续收到HR面通知，预感到自己已凉，在此分享一下一面、二面凉经。

6.22 二面：

面试官开门见山，说二面考察逻辑和算法能力，一共问了我3道题，第一道是逻辑题，后两道是算法题。最后一道题让我编程实现。

1.有100盏灯，只有开关两种状态。开始都是关着的状态，然后有100个人，第一个人把100盏灯的开关都拨一遍，第二个人，拨第2,4,6,8…盏灯的开关，第三个人拨第3,6,9,12…盏灯的开关，后面的人依此类推，问最后哪些灯是亮着的，哪些灯是灭了的。
有编号1~100个灯泡，起初所有的灯都是灭的。有100个同学来按灯泡开关，如果灯是亮的，那么按过开关之后，灯会灭掉。如果灯是灭的，按过开关之后灯会亮。

现在开始按开关。

第1个同学，把所有的灯泡开关都按一次(按开关灯的编号： 1,2,3,…100)。
第2个同学，隔一个灯按一次(按开关灯的编号： 2,4,6,…,100)。
第3个同学，隔两个灯按一次(按开关灯的编号： 3,6,9,…,99)。
…

问题是，在第100个同学按过之后，有多少盏灯是亮着的？

这个问题有一个数学上的解决方法。可以看出，被按了奇数次的灯泡应该是亮着的，被按了偶数次的灯泡应该是灭的。那么什么样的灯泡被按了奇数次？什么样的灯泡又被按了偶数次呢？从按的过程可以发现，如果一个灯泡的编号具有偶数个因子，那么该灯泡就被按了偶数次，反之按了奇数次。现在的问题又变成，什么样的编号具有奇数个因子，什么样的编号具有偶数个因子？这涉及到一个叫做质因数分解的定理，大概的意思是说，任何正数都能被唯一表示成多个质因数幂次乘积的方式。

例如:

14=27
50=25^2
…
100=2^2*52

也就是N=(p[1]^e[1])*(p[2]e[2])…(p[k]^e[k])，其中p[i]是质数，e[i]是p[i]的幂次。而由这个公式我们又可以导出一个数有多少个因子的计算公式:FactorNumber(N)=(e[1]+1)(e[2]+1)…*(e[k]+1)。

那么什么条件下满足FactorNumber(N)是奇数呢？显然必须所有的e[1],e[2],…,e[k]都必须是偶数，这样才能保证e[i]+1是奇数，结果乘积才能是奇数。而由于e[1],e[2],…,e[k]都是偶数,那么N一定是一个完全平方数(因为sqrt(N)=(p[1]^{(e[1]/2))*(p[2]}(e[2]/2))…(p[k]^(e[k]/2))是整数) 。回到按灯泡的问题上来，1~100中完全平方数有1,4,9,16,25,36,49,64,81,100这10个数，也就是说最后只有编号为这10个数的灯是亮着的。

2.生成1000个1000以内的随机整数，排序后去重。

链接：https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0
来源：牛客网

#include <iostream>
using namespace std;
int main() {
    int N, n;
    while (cin >> N) {
        int a[1001] = { 0 };
        while (N--) {
            cin >> n;
            a[n] = 1;
        }
        for (int i = 0; i < 1001; i++)
            if (a[i])
                cout << i << endl;
    }
    return 0;
}

链接：https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0
来源：牛客网

import java.util.Scanner;
import java.util.TreeSet;
 
public class Main
{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
             
            TreeSet<Integer> set=new TreeSet<Integer>();
            int n=sc.nextInt();
            if(n>0){
                for(int i=0;i<n;i++){
                    set.add(sc.nextInt());
                }
            }
            for(Integer i:set){
                System.out.println(i);
            }
        }
    }
}

3.找出一个字符串所有连续子串中字典排序最大的子串。

感觉算法题都很简单但当时没想出最优解法。应该是凉了。我的TP-LINK应聘之旅应该是到此为止了。

作者：早日上岸♡
链接：https://www.nowcoder.com/discuss/445284?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

注意:最好等在电脑前，一发面试链接立马进入会议室，不要相信面试链接里面的面试时间，我就是因为相信了面试链接里的时间，被面试官说迟到好久，面试官当时很不爽，导致问的问题都没咋听我说
1.自我介绍
2.介绍研究方向
3.你知道哪些数据结构
4.多线程了解吗
5.你接触了哪些技术栈
6.1kk url求访问频率最高的k个链接
https://blog.csdn.net/v_july_v/article/details/7382693
大概就是这些了，最后让我反问，我说还有下一面吗，他说技术最后一面，后面还有hr面，一周内知道结果

许愿许愿，希望有offer！

作者：许浩Forwards
链接：https://www.nowcoder.com/discuss/444670?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

作者：牛客205589245号
链接：https://www.nowcoder.com/discuss/444349?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

6/28 早上九点（面试官迟到6分钟，第二个面试官在开始十多分钟后到的，没问问题）
在这里插入图片描述

智力题：

两个人轮流抛硬币吃苹果，求概率

两个人轮流抛硬币，规定第一个抛出正面的人可以吃到苹果，请问先抛的人能吃到苹果的概率多大？
在这里插入图片描述

在这里插入图片描述

1000瓶毒酒，至少几只老鼠喝能找出
题目：

某酒主人要宴请客人，他共有1000瓶酒，其中1瓶有毒。一旦喝了毒酒后，会在一周后发作，现在如果我们用试纸进行检测，滴了毒酒

的试纸会在1周后变色，问最少需要多少张试纸可以检测出哪瓶有毒？

解答：

10张试纸即可。

10张试纸按从左到右的顺序一字排好，每瓶酒也编上号1到1000，并把编号转换成10位二进制形式，数位和试纸的位置一一对应，把

酒滴到酒二进制编号数相应位置上是1的试纸上（每一瓶酒都要滴）。一周后看变色的试纸有哪几张，然后排成二进制，再转成十进制

就是第几瓶酒。比如：第70瓶酒，70转换成二进制为0001000110，那么就滴到第4、8、9张试纸上。如果最后第3、7、8张试纸变

色，那么就是0010001100，转换成十进制就是140，即140瓶酒有毒。因此理论上用10张试纸可以检测1024瓶酒中哪一瓶酒有毒。

编程：
3. 括号匹配

作者：改过自新失败的菜鸟
链接：https://www.nowcoder.com/discuss/441816?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

作者：现实理想青年
链接：https://www.nowcoder.com/discuss/441975?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

、
最后撸一个16进制字符串转数字，太紧张，时间内没写出来😢😢😢
————————————
————————————

作者：吊车尾的探索士
链接：https://www.nowcoder.com/discuss/442039?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

用Java怎么写个单例模式我说我不太熟悉Java 用C++说的

public class Singleton {

    //volatile保证，当uniqueInstance变量被初始化成Singleton实例时，多个线程可以正确处理uniqueInstance变量
    private volatile static Singleton uniqueInstance;
    private Singleton() {
    }
    public static Singleton getInstance() {
       //检查实例，如果不存在，就进入同步代码块
        if (uniqueInstance == null) {
            //只有第一次才彻底执行这里的代码
            synchronized(Singleton.class) {
               //进入同步代码块后，再检查一次，如果仍是null，才创建实例
                if (uniqueInstance == null) {
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

如何判断链表有环
如何找出环入口？如何证明你的算法（只知道算法，能手撕，但不会证明，瞎扯的）
从 head 到入口点的距离设为 x，入口点到相遇点的距离设为 y，环的的长度设为 n。

假设 slow 指针走过的距离为 t，那么 fast 指针走过的一定是 slow 指针的 2 倍，也就是 2t。

slow 指针从 head 出发走了 x 的距离到达入口点，然后可能走了 k1 圈，然后再次回到入口点，再走了 y 的距离到达相遇点和 fast 指针相遇。

t = x + k1 * n + y

fast 指针同理，fast 指针从 head 出发走了 x 的距离到达入口点，然后可能走了 k2 圈，然后再次回到入口点，再走了 y 的距离到达相遇点和 slow 指针相遇。

2t = x + k2 * n + y

上边两个等式做一个差，可以得到

t = (k2 - k1) * n

设 k = k2 - k1 ，那么 t = k * n。

把 t = k * n 代入到第一个式子 t = x + k1 * n + y 中。

k * n = x + k1 * n + y

移项，x = (k - k1) * n - y

取出一个 n 和 y 结合，x = (k - k1 - 1) * n + (n - y)

左边的含义就是从 head 到达入口点。

右边的含义， n - y 就是从相遇点到入口点的距离，(k - k1 - 1) * n 就是转 (k - k1 - 1) 圈。

左边右边的含义结合起来就是，从相遇点走到入口点，然后转 (k - k1 - 1) 圈后再次回到入口点的这段时间，刚好就等于从 head 走向入口点的时间。

所以代码的话，我们只需要 meet 指针从相遇点出发的同时，让 head 指针也出发， head 指针和 meet 指针相遇的位置就是入口点了。
昨天下午进行一面 20mins
面试内容主要是为了很多项目上的东西
另外问了
（1）堆和栈的区别
（2）描述快排算法

作者：新垣结衣的男朋友
链接：https://www.nowcoder.com/discuss/390057?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

说一下平衡二叉查找树，插入和删除的时间复杂度是多少

https://blog.csdn.net/keda8997110/article/details/45057081

怎么判断一棵树的高度，我说的dfs，又问树如果很高怎么办，递归次数过多会出现什么问题
判断链表是否有环
怎么用两个栈实现队列，扣细节
最后问了一下在校期间成绩怎么样

作者：Scout_N
链接：https://www.nowcoder.com/discuss/441965?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post
来源：牛客网

岗位：IT软件开发
项目：Java做的一个存储项目
第一个问题：关于微服务化的基本理解，想到哪讲到哪；
第二个问题：spring的bean加载机制；根据印象说了点；
Bean容器找到配置文件中 Spring Bean 的定义。
Bean容器利用Java Reflection API创建一个Bean的实例。
如果涉及到一些属性值利用set方法设置一些属性值。
如果Bean实现了BeanNameAware接口，调用setBeanName()方法，传入Bean的名字。
如果Bean实现了BeanClassLoaderAware接口，调用setBeanClassLoader()方法，传入ClassLoader对象的实例。
如果Bean实现了BeanFactoryAware接口，调用setBeanFactory()方法，传入BeanFactory对象的实例。
与上面的类似，如果实现了其他*Aware接口，就调用相应的方法。
如果有和加载这个Bean的Spring容器相关的BeanPostProcessor对象，执行postProcessBeforeInitialization()方法
如果Bean实现了InitializingBean接口，执行afterPropertiesSet()方法。
如果Bean在配置文件中的定义包含init-method属性，执行指定的方法。
如果有和加载这个Bean的Spring容器相关的BeanPostProcessor对象，执行postProcessAfterInitialization()方法
当要销毁Bean的时候，如果Bean实现了DisposableBean接口，执行destroy()方法。
当要销毁Bean的时候，如果Bean在配置文件中的定义包含destroy-method属性，执行指定的方法。

第三个问题：cookie和session的生命周期；讲了cookie和session是什么，生命周期以前没了解过，虽然很简单；

https://blog.csdn.net/shuaishenkkk/article/details/8634917

剩下的就很无聊的一些问题了，面后台开发，面试官不是做Java的，不提问项目的，我感觉面的有些心累

进程间通信方式、

平时用哪些数据结构比较多、
什么情况下会用到树

介绍完全二叉树（…？…）

一、满二叉树

一棵二叉树的结点要么是叶子结点，要么它有两个子结点（如果一个二叉树的层数为K，且结点总数是(2^k) -1，则它就是满二叉树。）
　　二、完全二叉树

若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。