当前位置： 首页 > news >正文

C++面试常见手撕题目

news 2025/2/22 2:10:49

前言

作者：小蜗牛向前冲

名言：我可以接受失败，但我不能接受放弃

  如果觉的博主的文章还不错的话，还请点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正

分享常见的面试手撕题目（未完待续） 

一、场景设计题目 

1、设计一个多线程下安全缓冲区

支持push:当缓冲区满了应该阻塞等待

支持pop：移除缓冲区的元素

支持size：缓冲区中有多少有效元素

支持多个生产者和消费者同时访问，要保证线程安全

 对于多线程中的安全机制：以上可以通过muetx，condition_variable实现

#include<iostream>
#include<queue>
#include<mutex>
#include<condition_variable>using namespace std;template<class T>
class buffer
{
public:buffer(int capacity):_capacity(capacity){}void push(const T& item){//加锁保证线程安全unique_lock<mutex> lock(_mutex);//等待直到可用空间//wait的参数：lck锁，pred:是一个可调用对象或者函数，返回true就是不等待继续往后执行cond_producer.wait(lock, [this]() {return _buf.size() < _capacity; });//插入元素_buf.push(item);//通知消费者可以进行消费cond_consumer.notify_one();//这里的notify_one可以让条件变量阻塞的那个线程运行起来}//这里返回的是队头元素T pop(){//加锁unique_lock<mutex> lock(_mutex);//等待可以消费的元素cond_consumer.wait(lock, [this]() {return !_buf.empty(); });T item = _buf.front();_buf.pop();//通知生产者进行生产cond_producer.notify_one();return item;}int size(){return _buf.size();}
private:queue<T> _buf;//缓冲区int _capacity;//容量mutex _mutex;//锁condition_variable cond_producer;//生产者等待条件condition_variable cond_consumer;//消费者等待条件
};

unique_lock 和 lock_guard 的区别

  1. std::lock_guard<mutex>:

    • 是一个简单的、轻量级的锁管理器，一旦构造，就立即获取锁，并在析构时自动释放锁。
    • 它的使用非常简单，适合不需要改变锁状态（如手动锁定、解锁）的情况。
    • lock_guard 不支持手动解锁或重新锁定，也不支持条件变量等待时的锁管理。

  2. std::unique_lock<mutex>:

    • 提供了更灵活的锁管理功能，可以手动锁定、解锁和重新锁定。
    • 支持条件变量的等待机制（如 std::condition_variable::wait）。
    • 可以延迟锁定（即在构造时不立即获取锁），更适合需要更复杂锁控制的场景。

在有条件变量的情况下应该选择：unique_lock，支持手动加锁和解锁。 

2、在Linux中计算一个目录的文件大小

int get_dir_size(const char *name)函数如何设计

要想知道一个文件大大小，

首先我们得打开这个文件opendir

DIR *opendir(const char *name);

 返回值：

  • 成功时：opendir() 返回一个指向 DIR 类型的指针。这个指针代表了打开的目录流，它可以被后续的 readdir() 等函数使用来遍历目录内容。

  • 失败时：opendir() 返回 NULL，并且设置全局变量 errno 来指示失败的原因。例如，目录不存在、没有权限读取等原因会导致 opendir() 失败

 其次我们用readdir读取目录中的每个文件信息

struct dirent *readdir(DIR *dirp);

struct dirent 结构体 ：

readdir() 返回的 struct dirent 结构体包含关于目录项的信息，以下是它的典型定义：

struct dirent {ino_t          d_ino;       /* inode number */off_t          d_off;       /* offset to the next dirent */unsigned short d_reclen;    /* length of this record */unsigned char  d_type;      /* type of file */char           d_name[256]; /* filename (null-terminated) */
};

这里我们关注的在目录中，我们现在读取到的文件名

