1 计算机网络

1.1 网络分层和常见概念

  • 介绍网络5层模型，每一层都实现什么功能
    • 物理层：确保原始的数据可在各种物理媒体上以比特流的形式可靠地传输
    • 数据链路层：将源自网络层来的数据可靠地传输到相邻节点的目标机网络层
    • 网络层：实现两个主机之间的数据透明传送（不一定可靠(IP)）。主要功能：路由选择Routing；存储转发Forwarding；（一部分的）拥塞控制Congestion Control
    • 传输层：实现两个应用程序之间的数据透明传送（不一定可靠(UDP)）。将上层数据分段，提供端到端的可靠的(TCP)和不可靠的(UDP)服务。
    • 应用层：为操作系统或网络应用程序提供访问网络服务的接口
  • 端到端，点到点的区别
    • 端到端是针对传输层说的。在数据传输之前，先为数据的传输开辟一条通道，然后在进行传输。
    • 点到点通信是针对数据链路层或网络层来说的，是指一个设备发数据给直接连接的其他设备，通过一台一台直接相连的设备把数据传递到接收端。
    • 端到端的优点是，链路建立之后，发送端知道接收端一定能收到。而点到点发送端发出数据后，不知道接收端能否收到或何时能收到数据。
    • 端到端传输的缺点是直到接收端收到数据为止，发送端的设备一直要参与传输。点到点传输则在发送端设备送出数据后，它的任务已经完成。
    • 端到端经过中间交换设备时不需要进行存储转发（至少不可见），而点到点需要。但如果接收端设备关机或故障，点到点传输可以采用存储转发技术进行缓冲，端到端则传输失败。
  • 7层模型，5层模型，4层模型
    • OSI: 物理层；数据链路层；网络层；传输层；会话层；表示层；应用层
    • 5层模型: 物理层；数据链路层；网络层；传输层；应用层
    • TCP/IP: 网络接口层；网络层；传输层；应用层
  • 每一层有哪些常见协议？
    • 数据链路层：以太网协议
    • 网络层：IP; ICMP; ARP; RARP
    • 传输层：TCP;UDP
    • 应用层：HTTP(80); HTTPS(443); FTP(21); SSH(22); TELNET(23); DNS(53)
  • 路由器/交换机是哪一层
    • 网络层和数据链路层
  • 10.101.102.103是公网IP还是内网IP，如何区分公网内网
    • 这是内网ip
    • img
    • 除了这三个ip地址段为私有ip地址外，其它的都为公网ip。这些地址已被声明私有化，任何内网中的设备可以任意使用这些地址，但是在这三个范围内的IP地址不允许出现在Internet（外网）上。
  • MAC地址和IP地址分别有什么作用
    • 二层基于MAC地址转发数据帧，三层基于IP地址转发报文
    • 实际上，IP地址只在网络间寻址才起作用，在同一个网络内，IP地址在发送端被转化为MAC地址进行寻址，而这种转化和交换的对应关系，依赖于ARP协议和MAC地址表
    • 交换机：维护一张“MAC地址表”，用来记录目的MAC地址-端口的映射关系
    • 路由器：维护“路由表” 用来记录目的IP地址-端口的映射关系
  • ARP过程
    • 同一网段：使用MAC = 0xFFFFFFFFFFFF广播询问B的MAC，B回复一下自己的MAC地址，A自然就知道了
    • 不同网段：使用广播通信，发现网关的MAC地址，把IP报文发给自己的网关

1.2 UDP

  • TCP和UDP的本质区别
    • 面向连接&无连接；
    • 可靠交付&尽力而为交付
  • 什么时候选择TCP/UDP
    • 看重速度，不看重准确率：UDP. (如在线视频，DNS)
    • 其他：TCP (HTTP,FTP)
  • dns为什么要用udp
    • 访问冷门网站时，可能多次迭代查询，如果用TCP每一次都握手浪费时间。
    • DNS发送数据量很小，一般一个包就可以，所以不需要可靠传输
    • DNS有时也会用TCP，比如解析到的IP太多了，一个响应的UDP包放不下。这是通常的做法是如果客户端收到一个被截断的UDP响应包，用TCP重新请求一次DNS
    • 应对DNS污染：DNS over TLS(DoT)和DNS over https(DoH)
  • HTTP为什么不用UDP
    • HTTP需要可靠传输，UDP不行
    • HTTP3好像用(实现了可靠传输的)UDP了。。。
  • 怎么改进UDP让他实现可靠传输（好像是可以利用应用层来实现TCP的一些功能，从而达到可靠性，具体可能可以参考一下QUIC）

1.3 TCP

TCP基础

  • 三次握手

  • 四次挥手time_wait的

    两个原因

    • 原因1：为了保证客户端发送的最后一个ack报文段能够到达服务器.
    • 原因2：2msl的时间足以让本次连接产生的所有报文段都从网络中消失，这样下一次新的连接中就肯定不会出现旧连接的报文段了。

  • 四次挥手time_wait时间

    • time-wait的的持续时间为2 * MSL.
    • MSL（Maximum Segment Lifetime,报文最大生存时间），工程上为2min。
    • PS: 服务器如果收不到最后一个ack，会在RTO之内重传FIN. 一般MSL设置要远比RTO(Retransmission Timeout)要长, 因此2MSL时间内如果服务器重传FIN，客户端一定能收到

  • 握手时产生的序列号干什么用的

    • 给字节流排序，表明前后关系。
    • 随机产生：防止误接收过时的TCP报文段。

  • 讲一下接收窗口

    • 取决于接收缓存区的大小
    • 但是因为TCP头部原因，接收窗口要小于缓存区大小
    • 而且如果对方经常发小包，有溢出的危险

TCP拥塞控制

  • 主要有四种方法：滑动窗口机制、慢启动机制、拥塞避免机制、快速重传与恢复。
  • 【滑动窗口机制】包括发送窗口(SWND)、接受窗口(RWND)和拥塞窗口(CWND)。其中MAX（SWND）=MIN（CWND，RWND）。
  • 【慢启动机制】新建TCP连接的时候,拥塞窗口以一个数据包大小(512Byte)为基数,每接受一个ACK确认就会指数式增加CWND。
  • 【拥塞避免机制】拥塞避免机制就是在CWND达到ssthresh之后缓慢增大,每次只加一。
  • 【快速重传与恢复】如果发送方收到重复的三个确认，则会立即重传确认所期待的下一个报文。并从ssthresh/2开始恢复。（超时则重新慢启动）

差错控制

主要使用校验和、确认、超时重传这三个工具进行差错控制

  • 数据正确：校验和
  • 顺序正确：用序列号对失序数据包重新排序
  • 发包重复：丢弃重复数据
  • 发包缺失：确认号(ACK) + 超时重发

深入问题

  • TCP攻击(SYN-Flooding)
    • Server收到SYN时，将发送一个（ACK，SYN）应答报文，同时创建一个控制结构.如果 Server 在一段时间内没有收到应答消息，则控制块将被释放。
    • 在 TCP 协议软件中，通常对每个端口等待建立链接的数目有一定限制，当队列长度到达设定阈值时，将丢弃后面到达的 TCP SYN 请求报文。
    • 如果攻击者不断发送大量的 TCP SYN 报文，其他用户就无法再链接到被攻击者服务器
    • SYN-Flooding防御：启用SYN Cookie；增加SYN最大队列长度；降低SYN+ACK最大重试次数；TCP首包丢弃测试假IP；屏蔽握手过慢的可疑IP一段时间.DDoS（分布式拒绝服务）攻击是无解的吗？ - 刘浩博的回答 - 知乎
  • TCP 粘包
    • TCP是流协议，不存在所谓粘包，需要使用或自定义应用层协议
    • 法1：分隔符（但数据里的相应字符也要转义。不方便。）
    • 法2：Header+Payload，如每段数据前加一个2 byte的header记录长度
    • 法3：等长数据段 每个包就固定500 byte这样收发，肯定没问题
  • TCP keepalive
    • TCP协议在HTTP短连接环境下，数据交互完毕后就主动释放连接；但是HTTP长连接的环境下，客户端可能意外断电或者中间路由网络无故断开，导致非常多的半打开连接，浪费服务器资源
    • 保活机制默认是关闭的，TCP连接的任何一方都可打开此功能。
    • 三个参数：
      • 保活时间：tcp_keepalive_time。TCP连接没有发送数据多少秒之后，开始发送Keep-Alive探活包。
      • 探测时间间隔：tcp_keepalive_intvl。Keep-Alive数据包发送的间隔。
      • 探测循环次数：tcp_keepalive_probes。最多会发送多少个Keep-Alive数据包。

