笔试知识点
Hbase
HBase是一个分布式的、面向列的开源数据库。
题目来源于：https://www.cnblogs.com/cxchanpin/p/7381890.html
HBase来源于哪篇博文？ C
A. The Google File System
B. MapReduce
C. BigTable
D. Chubby
下对HBase的描写叙述哪些是正确的？ B、C、D
A. 不是开源的
B. 是面向列的
C. 是分布式的
D. 是一种NoSQL数据库
HBase依靠（）存储底层数据 A
A. HDFS
B. Hadoop
C. Memory
D. MapReduce
HBase依赖（）提供消息通信机制 A
A. Zookeeper
B. Chubby
C. RPC
D. Socket
HBase依赖（）提供强大的计算能力 D
A. Zookeeper
B. Chubby
C. RPC
D. MapReduce
MapReduce与HBase的关系，哪些描写叙述是正确的？ B、C
A. 两者不可或缺。MapReduce是HBase能够正常执行的保证
B. 两者不是强关联关系，没有MapReduce，HBase能够正常执行
C. MapReduce能够直接訪问HBase
D. 它们之间没有不论什么关系
以下哪些选项正确描写叙述了HBase的特性？ A、B、C、D
A. 高可靠性
B. 高性能
C. 面向列
D. 可伸缩
以下与Zookeeper类似的框架是？D
A. Protobuf
B. Java
C. Kafka
D. Chubby
Kafka是一个高吞吐量分布式消息系统。kafka的数据仅仅会顺序append。数据的删除策略是累积到一定程度或者超过一定时间再删除。Kafka还有一个独特的地方是将消费者信息保存在client而不是MQserver。这样server就不用记录消息的投递过程，每一个client都自己知道自己下一次应该从什么地方什么位置读取消息。消息的投递过程也是采用client主动pull的模型，这样大大减轻了server的负担。Kafka还强调降低数据的序列化和拷贝开销，它会将一些消息组织成Message Set做批量存储和发送，而且client在pull数据的时候，尽量以zero-copy的方式传输。利用sendfile（相应java里的 FileChannel.transferTo/transferFrom）这种高级IO函数来降低拷贝开销。可见，kafka是一个精心设计，特定于某些应用的MQ系统，这种偏向特定领域的MQ系统我预计会越来越多，垂直化的产品策略值的考虑。
Chubby首先是一个分布式的文件系统。Chubby可以提供机制使得client可以在Chubby service上创建文件和运行一些文件的基本操作。说它是分布式的文件系统，是由于一个Chubby cell是一个分布式的系统。一般包括了5台机器，整个文件系统是部署在这5台机器上的。
从更高一点的语义层面上，Chubby是一个 lock service。一个针对松耦合的分布式系统的lock service。所谓lock service，就是这个service可以提供开发者经经常使用的“锁”，“解锁”功能。通过Chubby，一个分布式系统中的上千个client都可以 对于某项资源进行“加锁”，“解锁”。
那么，Chubby是如何实现这种“锁”功能的？就是通过文件。Chubby中的“锁”就是文件。在上例中，创建文件事实上就是进行“加锁”操作，创建文件成功的那个server事实上就是抢占到了“锁”。用户通过打开、关闭和读取文件。获取共享锁或者独占锁； 而且通过通信机制，向用户发送更新信息。
综上所述。Chubby是一个lock service。通过这个lock service能够解决分布式中的一致性问题。而这个lock service的实现是一个分布式的文件系统。
以下与HDFS类似的框架是？C
A. NTFS
B. FAT32
C. GFS (也是分布式文件系统，谷歌自己的分布式文件系统)
D. EXT3
以下哪些概念是HBase框架中使用的？A、C
A. HDFS
B. GridFS
C. Zookeeper
D. EXT3
HFile
HFile是HBase存储数据的文件组织形式
HFile数据格式中的Data字段用于（）。A
A. 存储实际的KeyValue数据
B. 存储数据的起点
C. 指定字段的长度
D. 存储数据块的起点
HFile数据格式中的MetaIndex字段用于（）。D
A. Meta块的长度
B. Meta块的结束点
C. Meta块数据内容
D. Meta块的起始点
HFile数据格式中的Magic字段用于（）。A
A. 存储随机数，防止数据损坏
B. 存储数据的起点
C. 存储数据块的起点
D. 指定字段的长度
- HFile数据格式中的KeyValue数据格式，下列选项描写叙述正确的是（）。A、D
A. 是byte[]数组
B. 没有固定的结构
C. 数据的大小是定长的
D. 有固定的结构
HFile数据格式中的KeyValue数据格式中Value部分是（）。C
A. 拥有复杂结构的字符串
B. 字符串
C. 二进制数据
D. 压缩数据
HBase中的批量载入底层使用（）实现。A
A. MapReduce
B. Hive
C. Coprocessor
D. Bloom Filter
HBase性能优化包括以下的哪些选项？A、B、C、D
A. 读优化
B. 写优化
C. 配置优化
D. JVM优化
HBase构建二级索引的实现方式有哪些？ A、B
A. MapReduce
B. Coprocessor
(HBase在0.92之后引入了协处理器(coprocessors)，实现一些激动人心的新特性：可以轻易建立二次索引、复杂过滤器(谓词下推)以及訪问控制等)
C. Bloom Filter
D. Filter
关于HBase二级索引的描写叙述。哪些是正确的？A、B
A. 核心是倒排表
B. 二级索引概念是相应Rowkey这个“一级”索引
C. 二级索引使用平衡二叉树
D. 二级索引使用LSM结构
下列关于Bloom Filter的描写叙述正确的是？A、C
A. 是一个非常长的二进制向量和一系列随机映射函数
B. 没有误算率
C. 有一定的误算率
D. 能够在Bloom Filter中删除元素
HBase官方版本号能够安装在什么操作系统上？A、B、C
A. CentOS
B. Ubuntu
C. RedHat
D. Windows
HBase虚拟分布式模式须要（）个节点？A
A. 1
B. 2
C. 3
D. 最少3个
HBase分布式模式最好须要（）个节点？C
A. 1
B. 2
C. 3
下列哪些选项是安装HBase前所必须安装的？A、B
A. 操作系统
B. JDK
C. Shell Script
D. Java Code
解压.tar.gz结尾的HBase压缩包使用的Linux命令是？A
A. tar -zxvf
B. tar -zx
C. tar -s
D. tar -nf
- 从Hadoop 2.7.3 版本开始，HDFS中Block size 的默认大小为128MB.
SQL面试题
https://www.cnblogs.com/huolong-blog/p/7603454.html
触发器的作用？
触发器是一种特殊的存储过程，主要是通过事件来触发而被执行的。它可以强化约束，来维护数据的完整性和一致性，可以跟踪数据库内的操作从而不允许未经许可的更新和变化。可以联级运算。如，某表上的触发器上包含对另一个表的数据操作，而该操作又会导致该表触发器被触发。
什么是存储过程？用什么来调用？
存储过程是一个预编译的SQL语句，优点是允许模块化的设计，就是说只需创建一次，以后在该程序中就可以调用多次。如果某次操作需要执行多次SQL，使用存储过程比单纯SQL语句执行要快。可以用一个命令对象来调用存储过程。
索引的作用？和它的优点缺点是什么？
索引就一种特殊的查询表，数据库的搜索引擎可以利用它加速对数据的检索。简单地说，索引是一个数据结构，用来快速访问数据库表格或者视图里的数据。它很类似与现实生活中书的目录，不需要查询整本书内容就可以找到想要的数据。索引可以是唯一的，创建索引允许指定单个列或者是多个列。缺点是它减慢了数据录入的速度，同时也增加了数据库的尺寸大小。
什么是事务？什么是锁？
事务就是被绑定在一起作为一个逻辑工作单元的SQL语句分组，如果任何一个语句操作失败那么整个操作就失败，以后操作就会回滚到操作前状态，或者是上个节点。为了确保要么执行，要么不执行，就可以使用事务。要将有组语句作为事务考虑，就需要通过ACID测试，即原子性，一致性，隔离性和持久性。
锁：在所有的DBMS中，锁是实现事务的关键，锁可以保证事务的完整性和并发性。与现实生活中锁一样，它可以使某些数据的拥有者，在某段时间内不能使用某些数据或数据结构。
什么叫视图？游标是什么？
视图是一种虚拟的表，具有和物理表相同的功能。可以对视图进行增，改，查，操作，视图通常是有一个表或者多个表的行或列的子集。对视图的修改不影响基本表。它使得我们获取数据更容易，相比多表查询。
游标：是对查询出来的结果集作为一个单元来有效的处理。游标可以定在该单元中的特定行，从结果集的当前行检索一行或多行。可以对结果集当前行做修改。一般不使用游标，但是需要逐条处理数据的时候，游标显得十分重要。游标用于定位结果集的行。
算法工程师能力评估（牛客）
解析：
解析：
B树相关知识见这里
- 具有3个结点的二叉树有几种形态？
解析：
这是组合计数问题，最常见的catalan数，C(n)=(1/(n+1))*((2*n)!/(n!*n!))
3个节点详细如图： 
- 已知一棵二叉树前序遍历和中序遍历分别为
ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为多少？
解析：
前序遍历确定根节点，中序遍历确定左右子树。
- 已知数据表A中每个元素距其最终位置不远，为节省时间排序，应采用什么方法排序？
解析：
插入排序：如果平均每个元素离最终位置相距c个元素，则其复杂度为O(cn)，一共n趟，每次比较c次；
快速排序：最好的、平均的复杂度都是O(nlog(n))，如果每次选择的中间数都最小或最大，那就是最坏的情况，复杂度是O(n*n)；所以快速排序和元素的位置没有关系，跟选择的中间数有关。
堆排序：复杂度一直是O(nlog(n));
直接选择排序：跟元素位置没有关系，都要遍历n遍，每遍找出最小或最大数来，复杂度是O(n*n)；
答案是插入排序。
- 将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为()?
解析：
解析：这个是卡特兰数的经典应用，但是这个问题不是一两句话能说得清的。
可采取代入法，n=1或n=2代入，均可得到正确答案。
- T(n) = 25T(n/5)+n^2的时间复杂度？
解析：Master Theorem
- 连续自然数之和为1000的共有几组？（m，n都为自然数，单独1个数也算作“连续自然数”）
解析：
解析：
- 写出a*(b-c*d)+e-f/g*(h+i*j-k)的逆波兰表达式。
- 下列关于线性表，二叉平衡树，哈希表存储数据的优劣描述错误的是？
解析：在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的，所以可能需要通过一次或多次树旋转来重新平衡这个树。
解析：
- 如果一个堆栈的入栈序列是A,B,C,D,E,则堆栈的不可能输出顺序是（）。
- 若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（）。
解析：
解析：
- 设某颗二叉树中有360个结点，则该二叉树的最小高度是？(包括根节点)
解析：
其他
时间序列模型中，哪一个模型可以较好的拟合波动性的分析和预测 (D)
A. AR模型
B. MA模型
C. ARMA模型
D. GARCH模型
解析：
参考 https://blog.csdn.net/s1491695565/article/details/52093003
时间序列中常用预测技术 一个时间序列是一组对于某一变量连续时间点或连续时段上的观测值。
1. 移动平均法 (MA)
1.1. 简单移动平均法
设有一时间序列y1,y2,..., 则按数据点的顺序逐点推移求出N个数的平均数，即可得到一次移动平均数.
1.2 趋势移动平均法
当时间序列没有明显的趋势变动时，使用一次移动平均就能够准确地反映实际情况，直接用第t周期的一次移动平均数就可预测第t+1周期之值。
时间序列出现线性变动趋势时，用一次移动平均数来预测就会出现滞后偏差。修正的方法是在一次移动平均的基础上再做二次移动平均，利用移动平均滞后偏差的规律找出曲线的发展方向和发展趋势，然后才建立直线趋势的预测模型。故称为趋势移动平均法。
2. 自回归模型(AR)
AR模型是一种线性预测，即已知N个数据，可由模型推出第N点前面或后面的数据（设推出P点）.
本质类似于插值，其目的都是为了增加有效数据，只是AR模型是由N点递推，而插值是由两点（或少数几点）去推导多点，所以AR模型要比插值方法效果更好。
3. 自回归滑动平均模型(ARMA)
其建模思想可概括为：逐渐增加模型的阶数，拟合较高阶模型，直到再增加模型的阶数而剩余残差方差不再显著减小为止。
4. GARCH模型
回归模型。除去和普通回归模型相同的之处，GARCH对误差的方差进行了进一步的建模。特别适用于波动性的分析和预测。
4. 指数平滑法
移动平均法的预测值实质上是以前观测值的加权和，且对不同时期的数据给予相同的加权。这往往不符合实际情况。
指数平滑法则对移动平均法进行了改进和发展，其应用较为广泛。
基本思想都是：预测值是以前观测值的加权和，且对不同的数据给予不同的权，新数据给较大的权，旧数据给较小的权。
根据平滑次数不同，指数平滑法分为：一次指数平滑法、二次指数平滑法和三次指数平滑法等。
下面对集成学习模型中的弱学习者描述错误的是 (C)
A. 他们经常不会过拟合
B. 他们通常带有高偏差，所以其并不能解决复杂学习问题
C. 他们通常会过拟合
弱学习器：略优于随机猜测的学习器。（西瓜书）
xgboost对缺失值的处理方法：
把缺失值分别放到左叶子节点和右叶子节点中，计算增益。哪个增益大就放到哪个叶子节点。
- Hive四大表类型：
- 内部表
- 外部表
- 分区表
- 桶表（或叫分桶表）
能在O(1)时间内访问线性表的第i个元素的结构是 ( )
只要数据元素保持有序，则查找时就可以采用折半查找方法 ( )
一个长度为32的有序表，若采用二分查找一个不存在的元素，则比较次数最多是 ( )
分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。( )
下列说法中错误的是( )
A. 插入排序某些情况下复杂度为O(n)
B. 排序二叉树元素查找的复杂度可能为O(n)
C. 对于有序列表的排序最快的是快速排序
D. 在有序列表中通过二分查找的复杂度一定为O(logn)
答案：C
解析：
C选项应该为插入排序？
在长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（假定查找每个元素的概率均相等）为（）
折半查找与二元查找树的时间性能在最坏的情况下是相同的 ( )
使用KMP算法在文本串S中找m模式串P是一种常见的方法。假设S=P={xyxyyxxyx}，亦即将S对自己进行匹配，匹配过程中正确的next数组是( )
解析：参考 https://blog.csdn.net/qq_37969433/article/details/82947411
排序
基选归堆不变（运行时间不发生变化，与初始状态无关）
快选希堆不稳（是不稳定的排序）
已给图，( )是该图的正确的拓扑排序序列
在用邻接表表示图时，拓扑排序算法时间复杂度为( )
解析：
下面的排序方法中，关键字比较次数与记录的初始排序无关的是( )
解析：
基选归堆不变（运行时间不发生变化，与初始状态无关）
下列排序算法不稳定的有 ( )
快选希堆不稳（是不稳定的排序）
下列说法错误的是( )
解析：
解析：
以下来源于百度百科：
基数排序：最低位优先(Least Significant Digit first)法，简称LSD法：
下列排序算法中，( ) 在某趟排序结束后不一定能选出一个元素放到其最终位置上
解析：
选 择 排 序 (Selection sort)： 是 一 种 简 单 直 观 的 排 序 算 法 。 它 的 工 作 原 理 是 每 一 次 从 待 排 序 的 数 据 元 素 中 选 出 最 小 （ 或 最 大 ） 的 一 个元 素 ， 存 放 在 序 列 的 起 始 位 置 ， 直 到 全 部 待 排 序 的 数 据 元 素 排 完 ，所 以 每 一 趟 选 择 的 元 素 都 会 放 在 他 的 最 终 位 置
冒 泡 排 序 ：它 重 复 地 走 访 过 要 排 序 的 数 列 ， 一 次 比 较 两 个 元 素 ， 如 果 他 们 的 顺 序 错 误 就 把 他 们 交 换 过 来 。 走 访 数 列 的 工 作 是 重 复 地 进 行 直 到 没 有 再 需 要 交 换 ， 也 就 是 说 该 数 列 已 经 排 序 完 成 。 比 如 按 照 升 序 排 序 则 每 一 趙 会 将 前 面 未 排 序 部 分 的 最 大 的 往 后 交 换 到 已 排 序 的 最 前 面 ， 为 其 最 终 位 置
堆 排 序 ：如 果 要 求 升 序 则 建 立 大 根 堆 ， 降 序 则 建 立 小 根 堆 ， 堆 顶 元 素 为 最 大 或 者 最 小 的 元 素 ， 将 这 个 元 素 与 最 后 一 个 位 置 的 元 素 交 换 ， 再 将 剩 余 元 素 还 原 成 大 小 跟 堆 ， 每 一 趙 都 会 选 出 一 个 未 排 序 中 的 最 大 或 者 最 小 放 大 他 的 最 终 位 置
希 尔 排 序： 由 于 是 按 照 增 量 排 序 ， 步 长 不 同 可 能 元 素 不 一 定 到 他 最 终 位 置 ， 所 以 选 C
解析：
下面( )排序算法在输入数据逆序情况下排序速度最快
对于基本有序的序列，按照哪种排序方式最快：
解析：
解析：
