手头上有一份比较有意思的笔试题，基本分为三个模块（编程能力，图像处理，模式识别），最近陆陆续续在整理其中的知识点和编程题，耗时有点久，但是应该会有点收获吧…
图像处理
图像滤波
- 均值滤波：在滤波器覆盖范围内，所有值求平均为目标像素的值；
- 中值滤波：在滤波器覆盖区域中从小到大排序，取中间值为滤波器的目标像素值；
- 还有其他一些有趣的滤波器，见REF
REF: 滤波
图像直方图
- 统计直方图：统计图片所有像素值，得到统计直方图；
- 累积直方图：很多时候，统计直方图在很多像素值都得到0, 从而影响了后续的计算，例如计算两个图片的相似性，直方图的稀疏性会对相关系数产生较大影响。这时候有两种方案，一种是多个像素值量化称为一个值，另一种就是实用累积直方图，累积直方图的每一个维度的值为
bin(x) = num(p<x),即数字一直累积到最后一个像素值。
插值
- 最邻近插值：顾名思义，最邻近插值就是对于某个目标图像像素点，从原图中根据缩放的比例找到最邻近的一个值，插入到目标图像。当计算原图坐标得到浮点数的时候，直接四舍五入取最近。
scale_x = src.cols / dst.cols
scale_y = src.rows / dst.rows
sx = round(x * scale_x)
sy = round(y * scale_y)
dst(x,y) = src(sx, sy)
但是这个插值方法是由很大缺点的，缺点来自于粗暴的四舍五入。
i.e.
src dst dst
1 2 3 ? ? ? ? 1 2 3 3
4 5 6 -> ? ? ? ? -> 4 5 6 6
7 8 9 ? ? ? ? 7 8 9 9
? ? ? ? 7 8 9 9
- 双线性插值 与最邻近不同，当取原图坐标得到的是浮点数，双线性插值法就会以这个浮点坐标周边的四个像素点的值加权平均得到目标图像的像素值。举出一个比上面的例子更简单的矩阵方便理解。
i.e.
src dst dst
1 2 ? ? ? 1 1.5 2
3 4 -> ? ? ? -> 2 2.5 3
? ? ? 3 3.5 4
1）值为2.5的元素映射到源图矩阵中是坐标(0.5,0.5)，
2）首先从一个方向线性插值（例如从x方向线性插值得到1.5和3.5）
3）然后纵向线性插值得到2.5。
大概意思就如上述例子，目标像素值由映射到原图的浮点坐标周边的四个值根据浮点坐标作为权重计算。
REF：双线性插值
注意：做插值的时候，有一个情况需要想清楚想明白 — 如果输入图像比较大，而目标输入图像比较小，则上述的双线性插值实际上并不是真正的“双线性插值”，因为映射到原图的像素点过于离散，反而更接近于“最邻近插值”，或者说是一种混搭…
仿射变换
二维图像的仿射变换矩阵实际上完全由下面的2*3的矩阵决定
s * cos, s * sin , t1
s * -sin, s * cos , t2
其中s的缩放比例，cos和sin的角度决定了旋转，然后t1和t2决定了x方向和y方向的平移。
模式识别
这个部分有不少概念性的内容，即使当前机器学习的主流已经渐渐迁移到Deep Learning，很多DL的学生已经不怎么关注一些传统的机器学习方法。但是DL方法实际上很多概念还是和非DL方法一致的。
特征降维
在很多应用场景中，数据的形式是多种多样的，其特征的维度也是各不相同的，当实际问题中遇到很高的维度时，常常需要降低维度，一方面便于计算和可视化，一方面有效的提取有用的信息同时摒弃无用信息。
例如，现在对两位美女进行特征刻画从而考虑是否主动去搭讪。特征有五个维度：“眼睛好看”，”眉毛好看“，”鼻子好看“，”嘴巴好看“，”耳朵好看“，“谈吐优雅”，“能歌善舞”，“心地善良”，“孝顺顾家”，“乐观开朗”，可以量化为一个十维的向量。美女A特征为[1,1,1,1,0,1,1,1,1,0],美女B[1,1,0,1,1,0,1,1,1,1],那么两位美女都可以分类为“赶紧去认识”的一类。那么，通过对特征进行降维，例如特征变为两个维度，“内在美”和“外在美”,那么美女A和美女B同样都是内外兼备从而要赶紧去认识，所以不会影响分类性能，但是降低了特征的维度到原来的五分之一。
至于如何实现降维呢？后续的部分就有一些常用方法的介绍。
Bayes决策
根据贝叶斯公式计算出某个条件概率，然后基于计算出来的概率决策分类。这个就不再自己写了，找了一个带有例子的博客
REF：贝叶斯决策 实例
另外，李航老师那本《统计学习》也有一个简单易懂的例子。
PCA
LDA（线性判决分析）
REF：LDA
K-Means聚类
核函数
EM算法
SVM
最邻近法
最邻近方法，或者说K邻近方法，思想上非常简单，就是对于样本的类别估计取决于附近的K个样本的类别。当K==1的时候，就是“最”邻近…
举个简单的例子,现在有一个二维的向量空间，反映的是身高体重(假设两个变量独立？[哭笑])，存在样本：
阿强(178,55) 阿亮(172,62) 小生(183,53) 大壮(184,64) 属于类别A（男生）
翠花(158,45) 小莲(152,52) 欣欣(148,46) 宝珠(163,51) 属于类别B（女生）
现在新来一个同学，外貌上看不出是男生还是女生[尴尬]… 但是体检发现其身高体重为（149,45），那么根据最邻近法（衡量距离的度量可以根据实际情况取，例如二范数）， 最近的样本是 欣欣(148,46)，类别是女生，所以判别新来的同学是女生～
假如K不取1，则新来的样本需要找最近的K个样本，如果这K个样本里面男生多，则判别为男生，女生多，则判别为女生。so easy..
决策树分类器
随机森林
编程能力
编程题目语言不限，选择最能体现水平的来做（滑稽脸）
如果可以的话，每个题都分析一下时间复杂度和存储复杂度…
字符串输出
集合 A[n]={‘a’, ‘x’, ‘:’, …}
集合 B[n]={‘b’, ‘y’, …}
按顺序输出B中的字符，条件是输出的字符在A中也出现，且最多输出一次。
考核的内容实际上就是遍历字符串以及字符串去重
//assume input two vectors..
void solution(vector<char> a, vector<char> b) {
// use a map to store a dynamically
map<char,bool> table;
for(int i=0; i<a.size(); i++){
table[a[i]]=true;
}
// if character exist in a, print and update table.
for(int i=0; i<b.size(); i++){
if(table[b[i]]){
cout<<b[i]<<endl;
table[b[i]]=false;
}
}
}
代码遍历了两个数组各一次，时间复杂度为size(A)+size(B)
存储了一个映射表，存储复杂度为size(A)
done
遍历图中的点
一个图中有nodeNum个节点，编号为0到nodeNum-1，任意两个节点之间均有路径直接连接，二维矩阵pDis[i][j]记录了从节点i到节点j的路径长度。要求给出一条从节点0出发，遍历所有节点的路径，将访问顺序记录在输出数组path中。在该路径中，所有节点都必须只能访问一次，从某个节点i出发，到达下一个节点必须是所有还没有访问过的节点中距离i最近的那个。
实现memcopy
实现void memcopy(void *dst, void* src, unsigned int len); 要求考虑有重叠的情况.
数组
给定一个数组，输出该数组的中位数，最小值和最大值，并给出时间复杂度和储存复杂度
二分查找树
实现一个二分查找树，要求实现：1. 创建一个二分查找树T；2. 给定一个元素A，将T中所有大于A的元素按照从小到大的顺序依次输出；3. 给定一个元素B，输出T中最接近B的元素;
字典
给定一个字典A，里面含有m个英文单词，实现一个拼写检查算法，对用户输入的单词x进行检查。
正整数分解
给定一个正整数N，分解为不同正整数的和的形式。
字符串查重
给定一长一短两个字符串A和B，假设A长B短，要求判断B是否包含在字符串A中