1.AGV小车

1.1 串口通讯与色带导航算法

1.1.1 三个串口：

上位机与下位机运动控制串口，两个激光传感器串口

RS232，485串口速率要设置波特率，115200，设置校验位等信息，打开设备（open函数），是否有奇偶校验位

1.1.2 串口实质：

​ 是文件，要想读写串口数据，必须先打开串口，设置串口，然后读写，读写完毕还要关闭串口。

1.1.3 色带导航算法思想：

​ 保存当前传感器的位置信息和上一次前后传感器的位置信息。每次读取信息都要做均值处理，读取三帧数据，取报文中有效数据的均值。

1
2
3
4
5
6
7
8
9

//前后传感器报文接收帧
unsigned char frame_resultSensor_back[SENSORFRAMESIZE];
unsigned char frame_resultSensor_front[SENSORFRAMESIZE];
//前后传感器位置信息
double front_location[6];
double back_location[6];
//上一次前后传感器的位置信息
double pre_front_location[6];
double pre_back_location[6];

函数：根据指定的位姿产生指令报文。

对前后数据进行判断，如果前后都没有色带，就原地旋转，

检测到色带后：

​ 前有后无，就直行，然后不断读取当前传感器数据，判断状态并向standard调整（平行，左偏，右偏）

​ 前无后有，就旋转到前有，然后跳出旋转

​ 当前后都有，先直行一小段距离，然后判断状态并向标准调整。（直行，右平移，左平移，右旋转，左旋转）。

1.2 hectorSLAM

1.2.1激光雷达数据获取：

​ 进行激光雷达数据结构的解析，采用Socket通讯，通过ROS进行打包发布。

1.2.2基于GN算法计算激光雷达位姿：

​ 采用占据栅格地图，通过双线性差值，将激光雷达扫描数据投影到栅格地图中，然后引入GN算法，计算激光雷达位姿。对连续两帧激光数据进行匹配，估计算出移动机器人相对位姿的变化，然后通过连续叠加位姿变化从而实现对移动机器人的位姿跟踪，实现激光雷达自身定位。

1.2.3 全局位姿优化与环境地图绘制：

​ 需要利用图优化的思想，根据约束建模，增量参数化和误差函数设计实现最小化误差，实现位姿优化。最后构建出环境占据栅格地图。进行全局位姿优化的目的是为了降低位姿计算过程伴随的误差问题。首先对激光数据进行直线拟合，在此基础上提取角点特征，完成角点检测过程。以角点作为路标，结合机器人位姿构建出图模型，从而将SLAM问题转换成图优化问题。通过约束建模，增量参数化以及误差函数设计三个步骤实现最小化误差的目的，实现位姿优化，然后构建出环境占据栅格地图，实现了完整的SLAM设计流程。

1.2.4 角点检测算法：

​ 提出并实现一种基于最小二乘法直线拟合的角点检测算法。主要包括了角点特征滤波，特征值计算和NMS（非极大值抑制）处理。

难点：

1.串口通信

2.算法设计：色带导航算法，角点检测算法；

3.代码研究。不断的剥离代码，做注释。

2.视频压缩算法：

gropf指令可以看到程序中每个函数的消耗时间。

2.1采用SSE指令+loop unrolling对视频压缩进行优化。其中包括sad_block,dct优化。

2.2对压缩算法的运动估计的参数进行调整。

比如cm->me_search_range，参数越小，压缩时间越快，相当于搜索范围越小，但这个参数越小，编码文件的size就会越大。

对量化的精度参数进行调整。编码文件的大小在缩小，PSNR的数值在减小，但同样的执行时间也在减小，这里执行时间减小可能是因为编码文件大小改变引起的。根据实际播放效果来看，当cm->qp=10的时候播放是可以接受的，Y分量上的PSNR有34.5，U分量和V分量有40左右。当cm->qp=5的时候，播放出现了麻点，有点老式电视机播放的样子，但基本清晰，也勉强可以接受，但由于编码时间减少不多，PSNR降的却很多，因此不建议将参数设置为5，参数值设置为10是比较合适的。保证了较高的压缩比和编码速率，同时保证了视频的质量。

2.3采用cuda架构进行GPU视频编码。

2.3.1cuda的线程模型

