红黑树的时间复杂度是多少_红黑树查询时间复杂度

最新腾讯面试题汇总–C++后端开发岗（部分含答案） 　　阻塞、非阻塞、同步、异步 的区别 　　阻塞 阻塞调用是指调用结果返回之前，当前线程会被挂起（线程进入非可执行状态，在这个状态下，cpu 不会给线程分配时间片，即线程暂停运行）。函数只有在得到结果之后才会返回。对于同步调用来说，很多时候当前线程还是激活的，只是从逻辑上当前函数没有返回而已。 就是调用我（函数），我（函数）没有接收完数据或者没有得到结果之前，我不会返回。非阻塞 指在不能立刻得到结果之前，该函数不会阻塞当前线程，而会立刻返回。就是调用我（函数），我（函数）立即返回，通过 select 通知调用者同步 IO同步 IO 进行 IO 操作时会阻塞进程。IO 操作分两个阶段（数据准备和拷贝数据），阻塞 IO 是这两步都阻塞，非阻塞 IO 是数据准备阶段，不会阻塞进程。数据准备完成后，进程主动在此调用 recvfrom 函数将数据从内核拷贝到用户内存异步IO相当于用户进程将 IO 操作整个交给内核去完成，内核会返回事件完成通知。在此阶段，用户进程不需要检查 IO 操作状态，也不需要主动拷贝数据，用户进程完全没有阻塞 　　数据库 ACID 一致性和原子性的区别 　　ACID特性，原子性、一致性、隔离性、持久性原子性 是指事务是一个不可再分割的工作单位，事务中的操作要么都发生，要么都不发生。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样一致性一致性是指事务使得系统从一个一致的状态转换到另一个一致状态。这是说数据库事务不能破坏关系数据的完整性以及业务逻辑上的一致性隔离性多个事务并发访问时，事务之间是隔离的，一个事务不应该影响其它事务运行效果。这指的是在并发环境中，当不同的事务同时操纵相同的数据时，每个事务都有各自的完整数据空间。由并发事务所做的修改必须与任何其他并发事务所做的修改隔离持久性持久性，意味着在事务完成以后，该事务所对数据库所作的更改便持久的保存在数据库之中，并不会被回滚。即使出现了任何事故比如断电等，事务一旦提交，则持久化保存在数据库中 　　Mysql如何保证事务的ACID特性 　　详细1 详细2原子性 undolog记录反向操作，用于回滚： 对于每一个insert，undolog记录一个delete 对于每一个delete，undolog记录一个insert 对于每一个update，undolog记录一个相反的update一致性 redolog+undolog ，保证所有操作同时提交和回滚。 通过加锁保证同一行数据更新串行，避免提交丢失。 通过MVCC保证事务内读一致性。 加锁参考隔离性 通过隔离模式实现不同级别下的隔离性。 通过锁和MVCC实现隔离模式下的读写并行。 [四种隔离模式]https://success.blog.csdn.net/article/details/ [加锁原理]https://success.blog.csdn.net/article/details/持久性 通过redolog实现持久性。 sync_binlog和innodb_flush_log_at_trx_commi设置为1，也就是大家常说的双1策略，保证宕机数据不丢失。 宕机重启时通过对比redolog页和数据页的LSN（Log Sequence Number）进行恢复 　　常见排序算法，说下快排过程，时间复杂度 　　

