面试

反转链表 题目 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...

LRU缓存机制 题目 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。 ...

平衡二叉树 题目 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 3 / \ 4 4 返回 false 。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/balanced-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ...

验证二叉搜索树 题目 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 ...

在排序数组中查找元素的第一个和最后一个位置 题目 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 ...

最大子序和 题目 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 1 2 3 4 5 6 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 ...

加一 题目 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以零开头。 ...

K 个一组翻转链表 题目 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 ...

合并两个有序链表 题目 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 1 2 3 4 示例： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 来源：力扣（LeetCode） ...

有效的括号 题目 给定一个只包括 (，)，{，}，[，] 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 ...

两数之和 题目 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 ...

三数之和 题目 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 ...

105. 从前序与中序遍历序列构造二叉树 描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： ...

查找 折半查找 复杂度：O(logn) 对象：排序的数组 内容： 设置高低指针 中间开始，如果值相等则结束 值不相等，高低指针向中间迫近 指针相遇，结束 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 func BinarySearch(arr []int, goal int) int { // 取高低索引 low, high := 0, len(arr)-1 // 指针未相遇的时候循环 for low <= high { mid := low + (high-low)>>1 midV := arr[mid] // 符合条件，返回索引 if midV == goal { return mid } // 不符合条件，高低指针向中间迫近 if midV < goal { low = mid + 1 } else { high = mid - 1 } } return -1 } 排序 快速排序 x s ...

常问问题： 可能会手撕数据库语句，一般是查询，这个看你运气了 一些关键字 四个特性，三个“读”（脏读、幻读、不可重复读）、四个隔离级别、乐观悲观锁、表锁行锁之类的 索引是什么、创建索引原则、索引类型 数据库引擎、底层（B+树）及好处 其余的自己看下面的，多理解几遍就能讲出来了 另外还可能要去了解下主从数据库（读写分离）、分库分表、平滑扩容 相关的大致流程，我下面没写 知识内容 InnoDB和MySAM InnoDB和MySAM 操作性： InnoDB具有事务，支持四个事务隔离级别。 适用于大量INSERT或UPDATE操作。 不支持全文索引，新版本支持。 支持外键 MyISAM管理非事务表 它提供高速存储和检索，以及全文搜索能力。 如果应用中需要执行大量的SELECT查询，那么MyISAM是更好的选择 不支持事务、外键 存储： MyISAM在磁盘上存储成三个文件。表定义 .frm，数据文件.MYD， 索引文件.MYI。跨平台转移麻烦 InnoDB：空间数据文件和它的日志文件，InnoDB 表的大小只受限于操作系统文件的大小 索引： InnoDB（索引组织表）：能缓存索引，也能缓存数据，必须得有主键 MyISAM（堆组织表）：只能缓存索引。非聚类 InnoDB 在做SELECT的时候，要维护缓存数据和索引和其余的，慢一些。MyISAM只缓存索引块 MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。 B+树搜索算法搜索索引-取出data值-以此为地址读取数据记录 主索引要求key是唯一的，而辅助索引的key可以重复 InnoDB也使用B+Tree作为索引结构，数据文件本身就是索引文件。 叶节点data域就是数据记录，称之聚类索引 本身要按主键聚类，所以必须要主键（设置自增主键），没有的话分裂维持特性会十分低效。没指定的话会自动选择合适的或自动生成一个隐含字段。长度为6的长整型 辅助索引data存储的主键值 索引 为了 加快对数据表中的检索而创建的分布存储的数据结构 ...

面试CS基础——操作系统笔记 一、操作系统概述 操作系统四个特性 并发：同一段时间内多个程序执行。并行（同一时刻多个事件）和并发（同一个时间段多个事件） 并发：同一时间段运行多个程序，操作系统通过进程和线程实现 并行：同一时刻运行多个指令，需要硬件支持，流水线、多核、分布式 共享：系统资源可以被内存中的多个并发执行的进程共用 互斥共享（临界资源，比如打印机）和同时共享 虚拟：通过 时分复用（多道程序技术 分时系统）和空分复用（虚拟内存）技术把一个物理实体虚拟为多个实体 时分复用：多进程在一个处理器并发执行，让每个进程轮流占有处理器，用小时间片快速切换 空分复用：虚拟内存，物理内存抽象为地址空间。 地址空间的页不需要全部在物理内存中，若使用到 不在物理内存 的页时，执行页面置换算法，把页置换到内存中 异步：进程是走走停停的方式执行的，以一种不可预知的速度推进 操作系统主要功能 进程管理：进程控制、进程同步、进程通信、死锁处理、处理机调度 内存管理：内存分配、地址映射、内存保护和共享、虚拟内存 文件管理：存储空间、目录、读写管理和保护 设备管理：处理用户的IO请求、缓冲管理、设备分配、设备管理等 中断和轮询 轮询 早期计算机系统对 I/O 设备的管理方式。 ...

计算机网络 OSI模型 应用层（数据）：确定进程之间通信的性质以满足用户需要以及提供网络与用户应用 表示层（数据）：主要解决拥护信息的语法表示问题，如加密解密 会话层（数据）：提供包括访问验证和会话管理在内的建立和维护应用之间通信的机制，如服务器验证用户登录便是由会话层完成的 传输层（段）：实现网络不同主机上用户进程之间的数据通信，可靠与不可靠的传输，传输层的错误检测，流量控制等 网络层（包）：提供逻辑地址（IP）、选择最佳路径，数据从源端到目的端的传输 数据链路层（帧）：将上层数据封装成帧，用 MAC 地址访问媒介，错误检与修正 物理层（比特流）：设备之间比特流的传输，物理接口，电气特性等 在TCP/IP五层中，123层对应应用层 ...