首页 > 「面试」虎牙c/c++后台开发
头像
我是程序员小贱
编辑于 2020-11-02 22:02
+ 关注

「面试」虎牙c/c++后台开发

这是一篇纯C/C++服务端开发的面试,但是除了语言部分,其他部分也是需要大家好好掌握的,手撕算法合集见文末即可,希望对大家有帮助!

虎牙和斗鱼,这一定有你的青春吧?还真想回到那个通宵看直播的年纪,可是到了毕业季,找工作季,所以不得不将时间的中心转移,转移到离我们梦想更近的地方

前段时间不发生了虎牙,斗鱼一些事情嘛,于是我就想起之前也面过,大概回忆了下,面试不怎么难,但是这公司有个调性,动不动就把简历丢了,谁试谁知道。看看都面了些啥

开始之前呢,老规矩嘛,还是回忆下周末干了些啥,首先和小组的娟姐,谦参加了个算法拉力赛,怎么个拉立法,就是给你些数据,然后自己通过模型然后来进行预测,不管首先还是需要熟悉下环境,这都好几个月也没看过,py的很多库忘记的差不多了,不过我们三的努力还是进了个前十,哈哈哈哈

大米先生

想着一周基本上都是坐着,所以决定下午去和他们打打篮球,现在是真的酸痛。。。

最后,给大家看个游玩儿的视频,放松放松,开始新的一周。。

1 一面

常规的自我介绍带引面试官进入自己的知识海洋,这样的航行才会更加的顺利。

面试官对我的自我介绍的内容进行一番询问以后,开始对我的简历进行排查,无奈我的简历当然都是我所知道的内容,不仅如此,即使你往深入的挖,也是在我的掌控之中

纯虚函数和虚函数的区别

即使你知道关于虚函数的语法,但是你可能不知道为什么要这样子做以及它种种行为的所思所想。猜测你不想流于表面语法上的蜻蜓点水似是而非,那么现在我们来揭开挡在你和虚函数之间的这一层窗户纸

我们先看看他的语法规范

  • 类成员方法的生米前面加上virtual就变为虚函数
  • 在虚函数声明语句末尾加一个0就摇身变为纯虚函数
  • 子类可以重新定义基类的虚函数,这叫做复写
  • 子类可以自主选择是否提供一份属于自己的个性化虚函数实现

说说虚函数的简单实现

带有虚函数的类,编译器会为其分配一个虚函数表,里面会记录的是虚函数的地址,当此类被继承的时候,子类如果当此类被继承时,子类如果也写了虚函数就在子类的虚函数表中将父类的函数地址覆盖,否则继承父类的虚函数地址。

实例化之后,对象有一个虚函数指针,虚函数指针指向虚函数表,这样程序运行的时候,通过虚函数指针找到的虚函数表就是根据对象的类型来指向的了。

虚拟地址表

Vector的内存分配和底层实现

当你去了解某个知识的底层数据结构的时候,你就会发现,哦原来我们大一大二学习的数据结构这么重要。Vector采用的数据结构比较简单,使用一段连续的线性内存空间,我们先看看他的源代码

//_Alloc 表示内存分配器,此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};

在这里有分别使用Myfirst,Mylast和Myend分别指向vecotr容器对象的起始字节位置;Mylast只想当前最后一个元素的末尾字节;Myend只想整个vector容器所占用内存空间的末尾字节

内存地址

别小看这三个迭代器,它可以表示出一个已容纳2个元素,容量为5的vector容器,通过这三者的结合,我们可以组成这样不同的场景

  • Myfirst和Mylst表示vector容器中当前已经手机用的内存空间
  • Mylast和Myend表示vector当前空闲的内存空间
  • Myfirst和Myend表示vector容器的容量

这样的涉及方案,我不知道你现在是否想起了网络的滑动窗口,如果你忘记了,此时可以马上查阅一下,这样也许会让你的影响更加深刻

如果是空的vector容器,由于没有元素的空间分配,所以此时的first,last,end都是null,通过这样的三个迭代器,可以比较轻松的实现首尾表示,大小,容器判断等功能

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
public:
    iterator begin() {return _Myfirst;}
    iterator end() {return _Mylast;}
    size_type size() const {return size_type(end() - begin());}
    size_type capacity() const {return size_type(_Myend - begin());}
    bool empty() const {return begin() == end();}
    reference operator[] (size_type n) {return *(begin() + n);}
    reference front() { return *begin();}
    reference back() {return *(end()-1);}
    ...
};

vecotr的扩容机制是什么?

vecort用来存放元素,自然有个容量的概念。如果vector的大小和容量是满载的,那么此时往里面添加元素,vector就需要扩容,扩容会经历三个步骤

  • 弃用当前的内存空间,重新申请更大的内存空间
  • 将旧内存空间数据移动到新的内存空间中
  • 将旧的内存空间释放

