算法题

1.最大子序列和（Leetcode原题）（多次考，记得看哦）
2.最大序列乘积（依旧原题）：和上一道题一样用动态规划
3.反转单链表，引申（多次考）
（1）内存泄漏的问题，对象在堆上分配还是栈上？/会不会内存泄漏？
（2）然后开始写测试用例：考虑一下分支覆盖和环形链表就行。 顺着问了环形链表怎么
解决：快慢指针， 然后问可以边反转边检测环形链表
4.写个函数就是删掉一个字符串中的所有IP地址
5.通配符模式的匹配（Leetcode原题，做过...不过最优的解法忘了记得当时做的时候
看了好久才看懂dp的做法）
6.优先级队列（堆）
7.给一个n*n的矩阵，要求在原矩阵的基础上对该矩阵进行顺时针90度的旋转，不能新
生成一个矩阵。（多次考）
8.topk问题（多次遇到）（堆实现）
9.实现一个round函数
10.模拟，给一种字符串加密方法，加密过程是把一个串不断左右左右移动： abcde =>
dbace，你需要写一个还原函数，简单模拟，注意长度 奇数偶数分开讨论。。O(n)
解决。。但是可以常数小一点。。
11.给一个森林（数组形式），每个树有个高度，现在我要选一个高度，高于这个高度的
树木会被砍下，我只砍一次，在给定个目标树木和target, 要求看下的树木之和在
= target 基础上尽可能小，求最接近的答案
简单的二分。。。 O(n) check... 但是据说。。计数排序可以O(n)排序树
木。。。 一旦有序。。记录后缀和然后再二分中套个二分就可以让时间复杂度变成
O(n + log(n) * log(n) )。。
12.把中文数字转化为阿拉伯数字， 比如 一百零一 =》 101， 二零一九 =》 2019
，分两种情况。。第一种情况就是纯数字。 check下字串。不带 百、十、万，只包
含一、二、三。。。这样的，直接暴力处理。第二种情况就是代表一个有大小的数字：
三种解法：
O( n * log(n) ) ： 直接暴力递归， 每次找当前串中最大的部分 然后划分左右
部分，左边计算完乘以中间最大值再加上右边部分， 当当前串长度为1特判。零也要特
判，（比如一百零一里的零其实没啥特殊意义）
O( n ) : 单调栈从左到右扫一遍， 出栈时特殊处理一下，把栈顶元素累加到当前值
上，最后再把当前值入栈，结果就是栈内元素累加和。
O( n ) 空间复杂度小一点的 ： 从右到左去扫，记录最大值，累加。。。
13.给定年月日求该日是这一年的第几天
14.给定一系列日程（起始时间和终止时间），设计数据结构，如何寻找是否有日程冲突
（就简单排了序，按顺序找是否有overlap）
15.在时间复杂度O(log(m+n))的要求下寻找两个有序数组合并后的中位数；
16.给定一个手机上电话拨号排列，从0开始跳格子，每次都只能跳23矩阵的对角线，如
0只能跳到4或6，问从0开始跳几次刚好到达数字1，有多少种方式可以跳到1.
17.构建一个put函数，给key和value值，要保证放入put函数的key是顺序排列的，实
现键值对的覆盖和插入，当某个value值为delect时，若此时有一个key值是排在
其前后位置的value插入，则此时可以将这个value值替换delect。
18.找出一个数组中和为target两个数的索引
19.找出一个数组里和为0的三元组
20.一个二叉树是否是二叉搜索树
21.最长递增子序列。
22.二叉树中任意两点形成的路径上节点（每个节点有个值）之和的最大值。
23.中序遍历二叉树，递归和非递归分别怎么写
24.分布式日志系统要考虑哪些因素，怎么衡量性能
25.拓扑排序
26.给定一个字符串，判断是否是有效的IP地址，（提示，有效的IP地址格式是
xxx.xxx.xxx.xxx, xxx在0-255之间）（输入不保证都是这种格式，要自己判
断，同时001这种是否有效要问面试官）
27.给定一个字典，字典中有一些单词，然后给一个target的字符串，如果
targetString能被字典中的单词组合起来，就输出true，否则输出false。
我就从一开始的暴力搜索来考虑，时间复杂度是O（n2），后来优化；一下时间复
杂度是O(mn), m 是target的长度。
然后面试官就给了一些提示，比如dictionary是有contains方法的，类似于
hashmap，然后还有怎么降低空间复杂度，比如维护一个index就可以。
这道题跟面试官交互了很长时间，最终把思路捋了清楚，但是code还是没写出来。
28.判断一个数组是不是二叉搜索树后续遍历，leetcode原题
29.给一个不含重复元素的数组，如果该数组满足下面两个条件中的任意一个，就返回true，否则返回false；
条件1：如果在该数组中可以找到两个数字使得交换这两个数字后的整个数组变为升序，那么该条件满足。
条件2：如果该数组中可以找到一个连续的子数组使得反转这个子数组后整个数组变为升序，那么该条件满足。（多次）
30.现在有一个M*N的点阵，问从左下角走到右上角的最短路径一共有多少条。只能上下左右移动。没有障碍。Cm+n-2 n-1条路径
31.一个矩阵，每一行从左到右递增，每一列从上到下递增，给一个值，判断这个值是否在矩阵中（剑指offer原题）。面试官后面要求用binary search做。问了下时间复杂度。（多次）
32.判断一颗二叉树是不是平衡二叉树
33.(1)若有一个数组有100w个数，0＜=i＜j＜len，求从下标i到下标j的子数组的和。
(2)若更改了ij之间下标k的数，arr[k]=num，接着求子数组的和，要求时间复
杂度空间复杂的O(logn)
34.力扣76题
35.力扣79
36.力扣 124

操作系统

1.内核态和用户态的区别？
2.什么时候会陷入内核态？
3.c访问空指针会不会陷入内核态？
4.介绍线程和进程

数据库

1.数据库迁移的问题，讲的是先关闭服务，然后再导出导入sql文件；进阶又问我如何在
线实现数据库迁移

网络

1.http和https的区别

java基础

1.GC、运行时栈帧、与C++相比有何不同等。