​ Host（主机端）执行核函数 Kernel，而 Device（GPU）上运行 Grid，每一个 Grid 上面包含了很多的 block，而每个 block 上又包含了很多的线程，并且他们都可以被定义为一维、二维和三维的方式，在每个 block 内部又可以进行线程之间的同步和数据共享。

​ 当 Host 端需要进行大量并行计算的时候，会将数据从内存传入到 GPU 中，然后GPU 再利用自身高并发的特性，完成并行计算，计算完成之后再将计算结果传回到 CPU。

2.3.2sad_block优化

​ 将两个 block 块放入到 GPU 中，再利用核函数完成对应像素点的差值计算，最后将每个像素的差值返回到 CPU 中，完成求和计算，就得到了这两个块的 SAD 计算 。但CPU到GPU频繁的交换导致优化适得其反。

2.3.3运动估计优化

​ 将一帧图像完全送入到 GPU 中进行处理。将一帧的图像分成很多的 macroblock（宏块），在编码器中一个宏块的大小是 8x8 的矩阵，里面存储了 64 个像素。我的想法是一个 grid 中分割成(weight/8)(height8)个 block，其中 weight 和 height 是该帧图像的宽和高。在每个block 中根据 YUV 分量的不同操作，拥有不同的线程数，这个线程数主要取决于他们的搜索范围不同，比如对于 Y 分量，搜索范围就是 3232，所以会有 1024 个线程，每个线程中将两个对应的 88 的宏块进行差值计算，并且在一个 block 中找到最优的 SAD即最小的），因此在实际设计中，需要设置一个shared的变量 best_sad，让块中的每个线程都可以共享访问，确定自己对应的这个宏块是不是当前确定运动估计的最佳匹配块。

1.字节跳动 飞书 杭州 客户端 提前批 一面挂

​ https建立连接的流程

​ 手写单例模式

​ 手写生产者消费者模型

​ 两个栈实现一个队列

​ 线程池

​ 观察者模式

面试笔记

一、C++

1.基础知识

1.1 关键字

1.1.1 static

• 隐藏：在编译多个文件的时候，指定函数变量的作用于为文件内部，未加static具有全局可见性;
• 保持变量的内容持久;
• 默认初始化为0;
• C++的类成员变量会声明为static，不是对象的成员。

数据结构与算法面经

1.Top K解决办法。

• 全局排序，O(n*lg(n))
• 局部排序(冒泡前k个)，只排序前k个,O(n*k);

MVC模式

1.MVC模式即model-view-controller(模型-视图-控制器)模式，常见的比如Android开发中的，view即Android的界面，model即界面上要展示的数据，而controller就是控制数据，数据变化时实时更新view展示的数据。

• Model（模型）：代表了一个存取的数据的对象。
• View（视图）：视图代表了模型包含的数据的可视化。
• Controller（控制器）：控制器作用于模型和视图之上，可以做到在数据变化时实时更新视图。它让model和view分开。

适配器模式

1.适配器模式（Adapter Pattern）属于结构型模式，它结合了两个独立接口的功能。是作为两个不兼容接口的桥梁。比如读卡器可以看做是一个适配器，连接电脑和SD卡。适配器可以将一个类的接口转换成客户希望的另外一个接口。适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

单例模式

1.单例模式属于创建型模式。确保一个类只有单个对象被创建，这个类提供了一种访问其唯一对象的方式，可以直接访问，不需要实例化该类的对象。

注意：

• 1.单例类只能有一个实例；
• 2.单例类必须自己创建自己唯一的实例；
• 3.单例类必须给所有其他对象提供这一个实例。

The world is full of traps, but you are the treasure!

献给李沁小姐姐！

1.求链表倒数第K个节点（单向链表）？

​ 思路：采用双指针法。P1指向表头，P2指向P1相隔K的节点，同时向后移动，当P2到达表尾(P2->next=null), P1即倒数第K个节点。

2.判断链表是否有环？

​ 首先循环链表是带环链表的一种特殊情况。

1.机器学习算法分类

• supervised learning（监督学习）
  • classification problem（分类问题）
  • regression problem（回归问题）
• unsupervised learning（无监督学习）（clustering algorithm，聚类）
  阅读全文 »