1.4 DNS

  • DNS是基于什么协议，有没有其他情况
    • 一般是基于UDP, 因为
      • 访问冷门网站时，可能多次迭代查询，如果用TCP每一次都握手浪费时间。
      • DNS发送数据量很小，一般一个包就可以，所以不需要可靠传输
    • 也有其他情况
      • DNS有时也会用TCP，比如解析到的IP太多了，一个响应的UDP包放不下。这是通常的做法是如果客户端收到一个被截断的UDP响应包，用TCP重新请求一次DNS
      • 应对DNS污染：DNS over TLS(DoT)和DNS over https(DoH)
  • DNS解析出错误ip的原因
  • 问了不了解DNS劫持
    • TODO 以后再说
  • 问DNS怎么查询二级域名
    • TODO 以后再说

1.5 HTTP

方法与字段

  • HTTP的方法，head get post (待补充，这下面是RESTful)
    • img
    • GET: 单纯获取资源信息。集合/单个项目均可作用。看语义。
    • POST: 创建一个新资源。需要施加在一个集合上，而非尚未存在的项目。
    • PUT: 替代性更新原资源。集合/单个项目均可作用。看语义。
    • PATCH: 部分更新原资源。集合/单个项目均可作用。看语义。
    • DELETE: 删除资源。集合/单个项目均可作用。看语义。
  • GET和POST的区别
    1. GET是幂等的，即读取同一个资源总是得到相同的数据，POST不是幂等的；
    2. GET一般用于从服务器获取资源，而POST有可能改变服务器上的资源；
    3. GET请求（包括参数）可被保存到收藏夹，POST则不可以
    4. GET请求的数据明文附在URL之后；POST请求的数据在HTTP body中；
    5. GET只允许ASCII字符，POST对数据类型没有要求，也允许二进制数据；
    6. GET的长度有限制（操作系统或者浏览器），而POST数据大小无限制
  • HTTP状态码。502和504有什么区别。301 302 500状态码
  • content-type了解吗
    • HTTP请求中的Content-Type是用来指定请求或者响应的内容类型
    • 常见的媒体格式
      • text/html(plain/xml) (charset=utf-8)
      • image/gif(jpeg/png)
    • 以application开头的媒体格式
      • application/xml(json/pdf/msword)
      • application/x-www-form-urlencoded 表单默认的key-value提交数据格式
    • 使用POST请求批量上传文件分割用
      • multipart/form-data（有boundary参数进行分割）
  • http的结构，大小如何确定？没有content-length字段呢？
    • 请求结构 = 请求行(方法；URL；版本) + 请求头 + 请求体
    • 响应结构 = 状态行(版本；状态码；状态码描述) + 响应头 + 响应体
    • 大小：content-length
    • Content-Length如果存在且生效, 必须是正确的, 否则会发生异常.(大于实际值会超时, 小于实际值会截断并可能导致后续的数据解析混乱)
    • 如果报文中包含 Transfer-Encoding: chunked 首部, 那么Content-Length将被忽略.主要应用要传输大量数据, 但在请求在没有被处理完之前响应的长度是无法获得的的情况.
    • img

高级特性

  • http2.0了解吗？
    • HTTP/2专注于性能，最大的一个目标是在用户和网站间只用一个连接。
    • 概念：流；消息；帧
    • 改进：二进制；多路复用；header压缩；server推送
  • 问了我HTTP如何改善一个request对应一个response的情况，聊到了keepalive，聊了聊HTTP 1.0 1.1 2.0，聊了聊多路复用，流水线
    • 自行去看笔记去！这里不多说了~

Session与cookie

  • Session和cookie的区别
    • Cookie和Session不是一个维度的东西。
      • Cookie和LocalStorage是同类的，都是浏览器保存数据的地方，是一个具体的东西。
      • Session和Token是同类的，都是记录服务端和客户端会话状态的机制，是一个抽象的东西。
    • Cookie属于http协议的一部分；既不是客户端也不是后端，而是两者之间的桥梁。后端可以设置修改cookie；前端可以获取到cookie。
    • Session借助cookie(或者URL重写，不安全)才能正常工作
  • Session和cookie的区别（正常答案）
    • session保存在服务器，cookie保存在客户端
    • session保存的是对象，大小无限制；cookie保存的是字符串，单个cookie不能超过4KB
    • session不能区分路径，同一个网站都可访问；cookie如果设置路径，则在某些地方不能访问
    • Cookie 可以设置任意时间有效，而 Session 一般失效时间短
    • 每次访问都要传送cookie浪费带宽；保存太多session浪费服务器
    • Session的安全性大于cookie, 因为 Cookie 可以通过客户端修改,有些状态不能保存在客户端
  • 浏览器关闭，session就销毁了嘛？
    • 要看session是否过期，和浏览器是否关闭无关。
  • 服务器关闭，session就销毁了嘛？
    • 正常关闭不会。非正常关闭可能就…销毁了。
  • 禁用cookie，如何使用Session ID
    • url重写
  • Session存在哪里，怎么把session_id返回给客户端？
    • 服务器端（内存，数据库，文件）
    • 在返回头中有setCookie，把session_id存到cookie中

1.6 HTTPS

  • HTTPS的连接过程
    • Client Hello： 客户端向服务器发送请求，同时发送客户端支持的一套加密规则（包括对称加密、非对称加密、摘要算法）；
    • Server Hello： 服务器从中选出一组加密算法与Hash算法，并将自己的证书和加密公钥发送给客户端；
    • 客户端验证： 使用发行者证书发行者的公钥解开服务器的证书，查看是否和服务器的实际域名相匹配；
    • 客户端发送密匙： 生成一个随机密钥，使用Hash算法对握手消息进行摘要计算，并将随机密钥和摘要一起用服务器提供的公钥加密发送给服务器；
    • 服务器验证： 服务器使用自己的私钥解密得到对称加密的密钥，并验证握手消息是否一致
    • 服务器对称加密： 服务器使用对称加密的密钥加密握手消息发给客户端；
    • 客户端对称解密： 客户端解密并验证摘要，若一致，则握手结束。之后的数据传送都使用对称加密进行
  • HTTPS怎么确认收到的包就是服务器发来的
    • HTTPS (建立安全连接之后) 虽然加密但是也不会把ip和portal加密了呀

2 数据库

