记一次小公司的面试题
（1）重载、覆盖、重写、隐藏的区别和联系
（2）双向链表的插入和删除，链表和线性表的优缺点
（3）广度优先遍历BFS
（4）内存泄漏的原因
（5）快排和冒泡排序选择一种排序算法进行实现（排序算法属于基础算法，要求烂熟于心，要求2分钟内写出算法才算过关）
vector<int> nums;
int partition(int low,int high) {
int pivot = nums[low];
int pivotpos = low;
for (int i = low + 1; i <= high; i++) {
if (nums[i] <= pivot) {
pivotpos++;
swap(nums[pivotpos], nums[i]);
}
}
nums[low] = nums[pivotpos];
nums[pivotpos] = pivot;
return pivotpos;
}
void quickSort(int left,int right) {
if (left >= right) { return; }
int pos = partition(left, right);
quickSort(left, pos - 1);
quickSort(pos + 1, right);
}
int main() {
nums = { 12,56,6,59,26,859,45,46545,123,2562,4856,2,1564,265,5648,456 };
quickSort(0,nums.size()-1);
for (auto num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
（6）贪吃蛇蛇身移动算法的实现
（7）手撕代码：如图所示，假定有一个长为N,宽为M的矩形（M和N均为正整数），现在把它放到坐标轴中，然后从坐标轴的（0,0）这个点以向右上方45度抛出一个小球，小球碰到矩形的边后会反弹（就像光线一样），现在要求你设计一个算法，求出每次小球与矩形碰撞的坐标（均保留整数即可）。
思路：把矩形看成内部有很多网格，定义x轴、y轴方向向量dx、dy,小球每走一步进行一步探查，如果小球碰到了上下边界，则将y周的方向向量取反，如果小球碰到了左右边界，则将x轴的方向向量取反。
代码如下：
#面经##C++工程师##校招#void DBit(int M, int N) {
int x = 0, y = 0;
int dx = 1, dy = 1;
while (1) {
x = x + dx; y = y + dy;
if (x == 0 || x == N || y == 0 || y == M)
{
cout << x << " " << y << endl;
}
if (y == M||y==0) {
dy = -dy;
}
if (x == N||x==0) {
dx = -dx;
}
Sleep(100);
}
}
void testDBit()
{
DBit(3, 101);
}
int main() {
testDBit();
return 0;
}
投递中国科学技术大学等公司9个岗位 >