　　有N个节点的满二叉树的高度 　　1+logN 　　单点最短路的方法，时间复杂度 　　如何实现关键字输入提示，使用字典树，复杂度多少，有没有其他方案，答哈希，如果是中文呢，分词后建立字典树 　　红黑树的结构，查询性能 　　死锁是怎么产生的 　　线程和进程的区别 　　进程的通信方式 　　CPU的执行方式 　　代码中遇到进程阻塞，进程僵死，内存泄漏等情况怎么排查。通过ps查询状态，分析dump文件等方式排查 　　Linux了解么，查看进程状态ps，查看cpu状态 top。查看占用端口的进程号netstat grep 　　10g文件，只有2g内存，怎么查找文件中指定的字符串出现位置。MapReduce分割文件处理，他说可以用cat | grep 管道处理 　　Linux的swap了解么 　　MySQL的存储引擎，有什么区别 　　100w个数，怎么找到前1000个最大的，堆排序，怎么构造，怎么调整，时间复杂度 　　一个矩阵，从左上角到右下角，每个位置有一个权值。可以上下左右走，到达右下角的路径权值最小怎么走 　　四辆小车，每辆车加满油可以走一公里，问怎么能让一辆小车走最远 　　MySQL的索引，B+树性质 　　Linux的cpu 100怎么排查，top jstack，日志，gui工具 　　Linux大文件怎么查某一行的内容 　　十亿个数的集合和10w个数的集合，如何求它们的交集 （集合的数字不重复） 　　十亿和数找到前100个最大的，堆排序 　　TCP和UDP的区别，具体使用场景呢 　　TCP四次挥手讲一下过程 　　对于socket编程，accept方法是干什么的，在三次握手中属于第几次 　　对于单例模式，有什么使用场景了，讲了全局id生成器，他问我分布式id生成器怎么实现 　　除了单例模式，知道适配器模式怎么实现么，有什么用 　　proc文件系统 　　TCP和UDP的核心区别在哪，讲了滑动窗口保证可靠有序传输，UDP不可靠。TCP需要连接而UDP不需要 　　TCP的四次挥手，time wait状态有什么意义 　　map 和 set 底层是用什么数据结构实现？用 set 实现 map？（set<pair<key, value>>） 　　递归调用函数占用了什么空间 　　栈空间 实际上堆空间也有可能占用 　　函数栈空间多大 　　函数传参时int &会减少占用的空间吗，有好处吗 　　基础类型(不会) 感觉从内存上讲没好处，看需求把，是否需要改那个数。 　　引用占不占内存 　　1，引用实际是通过指针实现的。 2，引用是一个常量指针。 3，引用在内存中占4个字节。 4，在对引用定义时，需要对这个常量指针初始化。 5，因为在在表达式中，使用引用实际上就像使用变量本身一样，所以直接用sizeof是得不到引用本身的大小的。 　　HTTP协议 　　简单介绍，协议细节和包含了什么请求报文 请求行 请求方法 URL 版本协议 请求头部 请求数据响应报文状态行 版本协议 状态码 状态码描述 响应头部 connection 响应正文 　　相关视频推荐 　　tcpip，accept，11个状态，细枝末节的秘密，还有哪些你不知道 　　10道网络八股文，每道都很经典，让你在面试中逼格满满 　　从50道腾讯面试题，分析腾讯c++后端工程的技能树 　　需要C/C++ Linux服务器架构师学习资料及大厂面试题加qun（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享