2.1 事务

  • 事务的四大特性
    • Atomic原子性：要么全做，要么全不做。
    • Consistency一致性：不违反合法语义，如balance>0，主键唯一。
    • Isolation隔离性：并发事务不能互相干扰。
    • Durability持久性：一旦commit，对数据库的改变是永久的。
  • 四种隔离级别
    • Read Uncommited 读未提交
    • Read Commited 读已提交（解决脏读）
    • Repeatable Read 可重复读（解决脏读，不可重复读，幻读）
    • Serialized 串行化（解决脏读，不可重复读，幻读，丢失更新）
  • MySQL的可重复读底层是怎么实现的:MVCC
  • MVCC是怎么实现的
    • Innodb里面每行数据都可以有多个版本，字段trx_id记录生成这个版本的事务的ID。这些不同版本的数据不是物理存在的，而是每次通过undo log动态算出来的。
    • InnoDB 利用 undo log 和 trx_id 的配合，实现了事务启动瞬间创建快照的能力。MVCC的核心在于每个事务自己维护的一个事务ID数组。
    • img
    • 如果 trx_id 小于低水位，表示这个版本在事务启动前已经提交，可见；
    • 如果 trx_id 大于高水位，表示这个版本在事务启动后生成，不可见；
    • 如果 trx_id 大于低水位，小于高水位，分为两种情况：
      • 若 trx_id 在数组中，表示这个版本在事务启动时还未提交，不可见；
      • 若 trx_id 不在数组中，表示这个版本在事务启动时已经提交，可见。
    • MySQL是如何实现可重复读的? - 超超不会飞的文章 - 知乎
  • 什么是幻读
    • 在同一事务内查询返回不同的结果集合。一般是由于其他事务插入并提交了一些记录造成的。
  • InnoDB 怎么防止幻读
    • 在RR的隔离级别下，Innodb使用MVCC和next-key locks解决幻读
      • MVCC解决的是普通读（快照读）的幻读
      • next-key locks解决的是当前读情况下的幻读。
    • 多说一句：在RC的模式下，MVCC解决不了幻读和不可重复读，因为每次读都会读它自己刷新的最新的快照版本（读已提交）

2.2 索引

  • 什么是B+树
    • B+树是一个平衡的多叉树，从根节点到每个叶子节点的高度差值不超过1，而且同层级的节点间有指针相互链接。
  • 为什么用B+树
    • 相对于b树/二叉树来说,B树每个节点能存储的节点数更多，层级更低。
    • 相对于b树来说,每次查询是一定要到叶子节点，查询就更稳定
    • 相对于b树/二叉树/Hash来说,叶子节点有双向链表，便于范围查询。
    • 哈希索引在等值查询上有绝对优势，但是无法范围查询，无法用于排序，不支持最左前缀匹配原则（必须全部match）
  • B+树叶子满了，要添加新值怎么办
    • 尝试插入；如果key的个数满了就节点分裂，如果分裂后父节点也满了就长高
  • mysql索引有哪些
  • 联合索引的使用场景
    • 在查询时有多个字段总是同时出现则这些字段就可以作为复合索引,形成索引覆盖,提高where/group by/order by/limit 语句的查询效率
    • 最左匹配当遇到范围查询(>、<、between、like)就会停止匹配。
    • 将区分度高的字段放在前面，区分度低的字段放后面
    • 索引越少越好，在修改数据时每个索引都要进行更新，降低写速度

2.3 具体语法与语句执行

  • 一条 SQL 语句的执行流程

    肥猫三千问

    1. 查询缓存：是一个哈希表，将执行过的语句及其结果以key-value的形式保存。已经被历史淘汰。
    2. 分析器：解析器(词法分析语法分析，保证语法正确)；预处理器(验证查找的数据的确存在且权限满足，保证语义正确)
    3. 优化器：根据语法树，自动优化生成执行计划
    4. 执行器：根据执行计划，逐条调用底层存储引擎逐步执行

  • MySQL：各种连接的区别

    • 自连接；内连接；交叉连接；外连接
    • 自连接：一张表，使用多个别名，表面上进行多表连接查询
    • 内连接查询操作只列出与连接条件匹配的数据行（等值；不等；自然）
    • 交叉连接：笛卡尔积
    • 外连接：不只列出与连接条件相匹配的行，而是所有符合搜索条件的数据行，不满足连接条件则置空。

  • mysql的数据类型有哪些

img

  • int(10) 和 varchar(10)有什么区别
    • int字段长度其实是固定的，就是4个字节，括号里的长度是和zerofill配合打印用的。
    • varchar(10) 是真的用了10+1个字节的空间。
    • varchar为可变长度，但在字符的最后面会加一个1个字符，用来存储位置
    • char为固定长度，多余的存储空间会用空格来补齐，读取时尾部空格会丢失
  • where, ordered by, grouped by 等执行先后顺序
    • 先where，再group by, 最后order by
  • sql优化，a>‘x’ and z=‘x’ 会不会失效
  • explain有哪些字段
    • id：数字越大越先执行，一样大则从上往下执行
    • select_type:查询的种类，有simple,primary, subquery,derived,union等。
    • table：表名
    • type：使用的索引类型
    • 还有possible_keys，key，extra 等等

2.4 数据库动手题

  • 写一个建表语句
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

CREATE TABLE t_user2(id INT ,
userName VARCHAR(20) NOT NULL,	# 增加约束
password VARCHAR(20),
age INT,
PRIMARY KEY (id),	# 指定主键
FOREIGN KEY (P_Id) REFERENCES Persons(P_Id)	# 指定外键
UNIQUE INDEX index_userName(userName)  #同时创建索引
CHECK (age>0)		# 增加约束
);
复制代码
  • 一个sql语句student(sno, sname, …)中以“王”姓开头的个数
    • SELECT COUNT(*) FROM student WHERE sname LIKE '王%'
  • 数据库设计：文件的增加、删除、移动、列出子目录。设计一个表结构。
  • MySQL 有一个表 user表，有两个字段 userid, userdata。 ( userdata是json格式，有很多数据，包括name, age等等)
  • 设计一个接口，传入一个id， 和任意类型的数据，比如age，name，然后对特定的数据进行修改。 SQL怎么写？两个设备下，一个设备修改age，另一个设备修改name，同时修改，但是最后发现age修改成功了，name没有修改成功，为什么？加了事务还是会，怎么解决？除了 select… for update 还有什么思路吗
  • 做一个设计题，用户关系服务设计
    • 用户可以关注、取关任何一个人
    • 可以快速判断一个用户和一群用户的关系（无关系，粉丝，关注，好友）
    • 可以查看自己的粉丝列表，关注列表（以分页的形式）
    • 可以查看关注数和粉丝数
    • 随着用户增长，可能遇到什么瓶颈，如何优化？
    • 数据表的设计，sql查询语句，如何建索引，怎么查看sql有没有用索引，数据量大如何分表（回答的是hash(user_id)/N），这样分表后如何扩容，（想不出来了），大v怎么存，redis set zset，大v的粉丝都需要存到redis中吗？（不应该，但也不知道咋整）

3 操作系统

3.1 用户态和核心态

  • 什么是用户态和内核态
    • 系统态（核心态、特态、管态）：执行全部指令。
    • 用户态（常态、目态）：执行非特权指令。
  • 用户态如何切换到内核态
    • 外部中断；程序异常；系统调用
  • 中断分为哪些？
    • 外部中断：由CPU外部设备引起，又叫异步中断。包括硬中断（IO）和软中断(系统调用/陷入).
    • 内部中断：由CPU内部引起。如除0错、地址访问越界。又叫异常，同步中断。

3.2 进程

进程，线程，协程

  • 进程和线程的区别
    • 进程是资源分配的基本单位，而进程是CPU调度的基本单位
    • 线程共享进程的代码，地址空间，文件/网络句柄等资源，
  • 线程不共享的部分
    • 栈：函数调用的参数和返回地址、局部变量等内容
    • PC（Program Couner）：程序计数器，指向代码所在的内存地址。
    • TLS（Thread local storage）：线程在共享的堆中分配的变量。

img

  • fork函数
    • fork给父进程返回子进程pid，给其拷贝出来的子进程返回0，
    • 这也是他的特点之一，一次调用，两次返回。
    • 两次返回看上去有点神秘，实质是在子进程的栈中构造好数据后，子进程从栈中获取到的返回值。
1
2
3
4
5
6
7
8