 最后我们还知道，每个文件在状态stat函数。

int stat(const char *pathname, struct stat *statbuf);

stat函数会讲目标路径pathname，的信息存放着statbuf结构体中

struct stat 结构体:

struct stat {dev_t     st_dev;     /* 文件所在的设备 ID */ino_t     st_ino;     /* inode 编号 */mode_t    st_mode;    /* 文件的类型和权限 */nlink_t   st_nlink;   /* 硬链接的数量 */uid_t     st_uid;     /* 文件所有者的用户 ID */gid_t     st_gid;     /* 文件所有者的组 ID */dev_t     st_rdev;    /* 设备 ID（如果是设备文件） */off_t     st_size;    /* 文件的大小（字节数） */blksize_t st_blksize; /* 文件系统块的大小 */blkcnt_t  st_blocks;  /* 文件所占用的块数 */time_t    st_atime;   /* 文件的最后访问时间 */time_t    st_mtime;   /* 文件的最后修改时间 */time_t    st_ctime;   /* 文件状态的最后更改时间 */
};

到这里我们就可以知道，我们当前获取的文件是目录还是文件，如果是文件就可以读取文件大小，如果是目录就继续递归去找。 

细节处理：

在 Unix/Linux 文件系统中，每个目录都会有两个特殊的目录项：