　　http常见状态码 　　http常见请求方法 （get,post, push） 　　STL常用的容器有哪些 　　讲一讲容器的内部实现，扩容缩容，存储 　　vector内存结构，扩容缩容 string扩容缩容，连续的 string是连续的 优先级队列，以vector为存储结构的堆 　　面向对象思想的特点 　　封装多态继承 　　哪些语言特性体现面向对象 　　多态 　　多态通过什么实现的 　　多态和重载区别 　　多态通过虚函数表实现 一个接口，根据调用的对象不同产生不同的结果重载通过参数列表的不同实现根据输入参数类型不同选择对应的函数重写和重载的区别重载是相同函数名，但函数的参数不能完全相同。重写是指派生类改写基类虚函数的函数体 　　虚函数继承机制与内部实现 　　类的大小 　　int成员+普通函数+虚函数 类大小是多少 sizeof 为 8 　　字节对齐的理解 　　为什么要字节对齐 怎么字节对齐 不对齐会怎么样 对齐与不对齐的访问内存区别 　　字节序 　　大端小端的区别小端(先存小的) 数值高位 放在内存低位 网络序(默认大端序) 字节序怎么转换 int的怎么实现 　　string有字节序的说法吗没有，字节序是指byte的排序，string里面都是char，一个char就是1字节 只要出现索引的地方，一定是索引越大地址越大 　　四次挥手 　　2msl 半连接状态 　　内存碎片分为哪几种 　　内碎片外碎片 　　有序数组中找是否有两个数和为N 　　Linux命令的使用，查看进程、查看资源占用、查看某一个进程的资源占用 　　进程、线程及协程及使用场景 　　多线程哪些东西是共享的 　　静态变量共享吗 虚拟内存地址的组织 　　tcp拥塞控制 　　慢启动和快重传的触发条件 怎么区分是网络的原因(连发3次ack说明丢包) 　　udp改可靠udp怎么做 　　对着tcp的可靠传输方法改 加ack 加序号 拥塞控制 　　stl标准库六大容器 　　vector内存 map的实现方式 　　共享内存 　　进程重启如何读到之前的东西(比如本来有个map，重启后继续读到) 共享内存可以实现的 　　设计一个算法 　　红包算法，3个人抢5块的红包，每个人不能超过2块先每人分2块，再加权取随机数按比例加权扣一 　　epoll两种模式的区别 　　LT 模式 当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序，应用程序可以不立即处理该事件。下次调用 epoll_wait 时，会再次响应应用程序并通知此事件。 一个 socket 第一次有数据，LT 模式下检测到 socket 处于活跃状态，接下来再有数据过来，接着触发。或者说可以根据需要收取部分数据，只要 socket 上数据不收取完，epoll_wait 会接着返回这个可读 socket。编程上如果需要数据包一部分一部分的处理，可以使用 LT 模式ET 模式 当 epoll_wait 检测到描述符事件发生并将此事件通知应用程序，应用程序必须立即处理该事件。如果不处理，下次调用 epoll_wait 时，不会再次响应应用程序并通知此事件。第一次有数据会触发 socket，第二次再有数据不会触发，必须等第一次的数据完全读完或写完。必须把当前 socket 数据全部收完，才能接受下一次的可读 socket编程上 ET 模式必须是一个循环，收取数据到 recv 返回-1，errno=EAGAINepoll 的 ET 模式为什么一定要使用非阻塞 IO ET 模式下每次 write 或 read 需要循环 write 或 read 直到返回 EAGAIN 错误。以读操作为例，这是因为 ET 模式只在 socket 描述符状态发生变化时才触发事件，如果不一次把 socket 内核缓冲区的数据读完，会导致 socket 内核缓冲区中即使还有一部分数据，该 socket 的可读事件也不会被触发。根据上面的讨论，若 ET 模式下使用阻塞 IO，则程序一定会阻塞在最后一次 write 或 read 操作，因此说 ET 模式下一定要使用非阻塞 IO 　　http://google.com屏蔽的原理是什么，隧道怎么实现的 　　隧道上网原理 　　进程调度 　　进程调度：记录系统中的所有进程的状态、优先级数和资源的需求情况确定调度算法，决定将 CPU 分配给哪个进程多少时间分配处理机给进程，进行 CPU 现场的保护和移交 　　进程调度算法：先来先服务调度算法、短作业优先调度算法、非抢占式优先级调度算法、抢占式优先级调度算法、高响应比优先调度算法、时间片轮转法调度算法 　　页面置换算法 　　详细先进先出页面置换算法（FIFO）及其改进这种算法的思想和队列是一样的，OS维护一个当前在内存中的所有页面的链表，最新进入的页面在尾部，最久的在头部，每当发生缺页中断，就替换掉表头的页面并且把新调入的页面加入到链表末尾。 一种合理的改进，称为第二次机会算法。即给每个页面增加一个R位，每次先从链表头开始查找，如果R置位，清除R位并且把该页面节点放到链表结尾；如果R是0，那么就是又老又没用到，替换掉最佳页面置换算法（OPT）最理想的状态下，我们给页面做个标记，挑选一个最远才会被再次用到的页面。当然，这样的算法不可能实现，因为不确定一个页面在何时会被用到。最近最久未使用（NRU）系统为每一个页面设置两个标志位：当页面被访问时设置R位，当页面（修改）被写入时设置M位。当发生缺页中断时，OS检查所有的页面，并根据它们当前的R和M位的值，分为四类： （1）!R&!M（2）!R&M（3）R&!M（4）R&M 编号越小的类，越被优先换出。即在最近的一个时钟滴答内，淘汰一个没有被访问但是已经被修改的页面，比淘汰一个被频繁使用但是“clean”的页面要好。最近最少使用置换算法（LRU）最近最少使用，简单来说就是将数据块中，每次使用过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据剔除掉这就是 LRU 算法 　　操作系统的CPU如何调度 　　同进程调度 　　介绍下epoll，基本使用，lt/et,什么时候文件描述符活跃，活跃后内核如何处理。和select有什么区别 　　介绍下tcp/ip四层协议 　　TCP/IP协议并不完全符合OSI 标准定制的七层参考模型，它采取了四层的层级结构网络接口层：接收IP数据包并进行传输，从网络上接收物理帧，抽取IP 转交给下一层，对实际网络的网络媒体的管理，定义如何使用物理网络 ，如以太网。 网际层IP: 负责提供基本的数据封包传送功能，让每一块数据包都能打到目的主机，但不检查是否被正确接收，主要表现为IP协议 传输层：在此层中，它提供了节点的数据传送，应用程序之间的通信服务，主要是数据格式化，数据确认和丢失重传等。主要协议包括TCP和UDP 应用层：应用程序间沟通单层，如万维网（WWW）、简单电子邮件传输(SMTP)、文件传输协议（FTP）、网络远程访问协议（Telnet）等 　　ping通过什么协议，在哪一层 　　Ping 是一个应用程序，是基于 ICMP 协议实现的。ICMP 协议是位于 IP 层的一个协议。它是 TCP/IP 协议族的一个子协议，用于在 IP 主机、路由器之间传递控制消息。 Ping 命令的基本原理？答：ICMP，发送主机发送 echo 请求，接受主机sigusoft echo 报文 Ping 的如果是域名，还要先经过 DNS 解析 　　介绍三次握手四次挥手，服务器能否不wait直接断开 　　time_wait 状态如何避免 首先服务器可以设置 SO_REUSEADDR 套接字选项来通知内核，如果端口忙，但 TCP 连接位于 TIME_WAIT 状态时可以重用端口。在一个非常有用的场景就是，如果你的服务器程序停止后想立即重启，而新的套接字依旧希望使用同一端口，此时 SO_REUSEADDR 选项就可以避免TIME_WAIT 状态 　　心跳包通过什么实现的，如何调节参数 　　因为要考虑到一个服务器通常会连接多个客户端，因此由用户在应用层自己实现心跳包，代码较多 且稍显复杂，而利用TCP／IP协议层为内置的KeepAlive功能来实现心跳功能则简单得多。 不论是服务端还是客户端，一方开启KeepAlive功能后，就会自动在规定时间内向对方发送心跳包， 而另一方在收到心跳包后就会自动sigusoft，以告诉对方我仍然在线。 因为开启KeepAlive功能需要消耗额外的宽带和流量，所以TCP协议层默认并不开启KeepAlive功 能，尽管这微不足道，但在按流量计费的环境下增加了费用，另一方面，KeepAlive设置不合理时可能会 因为短暂的网络波动而断开健康的TCP连接。并且，默认的KeepAlive超时需要7,200，000 MilliSeconds， 即2小时，探测次数为5次。对于很多服务端应用程序来说，2小时的空闲时间太长。因此，我们需要手工开启KeepAlive功能并设置合理的 KeepAlive参数 　　心跳包一般来说都是在逻辑层发送空的echo包来实现的。下一个定时器，在一定时间间隔下发送一个空包给客户端，然后客户端反馈一个同样的空包回来，服务器如果在一定时间内收不到客户端发送过来的反馈包，那就只有认定说掉线了 　　malloc如何实现的，通过哪个系统调用开辟内存，如何映射到物理内存 　　当分配内存小于 128K 时，brk 是将数据段(.data)的最高地址指针_edata 往高地址推当分配内存大于 128K 时，mmap 是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存 　　这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系 　　mysql，acid，mvcc，版本号加在哪，跨表怎么办 　　介绍下B+树，数据存在哪，数据具体存的哪些？ 　　死机了数据怎么恢复？有几种log形式？ 　　详细 持久性是指一个事务一旦被提交了，那么对数据库中的数据的改变就是永久性的，即便是在数据库系统遇到故障的情况下也不会丢失提交事务的操作。 MySQL采用了一种叫WAL（Write Ahead Logging）提前写日志的技术。意思就是说，发生了数据修改操作先写日志记录下来，等不忙的时候再持久化到磁盘。这里提到的日志就是redo log。 redo log称为重做日志，当有一条记录需要修改的时候，InnoDB引擎会先把这条记录写到redo log里面。redo log是物理格式日志，它记录的是对于每个页的修改。 redo log是由两部分组成的：一是内存中的重做日志缓冲（redo log buffer）;二是用来持久化的重做日志文件（redo log file）。为了消耗不必要的IO操作，事务再执行过程中产生的redo log首先会redo log buffer中，之后再统一存入redo log file刷盘进行持久化，这个动作称为fsync binlog记录了mysql执行更改了所有操作，但不包含select和show这类本对数据本身没有更改的操作。但是不是说对数据本身没有修改就不会记录binlog日志。binlog是mysql自带的，他会记录所有存储引擎的日志文件。而redo log是InnoDB特有的，他只记录该存储引擎产生的日志文件binlog是逻辑日志，记录这个语句具体操作了什么内容。Redo log是物理日志，记录的是每个页的更改情况redo log是循环写，只有那么大的空间。binlog采用追加写入，当一个binlog文件写到一定大小后会切换到下一个文件 　　线程池如何实现的？ 　　在应用程序启动之后，就马上创建一定数量的线程，放入空闲的队列中。这些线程都是处于阻塞状态，这些线程只占一点内存，不占用 CPU。当任务到来后，线程池将选择一个空闲的线程，将任务传入此线程中运行。当所有的线程都处在处理任务的时候，线程池将自动创建一定的数量的新线程，用于处理更多的任务。执行任务完成之后线程并不退出，而是继续在线程池中等待下一次任务。当大部分线程处于阻塞状态时，线程池将自动销毁一部分的线程，回收系统资源。 　　epoll想改成多线程的该怎么实现？ 　　单独单写设计阻塞队列，不用锁怎么实现？ 　　使用一个全局变量进行标志 　　std:move介绍下，什么是左值右值，传递个对象会什么样？连续执行两次move会怎么样 　　取地址的、有名字的就是左值。左值的生存期长，可以作为赋值的对象。 右值指临时对象，只在当前语句有效，右值又可以细分为纯右值、将亡值。纯右值指的是临时变量和不跟对象关联的字面量值；将亡值则是 C++11 新增的跟右值引用相关的表达式，这样表达式通常是将要被移动的对象（移为他用）。如std::move 的返回值。将亡值可以理解为通过“盗取”其他变量内存空间的方式到的值 　　std::move()将左值强制转换为右值。 　　智能指针介绍一下，unique如何防止多次释放 　　shared_ptr、unique_ptr、weak_ptr。shared_ptr多个指针指向相同的对象。shared_ptr 使用引用计数，每一个 shared_ptr 的拷贝都指向相同的内存。每使用他一次，内部的引用计数加 1，每析构一次，内部的引用计数减 1，减为 0 时，自动删除所指向的堆内存。shared_ptr 内部的引用计数是线程安全的，但是对象的读取需要加锁。 unique_ptr“唯一”拥有其所指对象，同一时刻只能有一个 unique_ptr 指向给定对象（通过禁用拷贝构造函数和赋值运算符、只有移动语义来实现）。 对象互相引用 当父类对象包含子类对象且子类对象包含父类对象，然二者又互相赋值的时候，将会发生互相引用的情况，资源将得不到释放。 弱指针 weak_ptr 不控制对象的生命期，指向一个shared_ptr 管理的对象，但是引用计数不在进行加 1。 它只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造。,然后赋值给它的构造和析构不会引起引用记数的增加或减少.防止两个 shares_ptr 互相引用使得释放时引用计数为 1，无法得到释放。不能通过 weak_ptr 直接访问对象的方法，需要先将 weak_ptr 转为shared_ptr，才可以。某个 weak_ptr 调用 lock()转变为 shared_ptr。也可以 weak..直接赋值给 shared… 　　map和unordered_map的区别 　　unordered_map 和 map 类似，都是存储的 key-value 的值，可以通过 key 快速索引到 value。不同的是 unordered_map 不会根据 key 的大小进行排序unordered_map 的底层实现是 hash_table，map 中的素是按照红黑树存储如果需要内部素自动排序，使用 map，不需要排序使用 unordered_map 　　介绍下deque 　　详细 　　双端队列（deque）是一种支持向两端高效地插入数据、支持随机访问的容器。和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域。为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址。也就是说，map 数组中存储的都是指针，指向那些真正用来存储数据的各个连续空间 　　当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。如果 map 数组满了怎么办？很简单，再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧的空间。 　　伙伴系统 　　Linux 内核中引入了伙伴系统算法(buddy system)。把所有的空闲页框分组为 11 个块链表，每个块链表分别包含大小为 1，2，4，8，16，32，64，128，256，512 和 1024 个连续页框的页框块。最大可以申请 1024 个连续页框，对应 4MB 大小的连续内存。每个页框块的第一个页框的物理地址是该块大小的整数倍。 　　假设要申请一个 256 个页框的块，先从 256 个页框的链表中查找空闲块，如果没有，就去 512 个页框的链表中找，找到了则将页框块分为 2 个 256 个页框的块，一个分配给应用，另外一个移到 256 个页框的链表中。如果 512 个页框的链表中仍没有空闲块，继续向 1024 个页框的链表查找，如果仍然没有，则返回错误。页框块在释放时，会主动将两个连续的页框块合并为一个较大的页框块。 　　linux查询进程的CPU占用，打开的端口号，TCP连接数量，内存使用情况 　　top, ps, lsof, netstat, df -h查看程序对应的进程号： ps -ef | grep 进程名字 查看进程号所占用的端口号： netstat -nltp | grep 进程号 查看端口号所使用的进程号: lsof -i:端口号 　　多线程是如何通信的 　　重载和重写 　　什么时候设置成虚函数 　　https加密过程 　　指针和引用的区别 　　new和malloc区别 　　智能指针(auto_ptr,shared_ptr区别) 　　线程同步，进程同步方法 　　说一下四次挥手，为什么要有time-wait 　　分配内存的时候操作系统做了什么事情 　　epoll和select的区别 　　epoll的源代码读过吗？描述一下其中的数据结构 　　epoll发展于介绍 epoll中就绪列表引用着就绪的socket，所以它应能够快速的插入数据。程序可能随时调用epoll_ctl添加监视socket，也可能随时删除。当删除时，若该socket已经存放在就绪列表中，它也应该被移除。所以就绪列表应是一种能够快速插入和删除的数据结构。双向链表就是这样一种数据结构，epoll使用双向链表来实现就绪队列。 既然epoll将“维护监视队列”和“进程阻塞”分离，也意味着需要有个数据结构来保存监视的socket。至少要方便的添加和移除，还要便于搜索，以避免重复添加。红黑树是一种自平衡二叉查找树，搜索、插入和删除时间复杂度都是O(log(N))，效率较好。epoll使用了红黑树作为索引结构 　　如果epoll_wait函数中定时了3秒，有事情和没事情返回接口会发生什么？ 　　学校局域网到公共网时路由器是怎么变化的 　　一个阻塞的io进程是如何被调度的？（操作系统会一直等待吗？还是会定时去拉一把？ 　　IO 准备好 / Sleep 时间到 前不会调度该线程 　　tcpdump抓包 　　IO复用（select/poll/epoll）区别 　　非关系型数据库和关系型数据库区别 　　分布式事务 　　Git 　　git，新建一个分支、比较两个分支差异、合并分支 　　kill -9 与 kill -5的差别 　　linux：找一个文件夹下带某一个关键字的文件 　　TCP 和 UDP 区别? 　　TCP 是怎么保障可靠性的 　　三次握手四次挥手过程 　　信号量与信号的区别和应用场景？ 　　什么是中断？什么是陷入？ 　　中断是指计算机运行过程中，出现某些意外情况需主机干预时，机器能自动停止正在运行的程序并转入处理新情况的程序，处理完毕后又返回原被暂停的程序继续运行.硬件中断软件中断 是一条CPU指令，用以自陷一个中断。由于软中断指令通常要运行一个切换CPU至内核态（Kernel Mode/Ring 0）的子例程，它常被用作实现系统调用（System call）中断处理流程 1、设备发出中断信号 2、硬件通过 PSW 和 PC 保存现场，保存在堆栈中 3、根据中断码查找中断向量表 4、把中断处理程序入口地址推送给寄存器 5、执行中断处理程序 6、回到之前断点继续运行 　　字节码层面如何体现多态 　　缓存穿透，缓存雪崩，缓存击穿，缓存过期策略 　　缓存穿透缓存穿透是指缓存和数据库中都没有的数据，而用户不断发起请求，如发起为id为“-1”的数据或id为特别大且不存在的数据。这时的用户很可能是攻击者，攻击会导致数据库压力过大。 解决方案：接口层增加校验，如用户鉴权校验，id做基础校验，id<=0的直接拦截； 从缓存取不到的数据，在数据库中也没有取到，这时也可以将key-value对写为key-null，缓存有效时间可以设置短点，如30秒（设置太长会导致正常情况也没法使用）。这样可以防止攻击用户反复用同一个id暴力攻击缓存击穿缓存击穿是指缓存中没有但数据库中有的数据（一般是缓存时间到期），这时由于并发用户特别多，同时读缓存没读到数据，又同时去数据库去取数据，引起数据库压力瞬间增大，造成过大压力 解决方案： 设置热点数据永远不过期 加互斥锁降低从数据库中读取数据频率缓存雪崩缓存雪崩是指缓存中数据大批量到过期时间，而查询数据量巨大，引起数据库压力过大甚至down机。和缓存击穿不同的是，缓存击穿指并发查同一条数据，缓存雪崩是不同数据都过期了，很多数据都查不到从而查数据库 解决方案：缓存数据的过期时间设置随机，防止同一时间大量数据过期现象发生。如果缓存数据库是分布式部署，将热点数据均匀分布在不同搞得缓存数据库中。设置热点数据永远不过期。 　　缓存与数据库的一致性 　　对内存泄漏的理解，以及在项目中如何排查解决 　　内存泄漏是指由于疏忽或错误造成了程序未能释放掉不再使用的内存的情况。内存泄漏并非指内存在物理上消失，而是应用程序分配某段内存后，由于设计错误，失去了对该段内存的控制。 　　检查方法：在 main 函数最后面一行，加上一句_CrtDumpMemoryLeaks()。调试程序，自然关闭程序让其退出，查看输出： 输出这样的格式{453}normal block at 0x02432CA8,868 bytes long 被{}包围的 453 就是我们需要的内存泄漏定位值，868 bytes long 就是说这个地方有 868 比特内存没有释放。 定位代码位置 在 main 函数第一行加上_CrtSetBreakAlloc(453);意思就是在申请 453这块内存的位置中断。然后调试程序，程序中断了，查看调用堆栈。加上头文件#include <crtdbg.h> 　　大数据量分库分表方式，作用 　　数据库灾备方案 　　vector如何实现线程安全 　　自旋锁 　　输入url后发生了什么（详细介绍整个过程） 　　纯虚函数与虚函数的区别 　　MySQL索引、联合索引、联合索引应用特点 　　explain sql语句（我回答的是possible_keys、key、type等） 　　TCP三次握手、DNS负载均衡、长短连接 　　设计模型（口述下工厂、单例的写法） 　　查一个文件中含有某个关键字的行数 　　mysql中的视图 　　改变一个视图其它事务能看到吗 　　mysql为什么用b+树 　　线程如何调度 　　多路复用 　　消息队列 　　1.什么是消息队列 2.如何保证消息不丢失 3.如何保证消息不重复 　　如何保证线程安全 　　B+树索引说说 　　MySQL半同步复制过程 　　详细异步复制（Asynchronous replication） MySQL默认的复制即是异步的，主库在执行完客户端提交的事务后会立即将结果返给给客户端，并不关心从库是否已经接收并处理，这样就会有一个问题，主如果crash掉了，此时主上已经提交的事务可能并没有传到从上，如果此时，强行将从提升为主，可能导致新主上的数据不完整。全同步复制（Fully synchronous replication） 指当主库执行完一个事务，所有的从库都执行了该事务才返回给客户端。因为需要等待所有从库执行完该事务才能返回，所以全同步复制的性能必然会收到严重的影响。半同步复制（Semisynchronous replication） 介于异步复制和全同步复制之间，主库在执行完客户端提交的事务后不是立刻返回给客户端，而是等待至少一个从库接收到并写到relay log中才返回给客户端。相对于异步复制，半同步复制提高了数据的安全性，同时它也造成了一定程度的延迟，这个延迟最少是一个TCP/IP往返的时间。所以，半同步复制最好在低延时的网络中使用。 　　HTTPS握手过程（是SSL的握手） 　　HTTPs 是以安全为目标的 HTTP 通道，简单讲是 HTTP 的安全版，即HTTP 下加入 SSL 层，HTTPS 的安全基础是 SSL，因此加密的详细内容就需要 SSL HTTPs的握手过程包含五步浏览器请求连接服务器返回证书：证书里面包含了网站地址，加密公钥，以及证书的颁发机构等信息，服务器采用非对称加密算法（RSA）生成两个秘钥，私钥自己保留浏览器收到证书后作以下工作： 3.1 验证证书的合法性 3.2 生成随机（对称）密码，取出证书中提供的公钥对随机密码加密；浏览器即客户端使用非对称加密来加密对称加密规则，对称加密用于加密后续传输的信息 3.3 将之前生成的加密随机密码等信息发送给网站服务器收到消息后作以下的操作 4.1 使用自己的私钥解密浏览器用公钥加密后的消息，并验证 HASH 是否与浏览器发来的一致；获得浏览器发过来的对称秘钥 4.2 使用加密的随机对称密码加密一段消息，发送给浏览器浏览器解密并计算握手消息的 HASH：如果与服务端发来的 HASH 一致，此时握手过程结束，之后进行通信 　　c++ 11特性知道那些 　　tcp的几个字段ack，psh，rst之类什么作用 　　SYN表示建立连接， FIN表示关闭连接， ACK表示响应， PSH表示有 DATA数据传输， RST表示连接重置 　　c++吐核，原因，怎么排查，爆栈怎么查 　　分布式锁怎么实现的 　　c++的智能指针 　　虚拟地址空间 　　大端小端问题，怎样通过网络发送(考察网络序主机序转换的问题) 　　大端模式：是指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址端。 小端模式，是指数据的高字节保存在内存的高地址中，低位字节保存在在内存的低地址端 　　网络字节序类似于大端模式，因为UDP/TCP/IP协议规定:把接收到的第一个字节当作高位字节看待，类似于大端模式低地址存放高字节的存储方式，实际上也确实像，因为无论是收还是发，都是从低字节开始的，那么收到的第一个字节理应放到低地址。 　　场景题 　　# 朋友之间的点对点关系用图维护，怎么判断两人是否是朋友，并查集，时间复杂度，过程 　　程序现在CPU突然爆了，如何定位 　　给定某天 200 万用户登录日志（用户，登入登出时间），求某一时间点用户在线人数 　　两个小顶堆的优先队列，O(n)即可解决 　　如何从几亿个数中找到唯一出现的一个数（内存无法一次读取全部数据） 　　1G内存对1个T的数据进行排序 　　算法 　　最长回文子串 　　每K节点反转链表 　　两个字符串的最长公共子串 　　范围1到1000的数，原本有1000个，互不重复，现多出来1个重复的数，怎么找到他，统计次数，太慢，求和相减 　　N个糖果，每次只能取1个到6个，不能不取，你先取，请问是否有必胜策略，怎么取 　　找出规律不能为7的倍数，每次取到只剩7的倍数个糖果即可 　　八皇后的代码填空题 　　二分查找 　　海量数据topK的问题 　　合并有序链表 　　对称的数字 　　排序数组二分查找 　　左上角到右下角的路有几条？（中间存在障碍） 　　https://leetcode-cn.com/problems/unique-paths-ii/ 　　跳台阶问题 　　选硬币问题 　　twoSum 　　反转链表+判断栈是否合法 　　LeetCode 912.快速排序（要求分区点优化）& 堆排序 　　一本英文册中有很多单词，求单词的个数 　　反转一个字符串（需要进行优化） 　　实现一个队列 　　将字符串按单词反转，字符串结尾可能有句号，采用o(1)空间复杂度实现 　　lru，不用写全，把哈希表和双向链表结构写出来，增删操作伪代码就行 　　lru和lfu算法及缺点 　　最长无重复子串 　　Leetcode1166 设计文件系统 　　写一个简单的计算器 　　找出两个排序数组的相同的数 　　反转链表 　　字符串“6…”问第n个字符是啥。 　　一个ip字符串，转换成32位数字，考虑所有情况，把这个数字转化成01这样的储存(回答用移位和与操作，问有其他方法嘛？这时候想到了用struct) 　　写一个装饰器模式