int main()
{
    int pid = fork();
    if (pid == -1) return -1;
    if (pid) printf("I am father, my pid is %d\n", getpid());
    else printf("I am child, my pid is %d\n", getpid());
}
复制代码
  • 线程与协程
    • 协程既不是进程也不是线程，协程是一个特殊的函数
    • 协程被称作用户级线程，对于操作系统是并不可见的，不再被内核调度，而是交给了程序自己。
    • 协程也存在CPU上下文切换的问题，但相比线程切换更加高效。
    • 协程失去了使用多CPU的能力，实际上性能不如线程。说协程性能好的是瓶颈在IO上面
  • 协程的使用场景
    • IO密集型：总是在阻塞，总是在切换
  • 多进程多线程应用场景
    • 需要大量共享数据或频繁通信时，使用多线程，其他情况下尽量使用多进程。
    • 多进程有更强的容错性；并且资源天然隔离没有同步问题；通过增加CPU可以容易扩充性能。

进程调度与通信

  • 进程调度方法
    • FCFS; SJF; HRRN
    • 时间片轮转；优先级；多级反馈队列
  • 进程的状态转换
    • 新建；就绪；运行；阻塞；终止
  • 进程切换发生哪些事情
    1. 切换新的页表，然后使用新的虚拟地址空间(页表切换后TLB就失效了，那么虚拟地址转换为物理地址就会变慢,这就是为什么切进程比切线程效率低)
    2. 切换内核栈和硬件上下文
  • 进程间通信的方式
    • 管道(PIPE/FIFO)；消息队列；共享内存；信号；信号量；socket
  • 进程间通信的方式，哪种最快
    • 共享内存（无需拷贝数据同时读写）

进程间资源共享与死锁

  • 信号量怎么实现对共享资源的访问
    • 信号量本质是一个计数器，表示该共享资源的余量
    • PV原语是…… 如果信号量为0，则阻塞等待……
  • 并发和并行的区别
    • 并发：同一时间段中有多个程序在运行
    • 并行：多CPU系统中，多个程序无论宏观还是微观上都是同时执行的
    • 异步：在等待某个资源的时候继续做自己的事
  • 死锁发生的原因
    • 互斥条件；请求与保持条件；不剥夺条件；循环等待条件
  • 银行家算法流程，怎么检测不安全状态

进程的内存空间

  • 进程的内存模型

    1. 栈区（stack）：由编译器自动分配释放
    2. 堆区（heap）：一般由程序员分配释放，程序结束时可能由OS回收。与数据结构中的堆是两回事，分配方式倒是类似于链表
    3. 静态区（static）：全局变量和静态变量. 初始化的在一块区域，未初始化的在相邻的另一块区域。程序结束后由系统释放。
    4. 文字常量区：常量字符串就是放在这里的。程序结束后由系统释放
    5. 程序代码区：存放函数体的二进制代码。

  • 全局变量存储位置

    • 已经初始化：data；未初始化：bss

  • (java)堆什么时候做内存回收

  • 堆和栈的区别？

    • 大小限制：栈底的地址和栈的最大容量是系统预先规定好的（2M/1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间, stack overflow。因此，能从栈获得的空间较小。堆是用链表来存储的不连续内存区域，大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
    • 申请效率：栈由系统自动分配，速度较快。但程序员是无法控制的。堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.
    • 存储内容：栈存储返回地址，参数，局部变量。堆在这块内存空间中的首地址处记录本次分配的大小，具体内容由程序员安排。
    • 数据访问：存储在堆中的对象是全局可以被访问的，然而栈内存不能被其他线程所访问，且遵循LIFO原则。
    • 生命周期：栈内存的生命周期很短，而堆内存的生命周期从程序的运行开始到运行结束。

3.3 内存管理

  • 讲一下操作系统的内存管理，如何进行内存分配
    • 连续内存分配（首次适配，最佳适配，最差适配）
    • 非连续内存分配（分段，分页）– 虚拟内存技术&页面置换算法
  • 内存为何要分页
    • 内存的连续分配总是会有碎片的产生，不连续就能解决碎片问题
  • 页置换算法(LRU 最近最久未使用)
  • 地址转换
  • 虚拟地址和物理地址怎么对应的？
    • 基址 + 偏移
  • 页表机制中TLB做了什么？MMU做了什么？
    • MMU内存管理单元: 将页号分离出来，然后判断该虚拟页面是否有效，是否在内存，是否受到保护。并做出相应的反应（禁止访问/缺页中断/正常找到对应物理页号）
    • Translation Look-Aside Buffer,TLB 翻译快表：最近使用页面映射的缓存。其记录的格式与内容和正常页表一样。使用硬件O(1)并行查找记录。减少访问内存页表或多级页表的次数。在查找的时候，TLB与正常页表同时进行。

3.4 Linux常用命令

  • Linux常用命令
    • cd; ls;
    • find / -name passwd # 查找文件名为passwd的文件
    • cp; mv; rm
    • ps 用于将某个时间点的进程process运行情况选取下来并输出
    • top 和ps命令的输出也很多重叠的部分; top命令可以一直动态刷新显示
    • kill -signal PID
    • cat; head; tail
  • Linux查看所有进程占内存最高得前10个（top）
  • linux如何查看哪个端口被占用呢？
    • lsof -i -P -n | grep LISTEN
    • lsof -i:22 ## see a specific port such as 22 ##
    • netstat; ss
  • linux的命令，如何查看服务器负载？
    • top：CPU内存
    • iostat：IO的开销
  • 如何查看远程服务器某一个端口被占用(nc命令，nmap命令，telnet命令)
1
2
3
4
5
6
7
8

>>> nmap 192.168.1.8 -p 22
 