这样看来vector的扩容还是不容易,比较耗时。那么为了降低再次分配内存空间的成本,每次扩容vector的时候申请比用户需求量更多的内存空间,但是vecoter容器扩容的时候,不同的编译器可能有所不同,比如使用VS的时候,它会扩容现有容器容量的百分之50

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> a;
    cout << "a.size(): " << a.size() << "       a.capacity(): " << a.capacity() << endl;
    for (int i = 0; i < 10; i++)
    {
        a.push_back(i);
        cout << "a.size(): " << a.size() << "   a.capacity(): " << a.capacity() << endl;
    }
    return 0;
}

说说STL的线程安全

这里可从操作系统 来回答线程安全,然后联系STL即可

什么时候用vector和list,实现的方案

简单说:vector和数组类似,连续的内存空间,那么随机访问,时间复杂度为O(1),由于内存空间连续,所以插入删除的时候,会造成内存块的拷贝,时间复杂度为O(n)

另外,如果数据内存空间不足,会采取扩容的方式,重新申请一块更大的内存空间进行拷贝

而list底层采用双向链表的方式,内存空间不连续,那么List查询效率较低,时间复杂度为O(n),但是插入和删除的效率比较搞,不用移动数据,移动指针即可

从迭代器的角度出发,在vector中,iterator支持“+”、"+="、“<”等操作,而list中不支持。到那时两者都是重载了"+="

说说HTTP代理

之前介绍的都是一问一答的情景,但是在大部分的情况下都会存在多台服务器进行通信服务。其中比较常见的就是在请求方与应答方中间增加一个中间代理。

图片说明
代理

代理作为中间位置,相对请求方为服务端,相当于后端服务端为请求方。代理常见的功能为负载均衡。在负载均衡中需要区分正向代理与反向代理,其中也就会涉及调度算法,比如轮询还是一致性哈希等。

图片说明

2 二面

面向对象的三个特点,简单总结

封装:使用类将自己的数据和方法让可信的类或者对象操作,对不可信的进行信息隐藏。比如对某些数据的权限设置为私有的,则不能被外界访问,不同对内部数据提供不同级别的保护,防止程序中无关的部分意外的改变或者错误的使用了对象的私有部分

继承:它可以使用现有类的所有功能,无需重新编写原来的类的情况下对这些功能进行扩展,被继承的类叫做基类,父类

多态:向不同的对象发出同意消息,不同的对象在接受的时候产生不同的行为

  • 静态多态:c++语言允许函数重载和运算符重载,模板
  • 动态多态:通过定义虚函数支持动态联编

进程间的通信,这是之前写过的,就直接拿过来了,免得大家还跳转过去看

管道

学习软件工程规范的时候,我们知道瀑布模型,在整个项目开发过程分为多个阶段,上一阶段的输出作为下一阶段的输入。各个阶段的具体内容如下图所示

图片说明

最初我们在学习Linux基本命令使用的时候,我们经常通过多个命令的组合来完成我们的需求。比如说我们想知道如何查看进程或者端口是否在使用,会使用下面的这条命令

图片说明

这里的"|"实际上就是管道的意思。"|"前面部分作为"|"后面的输入,很明显是单向的传输,这样的管道我们叫做"匿名管道",自行创建和销毁。既然有匿名管道,应该就有带名字的管道"命名管道"。如果你想双向传输,可以考虑使用两个管道拼接即可。

创建命名管道的方式

图片说明

test即为管道的名称,在Linux中一切皆文件,管道也是以文件的方式存在,咋们可以使用ls -l 查看下文件的属性,它会"p"标识。

图片说明

下面我们向管道写入内容

echo "666" > test

图片说明

此时按道理来说咋们已经将内容写入了test,没有直接输出是因为我们需要开启另一个终端进行输出(可以理解为暂存管道)

cat < test

ok,我们发现管道内容被读出来,同时echo退出。那么管道这种通信方式有什么缺点?我们知道瀑布模型的软件开发模式是非常低下的,同理采用管道进行通信的效率也很低,因为假设现在有AB两个进程,A进程将数据写入管道,B进程需要等待A进程将信息写完以后才能读出来,所以这种方案不适合频繁的通信。那优点是什么?

最明显的优点就是简单,我们平时经常使用以致于都不知道这是管道。鉴于上面的缺点,我们怎么去弥补呢?接着往下看

消息队列

管道通信属于一股脑的输入,能不能稍微温柔点有规矩点的发送消息?

答:可以的。消息队列在发送数据的时候,按照一个个独立单元(消息体)进行发送,其中每个消息体规定大小块,同时发送方和接收方约定好消息类型或者正文的格式。

在管道中,其大小受限且只能承载无格式字节流的方式,而消息队列允许不同进程以消息队列的形式发送给任意的进程。

但是当发送到消息队列的数据太大,需要拷贝的时间也就越多,所以还有其他的方式?继续看

共享内存