  1. "."：表示当前目录本身。
  2. ".."：表示当前目录的父目录。

所有我们要在遍历找文件的时候，跳过他们，否则会进行死循环。 

#include <iostream>
#include <dirent.h>
#include <sys/types.h>
#include <sys/stat.h>
#include<cstring>using namespace std;// 求目录中的所有文件的大小
int get_dir_size(const char *name)
{long long size = 0;    // 文件大小DIR *dir;              // DIR是一个结构体，是一个目录流，经常和opendir.readdir,closedir一起使用struct dirent *entry;  // readdir的返回值，结构体中一般包含文件名或者目录名称，文件类型struct stat statbuff; // 用来获取文件的信息// 1、打开目录if ((dir = opendir(name)) == NULL){// 打开失败perror("openedir");return -1;}//2、遍历目录中的每一个文件和子目录while((entry=readdir(dir))!=NULL){char path[1024];snprintf(path,sizeof(path),"%s/%s",name,entry->d_name);//在目录中，拼接文件所在的路径//2.1跳过"."表示当前目录和".."父目录,避免死循环if((strcmp(entry->d_name,".")==0)||strcmp(entry->d_name,"..")==0){continue;}//2.2获取文件信息if(stat(path,&statbuff)==-1){perror("stat");continue;}//2.3如果是目录就递归调用if(S_ISDIR(statbuff.st_mode)){size +=get_dir_size(path);}else if(S_ISREG(statbuff.st_mode))//如果是文件就累计文件大小{size +=statbuff.st_size;}}//记得关闭文件closedir(dir);return size;
}int main()
{cout<<get_dir_size("/home/pjb/study/study_linux/review_day4")<<endl;;
}

二、手撕排序算法 

1、冒泡排序

对于冒泡排序：

时间复杂度：O(N^2）

空间复杂度：O（1）

稳定性：稳定

//冒泡排序
void BubbleSort(vector<int>& arr)
{int n = arr.size();// 冒泡排序的核心是比较相邻的两个元素，每次将较大的元素“冒泡”到数组的末尾// 外层循环控制排序轮数，每轮确定一个最大值并放在正确的位置for (int i = 0; i < n-1; i++){bool check = false;//检查这个数组是否出现调整// 内层循环遍历还未排序的部分，n-i-1表示当前轮次中需要比较的元素范围for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){swap(arr[j], arr[j + 1]);check = true;}}//检查在数组经过一次遍历后，是否出现调整if (check == false){break;//数组已经是有序的}}
}

2、快排排序

时间复杂度：O(n*log(N)),最坏情况O(N*2)

空间复杂度:O(logN)

稳定性：不稳定

快排的核心思路，就是选定好一个基准元素，然后排序好这个基准元素，在去这个基准元素左右，排序好这二区间。

下面是排序好一个元素的思路： 

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
//快排
int part_sort(vector<int>& arr,int left,int right)
{//选择基准元素，这里选择在数组的一个元素为基准元素int ret = arr[left];int i = left+1;int j = right;while (i <= j){//从左往右找，比基准元素大的while (i<=right && arr[i]<=ret){i++;}//从右往左找，比基准元素要小的while (j > left && arr[j] >= ret){j--;}//交换好当前值if (i < j){swap(arr[i], arr[j]);}}//排序好一个基准元素swap(arr[left], arr[j]);return j;//返回已经排序好的位置
}

递归实现

递归实现void quickSort(vector<int>& arr, int left, int right)
{if (left < right){//排序好一个选定基准数int mid = part_sort(arr, left, right);//排序左边元素quickSort(arr, left, mid - 1);//排序右边quickSort(arr, mid+1, right);}
}

 非递归：借助的是栈实现的

//借助栈实现
void quickSort(vector<int>& arr, int left, int right)
{//这里借助栈的实现，其实核心也是模拟了递归实现的过程//用栈存放要排序数组的区间left,right,这里用键值对存放stack<pair<int, int>> st;st.push({ left,right });while (!st.empty()){//从栈中取出边界auto [start, end] = st.top();//c++17的语法，支持一个对象(数组，pair)，解析绑定到多个变量上st.pop();if (start < end)//注意判断{//进行分区操作int mid = part_sort(arr, start, end);//左区间if (mid - 1 > start){st.push({ start,mid - 1 });}//右区间if (mid + 1 < end){st.push({ mid + 1,end });}}}
}

3、堆排排序

时间复杂度：O(N*log(N))

空间复杂度：O(N*log(N))

稳定性：不稳定

堆排序的核心是：要先建立一个堆（这里以建立大堆进行举例子），依次取堆顶元素，填充数组，从后往前

//向上调整法:时间复杂度O(N)
void just_up(vector<int>& arr, int child)
{int parent = (child - 1) / 2;//不断向上调整进行大堆的建立while (child > 0){if (arr[child] > arr[parent]){swap(arr[child], arr[parent]);}else{break;}//向上调整child = parent;parent = (child - 1) / 2;}
}//向下调整
void just_down(vector<int>& arr, int n, int parent)
{int maxChild = parent * 2 + 1;//默认左孩子最大while (minChild < n){//找出最大的孩子if (minChild+1<n&&arr[minChild]<arr[minChild+1]){maxChild++;}//交换if (arr[minChild] > arr[parent]){swap(arr[minChild], arr[parent]);//更新坐标parent = minChild;maxChild = parent * 2 + 1;}else{break;}}
}
//堆排序
void HeapSort(vector<int>& arr,int n)
{//建大堆//用向上调整法进行建立大堆，从i==1开始即可//for (int i = 1; i < n; i++) //{//	just_up(arr, i);//这里是对数组中每个一个新加入的元素进行调整//}//用向下调整进建堆//这里是最后一个非叶子节点开始调整：(child-2)/2,,叶子节点肯定是不要调整的，因为他都没有节点和他相连接for (int i = (n - 2) / 2; i >= 0; --i){just_down(arr, n, i);}int i = 1;//把堆顶元素和最后一个元素进行交换，在将最后一个元素出堆,这里的出堆并是删除这个元素//只是不调整这个元素而已while (i < n){swap(arr[0], arr[n - i]);//调整堆just_down(arr, n - i,0);i++;}
}


http://www.mrgr.cn/news/27448.html

相关文章：

  • 运算符学习
  • 胤娲科技：解锁AI奥秘——产品经理的智能进化之旅
  • c++基础入门二
  • 【pyenv】pyenv安装版本超时的解决方案
  • ros学习笔记.4 Path Planning Part 2 (避障)
  • 机房运维工作的核心：确保系统稳定与高效
  • kaggle competition--房价预测（线性回归）
  • psgdemos本地安装与运行
  • Spring 源码解读：自定义实现BeanPostProcessor的扩展点
  • GameGen-O：大模型颠覆3A游戏开发
  • mp4文件解析
  • 跟《经济学人》学英文：2024年09月14日这期 People are splurging like never before on their pets
  • electron-vite vue3离线使用monaco-editor
  • 合资油车断崖式崩盘，买车的千万慎重了
  • [网络]http请求中的URL,方法,header 和 http响应中的状态码
  • 三、Kubernetes中的控制器的使用
  • 【AI大模型】Kimi API大模型接口实现
  • 如何使用 Visual Studio Code 将工作效率提升 200%
  • 21：I2C三：MPU6050的使用
  • 可解释性机器学习中的局部解释