Starting Nmap 7.70 ( https://nmap.org ) at 2019-03-16 03:37 IST Nmap scan report for 192.168.1.8 Host is up (0.00031s latency).

PORT STATE SERVICE
 
22/tcp open ssh
复制代码
  • 怎么查看django server的进程呢？
  • 怎么查看硬盘的占用情况呢？
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

crysflair@crysflair:~$ df
Filesystem     1K-blocks    Used Available Use% Mounted on
udev             1004100       0   1004100   0% /dev
tmpfs             204800    2744    202056   2% /run
...文件系统的占用

crysflair@crysflair:~$ du -sh ~
262M    /home/crysflair
文件夹的大小
复制代码

3.5 IO模型

  • Linux io模型

img 另一个精辟好文： zhuanlan.zhihu.com/p/36344554

  • 讲讲同步IO、异步IO，从用户态与内核态的角度讲
    • 对于一次IO访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间
    • 同步IO的执行者是IO操作的发起者（用户进程）。同步IO需要发起者进行内核态到用户态的数据拷贝过程，所以这里必须存在阻塞。
    • 异步IO是指用户进程触发I/O操作以后就立即返回，当I/O操作已经完成的时候会得到I/O完成的通知。异步IO的执行者是内核线程，内核线程将数据从内核态拷贝到用户态，所以这里没有阻塞
  • Epoll和其他两个IO复用的区别
    • select 以数组形式存储文件描述符fd，64位机器默认2048个，数量有限。无法感知具体是哪个流OK了，所以需要遍历，函数的时间复杂度为O(n)。而且多次复制句柄数组产生大量开销。只支持水平触发（没有完成IO下次还会返回）。
    • poll 以链表形式存储文件描述符，没有长度限制。本质与select相同。
    • epoll 是基于事件驱动的，如果某个流准备好了，会以事件通知，不需要遍历，函数的时间复杂度为O(1)。（内存红黑树组织自己的文件系统；新添加的socket注册回调函数；中断内核插入就绪链表）
  • 多线程的IO复用和单线程的IO复用有什么区别，为什么要用多线程呢
  • Redis为什么高效，为什么它不用多线程呢
  • 水平触发和边缘触发的区别和使用场景

4 Python语言

4.1 高级语法

  • 什么是生成器
    • 用yield函数的方式实现迭代器
    • 另一种做法是Generator Comprehension.圆括号.
    • 不立刻产生全部结果，节省内存，效率高。
  • 什么是迭代器；
    • 所有能用next访问取值的对象（当然同时也能for）
  • 什么是装饰器；
    • 使用一个函数return另一个函数，并动态添加特定的效果
  • 手写装饰器

4.2 数据结构

  • python的数据类型都有哪些？和别的语言有什么不同的数据类型吗？
    • Number(int,float,bool,complex)
    • String
    • List, Set, Dict, Tuple
  • 元组和list的区别
    • list可变，元组不可变. 底层都是变长数组，速度没有区别。
  • Python中的dict底层怎么实现的
    • 哈希表。使用伪随机探查法处理哈希冲突。
  • 双等于和is有什么区别
    • ==判断两个对象的值是否相等（ __eq__ ）
    • is判断的是对象的id是否相同

4.3 语言特性

  • 垃圾回收

    • 主要通过引用计数进行垃圾回收；
    • 通过 “标记-清除” 解决容器对象可能产生的循环引用问题；
    • 通过 “分代回收” 以空间换时间的方法提高垃圾回收效率

  • 深拷贝浅拷贝

    • Python不会对值相同的不可变对象申请单独的内存空间。只会记录它的引用次数。因此深浅拷贝是针对可变对象说的。
    • 浅拷贝：拷贝了原始元素的引用（内存地址）
    • 深拷贝：在遇到可变对象时，又在内部新建了一个副本。
  • 1

    __init__.py

    文件的作用是什么？除了引入模块之外还有别的作用吗？引入的模块都会被执行吗？

    • 去import一个Package的时候，会隐性执行 __init__.py。在 __init__.py 中定义的对象，会被绑定到当前的命名空间里面来
    • 导入子模块的时候，它会优先执行父模块中的 init ，接着执行自己模块中的 init. 导入父模块则只执行父模块的 init，可以在父模块使用 __all__=['submodule1','submodule2'] 这样的方法批量导入命名空间
    • 除了引入模块，可以在 __init__.py 做一些初始化的操作，比如数据库 session 的创建

  • 常用的库都有哪些呢？

5 散装知识

散装知识就是…… 既不是计算机网络，又不是操作系统，还不是数据库 ٩(๑`—´๑)۶

5.1 哈希表

  • HashMap（java）解决Hash冲突的方法。HashMap原理和扩容

    • HashMap 底层是 hash 数组和单向链表实现，数组中的每个元素都是链表。
    • 解决Hash冲突的方法：拉链法。当链表长度超过 8 时，链表转换为红黑树。
    • 扩容：实际填充度大于loadFactor装载因子（默认值是0.75）。扩容时，调用 resize()方法将table长度变为原来的两倍（初始长度默认16）

  • 哈希表是如何解决高并发的? 链表是如何形成环的？

  • ConcurrentHashMap底层是怎么实现的

  • hash冲突除了链表还有什么方法？

    1. 开放定址法
      • 线性探测再散列(+1,+2,+3…+n)
      • 二次探测再散列(+1,-1,+2,-2,+4,-4…+2^n, -2^n)
      • 伪随机探测再散列(+3,-6,+8,-7,-10,+2,+4..一串包含值从1到M–1的permutation随机序列)）
      • 双散列探查法((hash1(key) + i * hash2(key)) % TABLE_SIZE, i为步长，若再次碰撞则+1)
    2. 再哈希法(一个要是算出来重复啦，再用另一个算法去算)
    3. 链地址法(Java hashmap就是这么做的)
    4. 建立一个公共溢出区

  • 开放寻址法有什么缺点？

    1. 记录的数目不能超过桶数组的长度，如果超过就需要扩容，导致某次操作的时间成本飙升
    2. 使用探测序列需要计算，可能时间成本高
    3. 记录尺寸或总数规模很大时，空槽占用的空间会导致明显的内存浪费
    4. 删除记录时，比较麻烦。需要设置删除标记。导致额外的空间和操作。
    • 优点：便于序列化

  • 拉链法有什么优点

    1. 对于记录总数频繁可变的情况，处理的比较好（避免了动态调整的开销）
    2. 由于记录存储在动态分配的节点中，不会造成内存的浪费，适合那种记录本身尺寸（size）很大的情况，此时指针的开销可以忽略不计
    3. 删除记录时，比较方便，直接通过指针操作即可
    • 缺点：相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销；不便于序列化。

    拉链法&开放寻址对比总结：空间的问题；删除的问题；访问速度的问题；系列化的问题

5.2 面向对象

  • Override和overload的区别

    • 重载Overload：表示同一个类中可以有多个名称相同的方法，但这些方法的参数列表各不相同（即参数个数或类型不同）。和编译器有关，和OOP无关。
    • 重写Override：表示子类中的方法可以与父类中的某个方法的名称和参数完全相同，通过子类对象调用这个方法时将调用子类中的方法(即使是父类指针)。可以实现多态。

  • Restful api

    1. 统一接口Uniform Interface：接口要包括URL（一种资源）和自描述信息（如何处理这种资源）。可读性强。使得客户端只需要关注实现接口就可以。
    2. 无状态性Stateless：客户端的每一次请求带有充分的信息（url,header,body）能够让服务端识别。好处是便于debug，坏处是浪费传输带宽。
    3. Client-Server：数据存储在Server端，Client端只需使用就行。两端彻底分离。使client端代码的可移植性变强，Server端的拓展性变强。
    4. 可缓存Cacheable：管理得当的缓存会部分地或完全地除去客户端和服务端之间的交互，进一步改善性能和延展性
    5. 系统分层Layered System：客户端通常无法得知自己是直接还是间接与端服务器进行连接。分层时同样要考虑安全策略。

  • 如果要给软件加一个功能，是要用组合还是用继承

    • 如果需求上一些功能是可自由组合的，那么应该用组合，强行用继承的话会产生组合爆炸（Combinatorial explosion）问题。
    • 继承层次过深、过复杂，会影响到代码的可维护性。
    • 继承主要有三个作用：表示is-a 关系，支持多态特性，代码复用。
    • 从理论上讲，通过组合、接口、委托三个技术手段，可以替换掉继承。在项目中不用或者少用继承关系，特别是一些复杂的继承关系。
    • 继承向上传递调用以实现复用，组合向内传递以实现委托。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public class Ostrich implements Tweetable, EggLayable {//鸵鸟
  private TweetAbility tweetAbility = new TweetAbility(); //组合
  private EggLayAbility eggLayAbility = new EggLayAbility(); //组合
  //... 省略其他属性和方法...
  @Override
  public void tweet() {
    tweetAbility.tweet(); // 委托
  }
  @Override
  public void layEgg() {
    eggLayAbility.layEgg(); // 委托
  }
}

作者：沐晨
链接：https://zhuanlan.zhihu.com/p/93899632
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复制代码
  • 多重继承 如何解决钻石模型
  • 面向对象语言的三大特性
    • 封装：隐藏对象的属性和实现细节，仅对外公开接口。目的是增强安全性和简化编程
    • 继承：就是子类继承父类的特征(变量)和行为(函数)。可以代码重用(但也带来高耦合)，最大的意义在于实现多态。
    • 多态：子类对象可以被视作一个父类对象。根据程序运行时实际使用的类来达成不同的效果(执行子类自己重写的函数)。

5.3 Redis

为什么要用Redis？Redis为什么这么快？ - 胖狗子的文章 - 知乎

  • Redis的数据结构
    • String 整数，浮点数或者字符串
    • Set 集合
    • Zset 有序集合（跳跃表实现）
    • Hash 散列表
    • List 列表
  • Redis为什么快，为什么单线程
    • 首先，采用了多路复用阻塞io机制;
    • 然后，数据结构简单，操作节省时间;
    • 最后，运行在内存中，自然速度快
    • 单线程：Redis的瓶颈不是cpu的运行速度，而往往是网络带宽和机器的内存大小。单线程切换开销小，容易实现。

5.4 设计模式

  • 用过哪些设计模式，我说单例、工厂、观察者、代理模式。（他想让我说策略模式、装饰模式和适配器模式，但这三个我都不知道）

  • 装饰器模式

    • 动态地给某个对象添加额外的行为，比生成子类更为灵活(因为装饰的是对象不是类)
    1. 抽象组件(Component): 定义被装饰对象的接口
    2. 具体组件(ConcreteComponent)：定义被装饰器装饰的对象
    3. 抽象装饰器(Decorator): 维护对Component的引用
    4. 具体装饰器角色(ConcreteDecorator)：向组件添加新的职责

  • 设计模式了解吗，说一下策略模式

    1. 环境类(Context):持有一个具体的策略类的引用，提供给客户端调用。屏蔽高层模块对策略/算法的直接访问. 还可以提供一些公共功能或者是存储一些状态。
    2. 抽象策略类(Strategy): 策略的抽象，一般定义接口。
    3. 具体策略类(ConcreteStrategy):具体的抽象策略实现，实现接口。
    • 优点：切换策略很方便，增加策略也方便。
    • 缺点：每个策略都是一个类（数量增多），策略类都需要对外暴露（上层模块必须知道有哪些策略然后才能决定使用哪一个）

  • 适配器模式

    • 适配器模式可以让原本接口不匹配的两个类可以协同工作，起到转换的作用。
    • 类的适配器模式：把适配的类的API转换成为目标类的API。继承extend原始的被适配类，实现implement目标的接口。
    • 对象的适配器模式：也是把适配的类的API转换成为目标类的API。但是通过组合而非继承来完成。包含被适配类的对象，实现implement目标的接口。

5.5 Git

  • git rebase git merge 的区别

5.6 Behaviour Question

  • 看你简历有xxx，我们来聊一下
  • 给我说说你现在都在关注哪些最新的技术好么
  • 描述一个解决的问题，如何去解决的
  • 描述一个未解决的问题，探索解决问题的途径
  • 对一个陌生的工作，如何去开展工作
  • 最近看了什么非技术的书和技术的书
  • 会不会给自己比较大的压力

6 项目

显然项目这个引人而异，我是挑了几个和我的项目比较沾边的。

  • 项目里的登录状态怎么做的
    • django自带的auth模块
  • token有哪些好处,相比较cookie+session
  • Mvc，MTV
  • 大量连接时sessionid可能重复？
    • 可能会。但概率很小。
  • django的orm
  • 如何搜索数据库里的文章
1
2
3
4
5
6

# Django ORM: 搜索标题或内容包含指定字符串的文章，大小写不限
articles = articles.filter(
    Q(title__icontains=search) |
    Q(body__icontains=search))
# 这个Q是把条件包起来，因为filter直接逗号分隔的话，是AND。用了Q,和 | 运算符可以实现OR
复制代码
  • 标签-文章表太慢怎么办(not sure)
    • 文章上加索引。标签重复度高，不能加索引
    • 加缓存。一般用户按标签看文章都是看最上面的那几篇
  • 大文件上传

7 算法

7.1 经典题目

最长上升子序列

这是一道考烂了的题

 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
38
39
40
41
42
43
44
45
46
47
48
49

# 定义 arr[i]: 长度为i+1的连续上升子序列的尾部数字大小
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = []    
        for n in nums:
            # 特殊情况：一开始还没有数据的时候
            if not arr: 
                arr.append(n)
                continue
            # 从后往前找到比当前值小的数，在它的基础上延长
            i = len(arr)-1  
            while arr[i] >= n and i>=0: i -= 1
            
            if arr[i] < n:  # 因为找到小值而停止
                if i+1 < len(arr):  # 如果后面有人，尝试更新这个长度。尾部数字越小越好
                    arr[i+1] = min(arr[i+1], n)
                else:   # 如果后面没人，新开一个长度
                    arr.append(n)
            else:   # 没有找到比自己更小的，在0处停止
                arr[0] = n

        return len(arr)
复制代码
# 使用二分查找优化至 O(NlogN)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        arr = []    # arr[i]: 长度为i+1的连续上升子序列的尾部数字大小
        for n in nums:
            # 如果arr中没有比n大的数
            if not arr or arr[-1]<n: 
                arr.append(n)
                continue
            # 找比n刚好大一点的数，二分查找
            left,right=0,len(arr)-1
            while left <= right:
                mid = (left+right)//2
                midval = arr[mid]
                if midval > n:
                    right = mid-1
                elif midval < n:
                    left = mid+1
                else:
                    left = right = mid
                    break
            # 经过分析，left所指的肯定就是比n大一点或等于n的
            arr[left] = min(arr[left], n)
            
        return len(arr)
复制代码

剑指48.最长不含重复字符的子字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        left, right = 0, 1	
        # 左开右闭。right负责探索未知天地。
        contain = set()
        contain.add(s[left])
        ans = 1
        
        while right < len(s):
            if s[right] not in contain:
                contain.add(s[right])
                ans = max(ans, len(contain))
                right += 1
            else:	
            # 如果发现重复，就扔掉左边字符，直到不重复为止
            # 极端情况下，left=right，相当于扔空原有集合
                contain.discard(s[left])
                left += 1
        return ans
复制代码

接雨水

  • 每面墙一旦出现，就把它和左边墙之间能填的缝隙全都使用水泥填上。（这里假装是水泥，比水更形象。浇过的水泥也会变成墙）
  • 那么左边已经处理的部分，一定是先增加再减少的阶梯型，没有凹陷。对一面新出现的墙，它的左边由近及远是从比它矮的墙到比他高的墙
  • 按层次浇筑水泥。一开始的瓶颈是左边的矮墙，随着一层层浇筑水泥，池底的高度也越来越高。最后的瓶颈是它自己作为右边的矮墙。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []
        ans = 0
        for i, h in enumerate(height):
            if h == 0:
                continue
            bar = 0  # 对于每一面新处理的墙，bar都是全新的
            while stack:
                i_, h_ = stack[-1]
                if h_ <= h:     # 如果栈顶<=当前的墙, 用当前的墙不断碰撞左边的墙，并且逐步提升bar
                    ans += (i-i_-1) * (h_ - bar)
                    bar = h_
                    stack.pop()
                else:           # 如果栈顶>当前的墙, 当前的墙成为了右边的矮子，根据当前bar加水。
                    # 当前bar是当前的墙和此时栈顶之间的墙的最大值，在第一步的不断碰撞中已经计算好了
                    ans += (i-i_-1) * (h - bar)
                    break
            stack.append((i,h))
        return ans
复制代码

LRU实现

三数之和

wu_yan_zu - 力扣题解

一个字符串，找出出现第二多的字符

  • 这应该只能哈希表计数吧？

鸡蛋掉落

这个题写的时候屡屡受挫，要注意：

  • 思考的时候就要用题里给的符号，要么就全程用自己的符号。总之要统一！！！ 这个题草稿纸上想的时候用的是f(N,d)思考，但题目的顺序是(K,N),结果各种顺序写反也看不出来，浪费好多不必要时间。
  • Debug复杂的递归代码的时候，一下子打印一大片，分隔线也不好画，而且请相信即使分开了思路也是不可能follow的。。。另一种办法是按代码的逻辑功能分开，控制变量地测试。 例如"把二分替换成穷举"结果就由错变对了，说明二分代码有bug而其他代码无bug。不过这么做的前提是这个逻辑模块有“更愚蠢但可靠”的替代品。如穷举法。
  • 这题一开始我去找极值点了，侥幸认为没有那么多水平线除非答案附近，而实际上导数为0的地方还挺多的，离真正的最小值也挺远的。。。这就导致midval=midrval的时候非常难以处理。正解是去搜索upper=downer的地方。可见一开始考虑不周后果不堪设想。
  • 对于多次进入的递归函数，要考虑到输入参数的可能范围。鸡蛋是每次递归最多减一，因此可以保证在K=1的时候肯定已经被处理，不会有K=0的情况。如果出现N=0的情况一定是因为mid=1或mid=N。理论上前者有可能出现，因此还是处理一下比较好。

一个先递增后递减的数组找出独特元素的个数

先用set 需要O(n)的时间复杂度 然后写了个双指针 写完了也不用跑就结束了

实现循环队列 (leetcode 622)

  • 使用一个 k+1 长度的数组存储
  • 注意在MOD数组下标的时候也要按k+1取模啊！

二叉树转双向链表

爬楼梯 => 不允许到达7的倍数层

  • 类似斐波那契数列。不允许到达7的倍数层就不算了呗。

树中两个点的最长路径和 (leetcode 124)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        ans = root.val
        
        def work(node):
            nonlocal ans
            # ans: node+max(0,左边最长链长)+max(0,右边最长链长)
            # work函数：返回以node为头结点的最长链长，可能为负数
            
            if not node: return 0
            leftmax = work(node.left)
            rightmax = work(node.right)
            #print("at node", root.val, "leftmax,rightmax=",leftmax, rightmax)
            ans = max(ans, node.val + max(0,leftmax) + max(0,rightmax))
            return max(leftmax, rightmax, 0) + node.val
        
        work(root)
        return ans
复制代码

找比当前数大的下一个数（如1243，结果是1324）

  • 注意严谨。爬山的时候等于也要爬。这样才能正确处理重复数字
  • python中nums[nextdigit+1:].sort()行不通
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:	# LeetCode 31
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        这个函数也可以处理有重复值的情况~ 注意“爬山”时候的大于等于号~
        """
        
        cur = len(nums)-1  # 从后往前找第一个跌落(<)的地方
        while cur >= 1 and nums[cur-1] >= nums[cur]: cur -=1
        if cur==0:
            nums.reverse()
            return
        nextdigit = cur-1  # 即将增大进位的那个数位

        cur = len(nums)-1  # 从后往前找最小的大于target的数
        while nums[cur] <= nums[nextdigit]: cur -=1

        nums[cur], nums[nextdigit] = nums[nextdigit], nums[cur]
        nums[nextdigit+1:] = sorted(nums[nextdigit+1:])
复制代码

求x的y次方，想出比直接for循环更好的方案

  • 二进制快速幂

求众数

  • 摩尔投票

找出一个未排序的整数数组中没有出现的最小的正整数

用列表下标做哈希。

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度

滑动窗口。

二维数组，按行递增，按列递增，问是否能找到某个数字

  1. 从左下角右上角找的简单办法。但面试官会让你写正常二分，哈哈。
  2. 矩阵分成4块。但不是按行列中心点切割。具体见题解方法3

一个IP地址转成int类型数据（IP地址是32个比特，int也是32个比特）

二叉树找两个节点的公共父节点

img

快排当有很多重复数时怎么优化

三路快排.这玩意必须得手写一遍！

一组数字怎么排列组合出的数最大

和字符串同理。自定义规则排序。

字符矩阵是否存在给定的字符串

  • dfs，计算时间复杂度.剑指 Offer 12. 矩阵中的路径

非负整数字符串重新排列使得结果最小

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 剑指 Offer 45. 把数组排成最小的数
from functools import cmp_to_key    # python大法好!!
def compare(x1, x2):   # 如果x1更大返回正数，更小返回负数，相等返回0.
    return int(x1+x2) - int(x2+x1)

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums = [str(i) for i in nums]
        nums.sort(key=cmp_to_key(compare))
        return ''.join(nums)
复制代码

给定字符串，找出最短的包含指定字符的子串

并说出算法的时间复杂度，证明算法的有效性。

  • 应该和最长不重复子串一个思路，维护左右指针和一个集合

LeetCode 54 螺旋矩阵，做完提问怎样保证不会重复输出.

这个题有两种方法：分圈打印法，和四周“剥边”法。下面是分圈打印的代码。 保证不会重复输出也就是在left,right重合，或top,down重合的时候，不打印第二个即可。

 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

class Solution:		# 分圈打印法
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        
        m,n = len(matrix),len(matrix[0])
        left,right = 0, n-1
        top,down = 0, m-1
        
        ans = []   
        def printCircle(top, left, down, right):
            nonlocal ans
            for i in range(left,right+1):
                ans.append(matrix[top][i])
            for j in range(top+1, down):
                ans.append(matrix[j][right])
                
            if top != down:     # 这一部分可能被吞哦！
                for i in range(right, left-1, -1):
                    ans.append(matrix[down][i])
            if left != right:   # 这一部分可能被吞哦！
                for j in range(down-1, top, -1):
                    ans.append(matrix[j][left])
        
        while left<=right and top <= down:
            printCircle(top,left,down,right)
            top, left, down, right = top+1, left+1, down-1, right-1
            
        return ans
复制代码

Leetcode103 二叉树的锯齿形层次遍历

Leetcode25 K 个一组翻转链表

找出第一个缺失的正整数

  • 输入的正整数有n个的话，第一个缺失的正整数一定是在[1,n+1]这个区间里
  • 扫描列表，记录[1,n+1]的出现状况
  • 扫描数组，找到[1,n+1]中第一个没有出现的数

rand(1, 5)实现rand(1, 7)

  • 调用两次rand5，生成1~25种组合
  • 对1~21，使用%7+1，输出结果
  • 否则，拒绝采样，重头再来一遍

7.2 大数据量

10亿个无序整数找出中位数。

由于是 10 亿个整数，因此无法在内存中处理。也就是说要采用合适的外排序算法。 这里可以使用桶排序，使用 n 个区间均匀的桶，遍历一遍整数，将它们存入对应区间的桶中，并统计桶中数字个数。这样就可以找到中位数所在的桶，如果桶中数字还是很多，再进行桶排序，否则进内存中排序即可。

内存只能存1000条数据。如何对5000条数据进行排序?

  • 5k条分为5组，每组1k条
  • 每组分别读入内存，排序后写入硬盘
  • 从5组的每组中读入前200条，每次5选1，写入硬盘。当一组中的200条排完后，再从读该组200条，直到排序完成。

10万个ip，求出现频率最高的10个IP

  • 先哈希分组成多个小文件
  • 在每个小文件中求出现频率最高的10个IP
  • 计算全局的频率最高的10个IP

1000 亿个无符号整数，找最大的 100 个

内存不够的情况下用什么方案？内存充足的情况下呢？ partition 的方案不稳定，有什么稳定的方法吗？

  • 内存不够堆排序（建立一个k=100大小的小顶堆，然后遍历数据，有大于根结点的值将堆根节点替换上）他说时间复杂度呢，我说 N * log K。
  • 内存够用计数排序（无符号整数就那么多，1000亿肯定有重复的。计数排序的优点是O(n),缺点是内存占用太大。既然内存够用就随便用咯~）
  • 桶排序可以认为是弱化版的计数排序，计数排序是桶的大小为1的桶排序。

7.3 信号量与锁

信号量实现哲学家进餐

  • 方法一：给五个叉子编号为 0-4，每个哲学家必须先拿编号小的叉子。
  • 方法二：允许最多4个哲学家去持有叉子，可保证至少有 1 个哲学家能吃上面。
  • 方法三：让编号为奇数的哲学家先拿左边，编号为偶数的哲学家先拿右边。

三种思路 - 破坏循环等待 - ngcafai - 力扣题解

img

用条件变量实现读写锁

生产者消费者

手撕生产者、消费者模型，10个生产者，10个消费者，队列容量为30个 (下图是不while死循环的生产者消费者, 和原面经有所区别) img

实现阻塞队列

且要求取的时候先取优先级最大的. 我先直接用优先队列，后面面试官让我再实现最大堆.(下方代码并没有实现最大堆)

 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

import threading
class BoundedBlockingQueue(object):	# LeetCode1188
    
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.q = []
        self.con = threading.Condition()


    def enqueue(self, element: int) -> None:
        with self.con:  # 自动acquire,release
            while len(self.q) == self.capacity:   # 满
                self.con.wait()
            self.q.append(element)
            self.con.notify()

    def dequeue(self) -> int:
        with self.con: 
            while len(self.q) == 0:  # 空
                self.con.wait()
            ans = self.q.pop(0)
            self.con.notify()
            return ans
        

    def size(self) -> int:
        return len(self.q)
复制代码

8 智力题

这里是我千辛万苦攒的智力题，后来面试一个智力题都没问，好气 (= _=)

小白鼠喝毒药

1000瓶水，有一瓶是毒药，你有无限只小白鼠，喝了毒药一小时后毒发，怎样在一个小时内知道哪瓶水有毒？最少要用多少只小白鼠？1000瓶药水，1瓶有毒药，几只小白鼠能够找出？ - 温笛的文章 - 知乎

这道题考察的是对2进制的理解。

  • 鼠1: 喝个位编号为1的瓶子，鼠2：喝十位编号为1的瓶子……
  • 如鼠1死了，鼠2没死，鼠3死了，那么就是101=5号瓶子有毒。那么就是101=5号瓶子有毒。
  • N只老鼠的量程为2^N，1000只瓶子位于2^9 ~ 2^10，即10只小鼠可以测1000瓶水。

如果30分钟就会毒发呢？（可以测2轮）

  • 类比三进制，在对应的位数，第一轮喝1的瓶子，死了填1，第二轮喝2的瓶子，死了填2，两轮都没死就填0.

烧香计时

两根可以烧一小时的香，确定45分钟

  1. A两端点燃，B一端点燃
  2. A烧灭后，B还剩半根香，正常来说还要30分钟烧完
  3. 两端点燃B, 15分钟后烧完

海盗分金币

五个海盗抢来了一百个金币。五个海盗都很贪婪但同时又都很明智。他们按照抽签的方法，排出一个次序。首先由抽到一号签的海盗说出一套分金的方案，如果5个人中有50％以上（不含50％）的人同意，那么便依照这个方案执行，否则这个提出方案的人将被扔到海里喂鱼，接下来再由抽到二号签的海盗继续说出一套方案，然后依次类推到第五个。如果你是抽到一号签的海盗，你计划提出一套什么样的方案，在保住小命的前提下，分得最多的金子？

对于这个问题要采用倒推方法：

  • 如果只剩5号：5号自己独吞所有金币
  • 如果只剩4号和5号：5号一定投反对票让4号喂鲨鱼，以独吞全部金币。这种情况对4号是死局。
  • 如果只剩3，4，5号：3号自己有一票，只需要再争取1票即可通过。如果3号的方案通不过，就会变成两个人的情况。对4号是死局，对5号是利好。4号不需要金钱也会支持三号。分配方案：“100，0，0”
  • 如果剩2，3，4，5号：2号自己有一票，需要争取2票即可通过。如果2号的方案通不过，就会变成3个人的情况。对3号是利好，对4号是获得0个金币，对5号是获得0个金币。因此2号可以通过 “98，0，1，1” 拉拢4号5号。
  • 如果剩1，2，3，4，5号：1号自己有一票，需要争取2票即可通过。如果1号的方案通不过，就会变成4个人的情况。对2号是利好，对3号是0个金币，对4号是1个金币，对5号是1个金币。因此1号可以通过（97，0，1，2，0）或（97，0，1，0，2）拉拢3号，和4或5号。
  • 如果剩0，1，2，3，4，5号(自己加的)：0号自己有一票，需要争取3票即可通过。如果0号的方案通不过，就会变成5个人的情况。对1号是利好，对2号是0个金币，对3号是1个金币，对4号是2个或0个金币，对5号是2个或0个金币。因此1号可以通过（95，1，2，2，0）拉拢2,3,4号，或（95，1，2，0，2）拉拢2,3,5号。

老虎吃羊

100只老虎可以靠吃草活下来，但是它们更喜欢吃羊。每次只有一头老虎可以吃羊，但是吃了羊的那头老虎也会变成羊。假设所有老虎都很聪明，首先考虑保命然后再考虑吃羊，问羊是否会被吃？

  • 1只老虎的时候：果断吃羊
  • 2只老虎的时候：不能吃，不然自己就变成了1只老虎的情况里的那只羊
  • 3只老虎的时候：吃。吃羊后会变成2只老虎的情况，而两只老虎的情况不吃羊。

以此类推，偶数只老虎的话，羊不会被吃，奇数只的话羊会被吃

螺丝与螺母

赛马

25匹马5个跑道。每场比赛每个跑道只允许一匹马，每次只能记录名次不能记录时间，不存在并列。问最少比多少次能选出最快的3匹马？ 赛马64匹马，8个赛道，求前四名最少次数。面试官提示有的情况是11次，有的情况是10次。 腾讯算法面试——赛马问题 - 一帆诗的文章 - 知乎

12个球，一个质量不一样，最多称三次，如何称

神级通解：N 个乒乓球中有一个和其他的质量不同，用天平最少几次一定能称出来？ - 知乎

分为3组，记为{1，2，3，4}，{5，6，7，8}，{9，10，11，12}

  • [第一次]先称前两组，如果重量相同，我们知道8一定是正常球。然后[第二次]称{9，10}，{8，11}。
    1. 若重量相同，说明9,10,11都是正品，12是次品。[第三次]把12和1称一下即可判断是轻了还是重了。
    2. {9，10}重，则9或10重,或者11轻。[第三次]比较9和10：如果一样则11轻，否则那个重的就是次品。
    3. {9，10}轻，则9或10轻,或者11重。[第三次]比较9和10：如果一样则11重，否则那个轻的就是次品。
  • 如果前两组中，{1，2，3，4}重，则1-4中有某个重或者5-8某个轻。我们知道9-12都是正常球。[第二次]比较{1，2，5}(2个第一组的，1个第二组的)和{3，6，9}(第1,2,3组各一个)
    1. {1，2，5}重: 可能是1重或2重，或者6轻。[第三次]这时比较1、2，若不一样重，重的是次品。若一样重，6是次品。
    2. 一样重：说明1,2,5,3,6,9都是正常球。4重，或者7轻或8轻，[第三次]比较7，8。
    3. {1，2，5}轻：说明5轻或者3重，[第三次]比较3（或者5）和一个正常地即可（比如9）c)
  • 如果前两组中，{5，6，7，8}重，同{1，2，3，4}重的情况分析。

A中5个球，B中7个球，甲乙两个人每次至少取一个球，且只能取同一个箱子的球。取到最后一个球的人输。问先手是否有必胜策略？

  • 有。这个题就是手工dp。a,b<=1时分析很简单，略。 在a=b,a>=2的时候先手会输，其余时候先手必胜。

9 数学题

三门问题

有三个盒子，其中一个有奖品，参与者选中一个后，主持人打开另一个盒子没有奖品，问参与者是否换盒子，换与不换的中奖概率是？

给一个函数g，g以p的概率输出1，以1-p的概率输出0，设计一个函数f以等概率的情况输出0和1

拒绝采样法 ：调用两次g, 如果结果是0/1，输出0，结果是1/0输出1，结果是1/1或者0/0则再重新算一次。

一个圆内随机三个点刚好在一个半圆的概率

圆内任取三点/四点在同一半圆内的概率是多少？ - 心月狐的回答 - 知乎 灵感： 在圆周上随机取三个点，形成锐角三角形、直角三角形、钝角三角形的概率分别为？ （答案：1/4 0 3/4）其实钝角三角形就是在同一个半圆上。

最后 点个赞再走呗 (≧▽≦)/ [疯狂暗示][疯狂暗示][疯狂暗示]

作者：铃离 链接：https://juejin.cn/post/6901683754851532813

链接：https://juejin.cn/post/6901692006465011719

来源：掘金 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。