使用消息队列可以达到不错的效果,但是如果我们两个部门需要交换比较大的数据的时候,一发一收还是不能及时的感知数据。能不能更好的办法,双方能很快的分享内容数据,答:有的,共享内存

我们知道每个进程都有自己的虚拟内存空间,不同的进程映射到不同的物理内存空间。那么我们可不可以申请一块虚拟地址空间,不同进程通过这块虚拟地址空间映射到相同的屋里地址空间呢?这样不同进程就可以及时的感知进程都干了啥,就不需要再拷贝来拷贝去。

我们可以通过shmget创建一份共享内存,并可以通过ipcs命令查看我们创建的共享内存。此时如果一个进程需要访问这段内存,需要将这个内存加载到自己虚拟地址空间的一个位置,让内核给它一个合法地址。使用完毕接触板顶并删除内存对象。

那么问题来了,这么多进程都共享这块内存,如果同时都往里面写内容,难免会出现冲突的现象,比如A进程写了数字5,B进程同样的地址写了6就直接给覆盖了,这样就不友好了,怎么办?继续往下看

信号量

为了防止冲突,我们得有个约束或者说一种保护机制。使得同一份共享的资源只能一个进程使用,这里就出现了信号量机制。

信号量实际上是一个计数器,这里需要注意下,信号量主要实现进程之间的同步和互斥,而不是存储通信内容。

信号量定义了两种操作,p操作和v操作,p操作为申请资源,会将数值减去M,表示这部分被他使用了,其他进程暂时不能用。v操作是归还资源操作,告知归还了资源可以用这部分。

信号

从管道----消息队列-共享内存/信号量,有需要等待的管道机制,共享内存空间的进程通信方式,还有一种特殊的方式--信号

我们或许听说过运维或者部分开发需要7 * 24小时值守(项目需要上线的时候),当然也有各种监管,告警系统,一旦出现系统资源紧张等问题就会告知开发或运维人员,对应到操作系统中,这就是信号。

在操作系统中,不同信号用不同的值表示,每个信号设置相应的函数,一旦进程发送某一个信号给另一个进程,另一进程将执行相应的函数进行处理。也就是说把可能出现的异常等问题准备好,一旦信号产生就执行相应的逻辑即可。

套接字

上面的几种方式都是单机情况下多个进程的通信方式,如果我想和相隔几千里的小姐姐通信怎么办?

这就需要套接字socket了。其实这玩意随处可见,我们平时的聊天,我们天天请求浏览器给予的响应等,都是这老铁。

const和define的区别,哪种更好

  • 如果从起作用的阶段来说:#define在编译预处理阶段起作用,而const是在编译,运行的时候才起作用
  • 如果从起作用的方式而言:#define只是简单的字符串替换,没有类型检查。但是const有对应的数据类型,是需要判断的,可以避免一些低级的错误
  • 如果从存储方式而言,#define只是进行展开,多少地方使用就替换多少次,const定义的只读变量在程序运行过程中只有一份备份

使用C++实现LRU

实际上浏览器的缓存策略,memcached的缓存策略都采用了LRU的算法,它会将近期最不会访问的数据淘汰掉。之所以这么流行,在于实现比较简单又使用,命中率较高

  • 新的数据插入到链表的头部
  • 每当缓存命中,则将数据移动到链表头部
  • 当链表满的时候,将链表尾部的数据丢弃即可

那么实现它需要具备哪些操作

  • set(key ,value):如果key在hashmap中存在,则先重置对应的value值,然后获取对应节点的cur,将cur节点从链表中删除,并移动到头部。如果key在hashmap不存在,则新建一个节点,并将节点存放于链表的头部。如果cache满了,则将链表最后一个节点删除即可
  • get(key):如果key在hashmap存在,则将对应的节点放到链表头部,并返回对应的value值

此处实现采用双向链表+Map方式进行实现,为什么采用双向链表呢,因为如果为单链表,我删除一个元素需要从头部查找,时间复杂度为O(N),而使用双向链表只需要改变前驱的指针指向就可,这样只需要O(1)即可。使用map是考虑到便于在O(logn)的时间查找元素。

先来看看定义

struct CacheNode {
  int key;      // 键
  int value;    // 值
  CacheNode *pre, *next;  // 节点的前驱、后继指针
  CacheNode(int k, int v) : key(k), value(v), pre(NULL), next(NULL) {}
};

将节点插入到头部

void setHead(CacheNode *node)
{
  node -> next = head;
  node -> pre = NULL;

  if (head != NULL)
  {
    head -> pre = node;
  }
  head = node;
  if (tail == NULL)
  {
    tail = head;
  }
}

get(key)直接判断map是否有key值即可

int get(int key)
{
  map<int, CacheNode *>::iterator it = mp.find(key);
  if (it != mp.end())
  {
    CacheNode *node = it -> second;
    remove(node);
    setHead(node);
    return node -> value;
  }
  else
  {
    return -1;
  }

手撕算法+复习书籍 提取码:xlan

更多模拟面试

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