排序题

实现如下函数:int GetNthCount(const int *a , int len , int n)

其中,a为无序的int数组,len为a的长度,1<= n <len。

返回第n大的值在数组中出现的次数。

举例:假设a为{5,7,9,0,2,7},len=6,n=2,第n大的值是7,在数组中出现的次数是2,结果返回2。

 

我的代码

#include<iostream>
#include<set>
#include<map>
using namespace std;

int GetNthCount(const int *a , int len ,int n){
         map < int ,int> mp;
         for(int i =0; i < len ;i++){
            map<int , int>::iterator it = mp.find(a[i]);
            if(it != mp.end()){
                it->second++;
            }
            else{
                mp[a[i]] = 1;
            }
         }
         map<int , int>::iterator it1 = mp.end();
         for(int i = 0; i < n;i++){
            it1--;
         }
        return it1->second;
}

int main(){
   int a[] = {5,7,9,0,2,7,7};
   cout<<GetNthCount(a, 7 ,2)<<endl;
}

 

Vector

实现vector中的insert方法

template<class T>

class vector

{

//从pos位置开始插入,elems为插入元素的指针地址,len为elems指向的长度

bool insert(size_t pos,T * elems,size_t len = 1);

private:

T* __begin;//容器开始地址

T* __end;//容器有效元素的结束地址

size_t  __cap;//容器的容量

};

 

void insert(const_iterator iter,const T& t )
        {  
            int index=iter-begin();
            if (index<size_)
            {
                if (size_==capacity_)
                {
                    int capa=calculateCapacity();
                    newCapacity(capa);
                }
                memmove(buf+index+1,buf+index,(size_-index)*sizeof(T)); 
                buf[index]=t;
                size_++;
            } 
        }

 

字符串

给一个string,要求将里面的空格替换为特定字符后返回,如果空格在””里面则不需要替换。

示例:字符串为:zhuhai kingsoft office “wps et ppt”

将空格替换为逗号:”,”

替换后的字符串为:zhuhai,kingsoft,office,”wps et ppt”

 

我的代码

#include<iostream>
#include<cmath>
using namespace std;

string solution(string result){
    bool flag = false;
    for(int i = 0; i < result.length() ;i++){
          if(result[i] == '"'){
            flag = !flag;
          }
          if(flag){
            continue;
          }
          else if(result[i] == ' '){
            result[i] = ',';
          }
    }
    return result;
}

int main(){
    string str = "zhuhai kingsoft office \"wps et ppt\"";
    cout<<solution(str)<<endl;
}

1.创建远程仓库。

Project name:项目名称

Project description (optional):项目介绍

Visibility Level :项目的访问权限

2.创建完成后操作,终端cd 到你需要克隆到的文件夹目录下:

a. cd <你本地文件夹目录>

b.git clone <你自己刚创建的远程仓库目录>

c.把代码导入你clone 下来的目录下

3.提交代码

a. git add *

b.git commit -m”<注释>”

c.git push origin master

以上就是简单的代码上传过程。

注:你自己也可以在终端创建远程仓库

4.打开git命令窗口:
git clone 远程代码仓库的地址
cd (git clone的文件夹路径)

git pull origin master//更新 必须做的操作

// git remote add origin 你刚才建立的项目连接
git add .
git commit -m ‘注释’
git push -u origin master 将代码推送到gitlab端

5,创建并切换分支本地分支并推送到远程服务器;

git branch : 查看我们的git仓库有几个分支,而我们目前工作处于那个分支,前面有个*号的就为我们目前所处的分支。

git branch -a : 查看远程分支。

git branch name : 创建分支,而这个分支的指针就指向最新的commit对象,也就和HEAD指向同一对象。如git branch test,表示创建本地test分支。
git checkout name : 切换到目的分支,我们默认的主分支为master。
git checkout –b name:创建并切换分支。
git push origin name: 将本地name分支推送到远程服务器。

git status : 查看文件更改状态。在添加文件之前或之后,我们会用git status 查看有变化的文件(一般有变化的文件会以红色显示出来)。

//设置显示隐藏文件夹
defaults write com.apple.finder AppleShowAllFiles YES

6,遇到的问题,即解决办法:
! [rejected] master -> master (non-fast-forward)
error: failed to push some refs to ‘git@github.com:******/Demo.git’
hint: Updates were rejected because the tip of your current branch is behind

1.使用强制push的方法:

$ git push -u origin master -f

这样会使远程修改丢失,一般是不可取的,尤其是多人协作开发的时候。

2.push前先将远程repository修改pull下来

$ git pull origin master

$ git push -u origin master

3.若不想merge远程和本地修改,可以先创建新的分支:

$ git branch [name]

然后push
$ git push -u origin [name]

方法一很暴力,但很实用,可以轻易本地文件同步到远程服务器端。
多人协作使用,慎用!

7.tag 的简单使用

1. git push –tags 把本地的tag推送到远程

2.git fetch origin tag <tagname> 获取远程tag

(1)进程与线程的区别?

调度:线程是独立调度的基本单位,进程是拥有资源的基本单位。在同一进程中,线程的切换不会引起进程的切换;在不同的进程中,进行线程切换,则会引起进程的切换。
拥有资源:进程是拥有资源的基本单位,线程不拥有资源,但线程可以共享器隶属进程的系统资源。
并发性:进程可以并发执行,而且同一进程内的多个线程也可以并发执行,大大提高了系统的吞吐量。
系统开销:创建和撤销进程时,系统都要为之分配或回收资源,在进程切换时,涉及当前执行进程CPU环境的保存以及新调度的进程CPU环境的设置;而线程切换时只需保存和设置少量寄存器内容,因此开销很小,另外,由于同一进程内的多个线程共享进程的地址空间,因此这些线程之间的同步与通信比较容易实现,甚至无须操作系统的干预。
通信方面:进程间通信需要借助操作系统,而线程间可以直接读/写进程数据段来进行通信。

(2)进程间的通信方式?

  • 管道( pipe )
  • 有名管道 (named pipe)
  • 信号量( semophore )
  • 消息队列( message queue )
  • 信号 ( signal )
  • 套接字( socket )
  • 共享内存(Shared Memory)

(3)线程间的通信方式?

  • 事件(Event);
  • 信号量(semaphore);
  • 互斥量(mutex);
  • 临界区(Critical section)

(4)栈和堆的区别?

1、在申请方式上

(stack): 现在很多人都称之为堆栈,这个时候实际上还是指的栈。它由编译器自动管理,无需我们手工控制。 例如,声明函数中的一个局部变量 int b 系统自动在栈中为b开辟空间;在调用一个函数时,系统自动的给函数的形参变量在栈中开辟空间。

(heap): 申请和释放由程序员控制,并指明大小。容易产生memory leak。

在C中使用malloc函数。

如:char *p1 = (char *)malloc(10);

在C++中用new运算符。

如:char *p2 = new char(20);

但是注意p1本身在全局区,而p2本身是在栈中的,只是它们指向的空间是在堆中。

2、申请后系统的响应上

(stack):只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。

(heap): 首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序。另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete或 free语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。

3、申请大小的限制

(stack):在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将提示 overflow。因此,能从栈获得的空间较小。例如,在VC6下面,默认的栈空间大小是1M(好像是,记不清楚了)。当然,我们可以修改:打开工程,依次操作菜单如下:Project->Setting->Link,在Category 中选中Output,然后在Reserve中设定堆栈的最大值和commit。

注意:reserve最小值为4Byte;commit是保留在虚拟内存的页文件里面,它设置的较大会使栈开辟较大的值,可能增加内存的开销和启动时间。

(heap): 堆是向高地址扩展的数据结构,是不连续的内存区域(空闲部分用链表串联起来)。正是由于系统是用链表来存储空闲内存,自然是不连续的,而链表的遍历方向是由低地址向高地址。一般来讲在32位系统下,堆内存可以达到4G的空间,从这个角度来看堆内存几乎是没有什么限制的。由此可见,堆获得的空间比较灵活,也比较大。

4、分配空间的效率上

(stack):栈是机器系统提供的数据结构,计算机会在底层对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高。但程序员无法对其进行控制。

(heap):是C/C++函数库提供的,由new或malloc分配的内存,一般速度比较慢,而且容易产生内存碎片。它的机制是很复杂的,例如为了分配一块内存,库函数会按照一定的算法在堆内存中搜索可用的足够大小的空间,如果没有足够大小的空间(可能是由于内存碎片太多),就有可能调用系统功能去增加程序数据段的内存空间,这样就有机会分到足够大小的内存,然后进行返回。这样可能引发用户态和核心态的切换,内存的申请,代价变得更加昂贵。显然,堆的效率比栈要低得多。

5、堆和栈中的存储内容

(stack):在函数调用时,第一个进栈的是主函数中子函数调用后的下一条指令(子函数调用语句的下一条可执行语句)的地址,然后是子函数的各个形参。在大多数的C编译器中,参数是由右往左入栈的,然后是子函数中的局部变量。

注意:静态变量是不入栈的。当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地址,也就是主函数中子函数调用完成的下一条指令,程序由该点继续运行。

(heap):一般是在堆的头部用一个字节存放堆的大小,堆中的具体内容有程序员安排。

堆和栈的区别可以用如下的比喻来看出: 使用栈就象我们去饭馆里吃饭,只管点菜(声明变量)、付钱、和吃(使用),吃饱了就走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自由度小。

使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由度大。

(5)C++和C的区别?

C是一个结构化语言,它的重点在于算法和数据结构。对于语言本身而言,C是C++的子集。C程序的设计首要考虑的是如何通过一个过程,对输入进行运算处理,得到输出。对于C++,首要考虑的是如何构造一个对象模型,让这个模型能够配合对应的问题,这样就可以通过获取对象的状态信息得到输出或实现过程控制。

因此,C与C++的最大区别在于,它们用于解决问题的思想方法不一样。

C实现了C++中过程化控制及其他相关功能。而在C++中的C,相对于原来的C还有所加强,引入了重载、内联函数、异常处理等。C++更是拓展了面向对象设计的内容,如类、继承、虚函数、模板和包容器类等。

在C++中,不仅需要考虑数据封装,还需要考虑对象的粒度的选择、对象接口的设计和继承、组合与继承的使用等问题。

相对于C,C++包含了更丰富的设计概念。

(6)BST,AVL树,红黑树的区别?

二叉查找树(BST)

二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:

  • 任意节点左子树不为空,则左子树的值均小于根节点的值.
  • 任意节点右子树不为空,则右子树的值均大于于根节点的值.
  • 任意节点的左右子树也分别是二叉查找树.
  • 没有键值相等的节点.

AVL树

AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1).不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少,但查找多的情况。

红黑树

一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black. 通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍.它是一种弱平衡二叉树(由于是弱平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,我们就用红黑树.

性质

  • 每个节点非红即黑.
  • 根节点是黑的。
  • 每个叶节点(叶节点即树尾端NUL指针或NULL节点)都是黑的.
  • 如果一个节点是红的,那么它的两儿子都是黑的.
  • 对于任意节点而言,其到叶子点树NIL指针的每条路径都包含相同数目的黑节点.
  • 查找、插入和删除的时间复杂度都是O(logn)

(7)产生死锁的必要条件?已经如何预防死锁?

一、计算机系统中的死锁

竞争不可抢占性资源引起死锁
竞争可消耗资源引起死锁
进程推进顺序不当引起死锁
二、产生死锁的必要条件

互斥条件(资源独占)
请求和保持条件
不可抢占条件(不可剥夺)
循环等待条件
三、处理死锁的方法

预防死锁
避免死锁
检测死锁
解除死锁
四、预防死锁

破坏‘请求和保持’条件
破坏‘不可抢占条件’条件
破坏‘循环等待’条件
(主要是破坏产生死锁的后三个条件)

五、解决死锁

最简单的办法是终止各锁住进程,或按一定的顺序中止进程序列,直到已释放到有足够的资源来完成剩下的进程时为止。
也可以从被锁住进程强迫剥夺资源以解除死锁

(8)TCP和UDP的区别?

TCP和UDP的区别:

传输控制协议TCP的特点:

(1) TCP是面向连接的运输层协议

(2) 每一条TCP连接只能有两个端口,即:点对点

(3) TCP提供可靠交付的服务

(4) TCP提供全双工通信

(5) 面向字节流,TCP中的“流”指流入到进程或从进程流出的字节序列

用户数据报协议UDP的特点:

(1) UDP是无连接的

(2) UDP使用尽最大努力交付

(3) UDP是面向报文

(4) UDP没有拥塞控制

(5) UDP支持一对一、一对多、多对一和多对的的交互通信

(6) UDP的首部开销小,只有8个字节,比TCP的20个字节的首部要短

(9)TCP状态中 time_wait 的作用?

TCP状态中 time_wait 的作用:

客户端接收到服务器端的 FIN 报文后进入此状态,此时并不是直接进入 CLOSED 状态,还需要等待一个时间计时器设置的时间。这么做有两个理由:

确保最后一个确认报文段能够到达。如果 B 没收到 A 发送来的确认报文段,那么就会重新发送连接释放请求报文段,A 等待一段时间就是为了处理这种情况的发生。
可能存在“已失效的连接请求报文段”,为了防止这种报文段出现在本次连接之外,需要等待一段时间。

(10)HTTP 2.0与HTTP 1.0的区别 ?

  1. HTTP/2采用二进制格式而非文本格式
  2. HTTP/2是完全多路复用的,而非有序并阻塞的——只需一个连接即可实现并行
  3. 使用报头压缩,HTTP/2降低了开销
  4. HTTP/2让服务器可以将响应主动“推送”到客户端缓存中

(11)HTTP与HTTPS的区别?

HTTP协议传输的数据都是未加密的,也就是明文的,因此使用HTTP协议传输隐私信息非常不安全,为了保证这些隐私数据能加密传输,于是网景公司设计了SSL(Secure Sockets Layer)协议用于对HTTP协议传输的数据进行加密,从而就诞生了HTTPS。简单来说,HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议,要比http协议安全。

HTTPS和HTTP的区别主要如下:

1、https协议需要到ca(证书授权机构:Certificate Authority )申请证书,一般免费证书较少,因而需要一定费用。

2、http是超文本传输协议,信息是明文传输,https则是具有安全性的ssl加密传输协议。

3、http和https使用的是完全不同的连接方式,用的端口也不一样,前者是80,后者是443。

4、http的连接很简单,是无状态的;HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议,比http协议安全。

(12)TCP的三次握手和四次挥手的过程?

在这里插入图片描述

在这里插入图片描述

(13)事务具有四个特性?

  • 原子性(Atomicity)
  • 一致性(Consistency)
  • 隔离性(Isolation)
  • 持续性(Durability)

(14)树的先序、中序和后序的递归和非递归实现?

树的先序递归:

void PreOrder(Tree* root)
{
	if (root != nullptr)
	{
		cout << root->date << " ";
		PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

树的先序非递归:

void PreOrder(Tree* root)
{
	stack<Tree* > Stack;
	if (root == nullptr)
		return;
	while (root != nullptr || !Stack.empty())
	{
		while (root != nullptr)
		{
			Stack.push(root);
			cout << root->date << " ";
			root = root->lchild;
		}
		root = Stack.top();
		Stack.pop();
		root = root->rchild;
	}
}

树的中序递归:

void InOrder(Tree* root)
{
	if (root != nullptr)
	{
		InOrder(root->lchild);
		cout << root->date << " ";
		InOrder(root->rchild);
	}
}

树的中序非递归:

void InOrder(Tree* root)
{
	stack<Tree*> s;
	while (root != nullptr || !s.empty())
	{
		if (root != nullptr)
		{
			s.push(root);
			root = root->lchild;
		}
		else
		{
			root = s.top();s.pop();
			cout << root->date << " ";
			root = root->rchild;
		}
	}
}

树的后序递归:

void PostOrder(Tree* root)
{
	if (root != nullptr)
	{
		PostOrder(root->lchild);
		PostOrder(root->rchild);
		cout << root->date << " ";
	}
}

树的后序非递归:

void PostOrder(Tree* root)
{
	stack<Tree*> s;
	Tree* r = nullptr;//使用辅助指针,指向最近访问过的节点
	while (root != nullptr || !s.empty())
	{
		if (root != nullptr)
		{
			s.push(root);
			root = root->lchild;
		}
		else
		{
			root = s.top();
			if (root->rchild != nullptr && root->rchild != r)
				root = root->rchild;
			else
			{
				s.pop();
				cout << root->date << " ";
				r = root;
				root = nullptr;
			}
		}
	}
}

(15)树的层次遍历?

void LevelOrder(Tree* root)
{
	if (root == nullptr)
		return;
	queue<Tree*> que;
	que.push(root);
	while (!que.empty())
	{
		root = que.front();
		cout << root->date << " ";
		que.pop();
		if (root->lchild != nullptr)
			que.push(root->lchild);
		if (root->rchild != nullptr)
			que.push(root->rchild);
	}
}

(16)static关键字的作用?

static关键字的作用:

(1)函数体内static变量的作用范围为该函数体,不同于auto变量,该变量的内存只被分配一次,因此其值在下次调用时仍维持上次的值;

(2)在模块内的static全局变量可以被模块内所用函数访问,但不能被模块外其它函数访问;

(3)在模块内的static函数只可被这一模块内的其它函数调用,这个函数的使用范围被限制在声明它的模块内;

(4)在类中的static成员变量属于整个类所拥有,对类的所有对象只有一份拷贝;

(5)在类中的static成员函数属于整个类所拥有,这个函数不接收this指针,因而只能访问类的static成员变量。

(17)const关键字的作用?

const关键字的作用:

(1)欲阻止一个变量被改变,可以使用const关键字。在定义该const变量时,通常需要对它进行初始化,因为以后就没有机会再去改变它了;

(2)对指针来说,可以指定指针本身为const,也可以指定指针所指的数据为const,或二者同时指定为const;

(3)在一个函数声明中,const可以修饰形参,表明它是一个输入参数,在函数内部不能改变其值;

(4)对于类的成员函数,若指定其为const类型,则表明其是一个常函数,不能修改类的 成员变量;

(5)对于类的成员函数,有时候必须指定其返回值为const类型,以使得其返回值不为“左值”。

(18)指针和引用的区别?

  1. 指针:指针是一个变量,只不过这个变量存储的是一个地址,指向内存的一个存储单元;引用的底层是const指针,引用同样占据一块内存。
  2. 引用不可以为空,当被创建的时候,必须初始化,而指针可以是空值,可以在任何时候被初始化。

(19)哈希表处理冲突的方法?

(1) 链地址法

链地址法是指把所有的冲突关键字存储在一个线性链表中,这个链表由其散列地址唯一标识。

(2) 开放定址法

开放定址法是指可存放新表项的空闲地址,既向它的同义词表项开放,又向它的非同义词表项开放。其数学递推公式为(Hi表示冲突发生后第i次探测的散列地址)

Hi = (H(key) + di) % m

式中,i = 1,2,…,k,m为散列表表长,di为增量序列。di通常有以下几种取法:

当di = 1,2,…,m – 1时,称为线性探测法。其特点是,冲突发生时顺序查看表中下一个单元,直到找出一个空单元或查遍全表。

当di = 12,-12,22,-22,…,k2,-k2时,又称为二次探测法。

当di = 伪随机数序列时,称为伪随机探测法。

(3) 再散列法

当发生冲突时,利用另一个哈希函数再次计算一个地址。直到冲突不再发生。

(4) 建立一个公共溢出区

一旦由哈希函数得到的地址冲突,就都填入溢出表。

(20)面向对象的三大特性?

继承、封装、多态

(21)多态的实现?

(1)编译时的多态性。编译时的多态性是通过重载来实现的。对于非虚的成员来说。系统在编译时,根据传递的参数、返回的类型等信息决定实现何种操作。

(2)运行时的多态性。运行时的多态性就是直到系统运行时,才根据实际情况决定实现何种操作。C++中,运行时的多态性通过虚函数实现。

(22)深拷贝和浅拷贝的区别?

浅拷贝

对一个已知对象进行拷贝,编译系统会自动调用一种构造函数——拷贝构造函数,如果用户未定义拷贝构造函数,则会调用默认拷贝构造函数,调用一次构造函数,调用两次析构函数,两个对象的指针成员所指内存相同,但是程序结束时该内存却被释放了两次,会造成内存泄漏问题。

深拷贝

在对含有指针成员的对象进行拷贝时,必须要自己定义拷贝构造函数,使拷贝后的对象指针成员有自己的内存空间,即进行深拷贝,这样就避免了内存泄漏发生,调用一次构造函数,一次自定义拷贝构造函数,两次析构函数。两个对象的指针成员所指内存不同。

总结:浅拷贝只是对指针的拷贝,拷贝后两个指针指向同一个内存空间,深拷贝不但对指针进行拷贝,而且对指针指向的内容进行拷贝,经深拷贝后的指针是指向两个不同地址的指针。

(23)vector的实现原理

vector的数据安排以及操作方式,与array非常相似。两者的唯一区别在于空间的运用的灵活性。array是静态空间,一旦配置了就不能改变;要换个大(或小)一点的房子,可以,一切琐细都得由客户端自己来:首先配置一块新空间,然后将元素从旧址一一搬往新址,再把原来的空间释还给系统。vector是动态空间,随着元素的加入,它的内部机制会自行扩充空间以容纳新元素。因此,vector的运用对于内存的合理利用与运用的灵活性有很大的帮助,我们再也不必因为害怕空间不足而一开始要求一个大块头的array了,我们可以安心使用array,吃多少用多少。

vector的实现技术,关键在于其对大小的控制以及重新配置时的数据移动效率。一旦vector的旧有空间满载,如果客户端每新增一个元素,vector的内部只是扩充一个元素的空间,实为不智。因为所谓扩充空间(不论多大),一如稍早所说,是” 配置新空间/数据移动/释还旧空间 “的大工程,时间成本很高,应该加入某种未雨绸缪的考虑。稍后我们便可看到SGI vector的空间配置策略了。

另外,由于 vector维护的是一个连续线性空间,所以vector支持随机存取 。

注意:vector动态增加大小时,并不是在原空间之后持续新空间(因为无法保证原空间之后尚有可供配置的空间),而是以原大小的两倍另外配置一块较大的空间,然后将原内容拷贝过来,然后才开始在原内容之后构造新元素,并释放原空间。因此, 对vector的任何操作,一旦引起空间重新配置,指向原vector的所有迭代器就都失效了 。这是程序员易犯的一个错误,务需小心。

(24)C++ 源代码到可执行代码的详细过程 ?

https://maplefan.com/index.php/2018/12/06/编译预处理/

(25)memcpy和strcpy的区别 ?

memcpy和strcpy的区别?

strcpy和memcpy主要有以下3方面的区别。

复制的内容不同。strcpy只能复制字符串,而memcpy可以复制任意内容,例如字符数组、整型、结构体、类等。
复制的方法不同。strcpy不需要指定长度,它遇到被复制字符的串结束符”\0″才结束,如果空间不够,就会引起内存溢出。memcpy则是根据其第3个参数决定复制的长度。
用途不同。通常在复制字符串时用strcpy,而需要复制其他类型数据时则一般用memcpy,由于字符串是以“\0”结尾的,所以对于在数据中包含“\0”的数据只能用memcpy。
从s1复制字符串到s2

strncpy和memcpy很相似,只不过它在一个终止的空字符处停止。当n>strlen(s1)时,给s2不够数的空间里填充“\0”(n为s2的空间大小);当n<=strlen(s1)时,s2是没有结束符“\0”的,所以使用strncpy时,确保s2的最后一个字符是“\0”。

(26)vector删除数据时有什么需要注意的吗 ?

先用迭代器指向vector的起始位置,然后用while循环,找到符合的元素,删除迭代器所指向的元素,返回一个指向被删元素之后元素的迭代器,这时不能在自增了,因为迭代器指针已经指向下一个元素了,如果在自增,就将被删除的元素的后面一个元素就跳过去了,如果在被删除的元素在末尾,那么迭代器指针就会变成野指针。

(27)虚函数和纯虚函数的区别?

虚函数

引入原因:为了方便使用多态特性,我们常常需要在基类中定义虚函数。

纯虚函数在基类中是没有定义的,必须在子类中加以实现。

纯虚函数

引入原因:在很多情况下,基类本身生成对象是不合情理的。

纯虚函数就是基类只定义了函数体,没有实现过程,定义方法如下;

virtual void Eat() = 0; 直接=0 不要 在cpp中定义就可以了。

纯虚函数相当于接口,不能直接实例话,需要派生类来实现函数定义。

虚函数在子类里面也可以不重载的;但纯虚必须在子类去实现,

普通成员函数是静态编译的,没有运行时多态,只会根据指针或引用的“字面值”类对象,调用自己的普通函数;虚函数为了重载和多态的需要,在基类中定义的,即便定义为空;纯虚函数是在基类中声明的虚函数,它可以再基类中有定义,且派生类必须定义自己的实现方法。

一旦父类的成员函数声明virtual,其子类的函数不管有没有声明为virtual,都是虚函数。

普通函数如果不被使用,可以只有声明没有定义,虚函数必须要有定义,即使是一个空实现,因为编译器无法确定会使用哪个函数。

(28)C++中overload,override,overwrite的区别?

Overload(重载):在C++程序中,可以将语义、功能相似的几个函数用同一个名字表示,但参数或返回值不同(包括类型、顺序不同),即函数重载。
(1)相同的范围(在同一个类中);
(2)函数名字相同;
(3)参数不同;
(4)virtual 关键字可有可无。

Override(覆盖):是指派生类函数覆盖基类函数,特征是:
(1)不同的范围(分别位于派生类与基类);
(2)函数名字相同;
(3)参数相同;
(4)基类函数必须有virtual 关键字。

Overwrite(重写):是指派生类的函数屏蔽了与其同名的基类函数,规则如下:
(1)如果派生类的函数与基类的函数同名,但是参数不同。此时,不论有无virtual关键字,基类的函数将被隐藏(注意别与重载混淆)。

(2)如果派生类的函数与基类的函数同名,并且参数也相同,但是基类函数没有virtual关键字。此时,基类的函数被隐藏(注意别与覆盖混淆)。

(29)C++中四种强制类型转换 ?

去const属性用const_cast。

基本类型转换用static_cast。

多态类之间的类型转换用daynamic_cast。

不同类型的指针类型转换用reinterpret_cast。

(30)有了malloc/free,为什么还要new/delete?

malloc与free是C/C++的标准库函数,new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。

对于非内部数据类型的对象而言,光用malloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数,对象的消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符,不在编译器控制权限之内,不能够把执行构造函数和析构函数的任务强加于malloc/free。

因此,C++需要一个能完成动态内存分配和初始化工作的运算符new,以及一个能完成清理与释放内存工作的运算符delete。注意:new/delete不是库函数。

(31)map可以用结构体作为键值吗,注意事项?

在使用map时,有时候我们需要自定义键值,才能符合程序的需要。

比如我们需要使用自定义的结构体来作为map的键值。

键值无法比较。因为map的键值是自动比较后进插入的,键值是递增的。

现在我们自定义的键值,编译器无法进行比较,找不到类似的模板,所以报错。

既然是没有‘<’,那我们自己重载小于操作符应该就可以了。

(32)Volatile的作用?

voliate变量是随时变化的,用voliate修饰的运算,编译器不进行优化,以免出错。

对于一个普通变量,为提高存取速率,编译器会先将变量的值存储在一个寄存器中,以后再取变量值时,就存寄存器中取出。

但是用voliate修饰的变量,就说明这个变量会发生意向不到的改变。也就是说,优化器每次在读取该值时,不会假设这个值了,每次都会小心的在读取这个变量的值,而不是在寄存器中取保留的备份。

那么,一个参数可以同时被const和voliate修饰吗?
答案是可以的,如:只读的状态寄存器。它是voliate,是因为它可能会发生意想不到的改变;它是voliate,表示程序不应该试图去改变它。

(33)了解哪些C++11特性?

https://blog.csdn.net/chen134225/article/details/80976666

(34)右值引用和move语义?

不知道

(35)STL里resize和reserve的区别?

  • size():返回vector中的元素个数
  • capacity():返回vector能存储元素的总数
  • resize()操作:创建指定数量的的元素并指定vector的存储空间
  • reserve()操作:指定vector的元素总数

resize():改变当前容器内含有元素的数量(size()),eg: vector<int>v; v.resize(len);v的size变为len,如果原来v的size小于len,那么容器新增(len-size)个元素,元素的值为默认为0.当v.push_back(3);之后,则是3是放在了v的末尾,即下标为len,此时容器是size为len+1;

reserve():改变当前容器的最大容量(capacity),它不会生成元素,只是确定这个容器允许放入多少对象,如果reserve(len)的值大于当前的capacity(),那么会重新分配一块能存len个对象的空间,然后把之前v.size()个对象通过copy construtor复制过来,销毁之前的内存;

只有当容器内元素数(size)大于capcity时,容器才会改变地址。

(36)vector和deque的区别?

vector是单向开口的连续线性空间, deque是一种双向开口的连续线性定 ;

deque允许于常数时间内对起头端进行元素的插入或移除操作 ;
deque没有所谓容量(capacity)观念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。

(37)不同排序算法的比较?

在这里插入图片描述

(38)大端和小端的区别,以及如何判断一台机器是大端还是小端?

大端模式,是指数据的高字节保存在内存的低地址中,而数据的低字节保存在内存的高地址中,这样的存储模式有点儿类似于把数据当作字符串顺序处理:地址由小向大增加,而数据从高位往低位放;这和我们的阅读习惯一致。
小端模式,是指数据的高字节保存在内存的高地址中,而数据的低字节保存在内存的低地址中,这种存储模式将地址的高低和数据位权有效地结合起来,高地址部分权值高,低地址部分权值低。
int checkCPU()
{
    union w
    {
        int a;
        char b;
    }c;
    c.a = 1;
    return (c.b == 1);//小端返回1,大端返回0
}

(39)malloc分配内存的原理?

步骤分为放置、分割和合并

在堆中,堆块由一个字的头部、有效载荷、填充以及一个字的脚部组成,空闲块是通过头部中的大小字段隐含地连接在一起形成一个隐式空闲链表,分配器可以通过遍历堆中所有的块,从而间接遍历整个空闲块的集合。

1、放置已分配的块

当一个应用请求一个k字节的块时,分配器搜索空闲链表,查找一个足够大可以放置所请求块的空闲块,分配器执行这种搜索的方式是放置策略确定的。常见的策略是首次适配、下一次适配和最佳适配。

首次适配:从头开始搜索空闲链表,选择第一个适合的空闲块。

下一次适配:从上一次查询结束的地方开始搜索空闲链表,选择第一个适合的空闲块。

最佳适配:检查每个空闲块,选择适合所需请求大小的最小空闲块。

2、分割空闲块

一旦分配器找到一个匹配的空闲块,它就必须做另一个策略决定,那就是分配这个空块中多少空间。一个选择是用整个空闲块,另一个选择是将这个空闲块分割成两部分。

如果分配器不能为请求块找到合适的空闲块将发生什么呢?一个选择是通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块。然而,如果这样还是不能生成一个足够大的块,或者如果空闲块已经最大程度地合并了,那么分配器就会通过调用sbrk函数,向内核请求额外的堆内存,分配器将额外的内存转化成一个大的空闲块,将这个块插入到空闲链表中,然后将被请求的块放置在这个新的空闲块中。

3、合并空闲块

Knuth提出了一种聪明而通用的技术,叫做边界标记,允许在常数时间内进行对前面的块合并。这种思想是,在每个块的结尾处添加一个脚部,其中脚部就是头部的一个副本,如果每个块包括这样一个脚部,那么分配器就可以通过检查它的脚部,判断前面一个块的起始位置和状态,这个脚部总是在当前块开始位置一个字的距离。

(40)为什么构造函数不能声明为虚函数,析构函数可以,构造函数中为什么不能调用虚函数?

1 构造一个对象的时候,必须知道对象的实际类型,而虚函数行为是在运行期间确定实际类型的。而在构造一个对象时,由于对象还未构造成功。编译器无法知道对象 的实际类型,是该类本身,还是该类的一个派生类,或是更深层次的派生类。无法确定。。。

2 虚函数的执行依赖于虚函数表。而虚函数表在构造函数中进行初始化工作,即初始化vptr,让他指向正确的虚函数表。而在构造对象期间,虚函数表还没有被初 始化,将无法进行。

(41)STL中unordered_map 和 map的区别 ?

一、hash_map与unordered_map

这两个的内部结构都是采用哈希表来实现。区别在哪里?unordered_map在C++11的时候被引入标准库了,而hash_map没有,所以建议还是使用unordered_map比较好。

哈希表的好处是什么?查询平均时间是O(1)。顾名思义,unordered,就是无序了,数据是按散列函数插入到槽里面去的,数据之间无顺序可言,但是有些时候我只要访问而不需要顺序,因此可以选择哈希表。举个最好的例子,就是我的LeetCode的博文里——Longest Consecutive Sequence这一题,我的方法二就是用的unordered_map来实现“空间弥补时间”这样的做法。

二、unordered_map与map

虽然都是map,但是内部结构大大的不同哎,map的内部结构是R-B-tree来实现的,所以保证了一个稳定的动态操作时间,查询、插入、删除都是O(logn),最坏和平均都是。而unordered_map如前所述,是哈希表。顺便提一下,哈希表的查询时间虽然是O(1),但是并不是unordered_map查询时间一定比map短,因为实际情况中还要考虑到数据量,而且unordered_map的hash函数的构造速度也没那么快,所以不能一概而论,应该具体情况具体分析。

三、unordered_map与unordered_set

后者就是在哈希表插入value,而这个value就是它自己的key,而不是像之前的unordered_map那样有键-值对,这里单纯就是为了方便查询这些值。我在Longest Consecutive Sequence这一题,我的方法一就是用了unordered_set,同样是一个将空间弥补时间的方法。再举个大家好懂的例子,给你A,B两组数,由整数组成,然后把B中在A中出现的数字取出来,要求用线性时间完成。很明显,这道题应该将A的数放到一个表格,然后线性扫描B,发现存在的就取出。可是A的范围太大,你不可能做一个包含所有整数的表,因为这个域太大了,所以我们就用unordered_set来存放A的数,具体实现库函数已经帮你搞定了,如果对于具体怎么去散列的同学又兴趣可以查看《算法导论》的第11章或者《数据结构与算法分析》的第五章,如果要看《算法导论》的同学我给个建议,完全散列你第一遍的时候可以暂时跳过不看,确实有点复杂。

(42)C/C++中extern的用法 ?

在C语言中,修饰符extern用在变量或者函数的声明前,用来说明“此变量/函数是在别处定义的,要在此处引用”。

1:extern修饰变量的声明。举例来说,如果文件a.c需要引用b.c中变量int v,就可以在a.c中声明extern int v,然后就可以引用变量v。这里需要注意的是,被引用的变量v的链接属性必须是外链接(external)的,也就是说a.c要引用到v,不只是取决于在a.c中声明extern int v,还取决于变量v本身是能够被引用到的。这涉及到c语言的另外一个话题--变量的作用域。能够被其他模块以extern修饰符引用到的变量通常是全局变量。还有很重要的一点是,extern int v可以放在a.c中的任何地方,比如你可以在a.c中的函数fun定义的开头处声明extern int v,然后就可以引用到变量v了,只不过这样只能在函数fun作用域中引用v罢了,这还是变量作用域的问题。对于这一点来说,很多人使用的时候都心存顾虑。好像extern声明只能用于文件作用域似的。

2:extern修饰函数声明。从本质上来讲,变量和函数没有区别。函数名是指向函数二进制块开头处的指针。如果文件a.c需要引用b.c中的函数,比如在b.c中原型是int fun(int mu),那么就可以在a.c中声明extern int fun(int mu),然后就能使用fun来做任何事情。就像变量的声明一样,extern int fun(int mu)可以放在a.c中任何地方,而不一定非要放在a.c的文件作用域的范围中。对其他模块中函数的引用,最常用的方法是包含这些函数声明的头文件。

使用extern和包含头文件来引用函数有什么区别呢?
extern的引用方式比包含头文件要简洁得多!extern的使用方法是直接了当的,想引用哪个函数就用extern声明哪个函数。这大概是KISS原则的一种体现吧!这样做的一个明显的好处是,会加速程序的编译(确切的说是预处理)的过程,节省时间。在大型C程序编译过程中,这种差异是非常明显的。

3:此外,extern修饰符可用于指示C或者C++函数的调用规范。比如在C++中调用C库函数,就需要在C++程序中用extern “C”声明要引用的函数。这是给链接器用的,告诉链接器在链接的时候用C函数规范来链接。主要原因是C++和C程序编译完成后在目标代码中命名规则不同。

(43)I/O模型

https://blog.csdn.net/chen134225/article/details/81749980
(44)TCP和UDP的应用场景,从生活中使用的APP的一些例子来讲。

当对网络通信质量有要求时,比如:整个数据要准确无误的传递给对方,这往往对于一些要求可靠的应用,比如HTTP,HTTPS,FTP等传输文件的协议,POP,SMTP等邮件的传输协议。常见使用TCP协议的应用:
1.浏览器使用的:HTTP
2.FlashFXP:FTP
3.Outlook:POP,SMTP
4.QQ文件传输

对当前网络通讯质量要求不高的时候,要求网络通讯速度尽量的快,这时就使用UDP
日常生活中常见使用UDP协议:
1.QQ语音
2.QQ视频
(45)判断两个链表是否相交。

1.判断两个链表最后一个结点是否相同。

2.将第二个链表的头结点接在第一个链表的尾结点后,判断合成的链表是否形成了环。
(46)二叉树的广度优先遍历和深度优先遍历。

//深度优先搜索
//利用栈,现将右子树压栈再将左子树压栈
void DepthFirstSearch(BitNode *root)
{
    stack<BitNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty())
    {
        BitNode *node = nodeStack.top();
        cout << node->data << ' ';
        nodeStack.pop();
        if (node->right)
        {
            nodeStack.push(node->right);
        }
        if (node->left)
        {
            nodeStack.push(node->left);
        }
    }
}

//广度优先搜索
void BreadthFirstSearch(BitNode *root)
{
    queue<BitNode*> nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty())
    {
        BitNode *node = nodeQueue.front();
        cout << node->data << ' ';
        nodeQueue.pop();
        if (node->left)
        {
            nodeQueue.push(node->left);
        }
        if (node->right)
        {
            nodeQueue.push(node->right);
        }
    }
}

(47)快排,堆排,归并哪些是稳定的,假如我要用C++封装一个sort我要用那种比较好。

只有归并是稳定的,封装的话看需求。
(48)现在有一百万个数不重复我要使用那种排序最快最好。

内存足够,快速排序。

内存不够,多路归并排序。

1.静态变量跟普通变量的区别
2.静态函数跟普通函数的区别
3.进程和线程
4.线程间通信
5.互斥锁和信号量的区别
6.传递函数时,传递指针和传递指向指针的指针
7.在函数里定义数组,可以返回该数组名么
8.堆和栈的区别
9.数组和链表
10.链表的逆序
11.链表的内容
12.utf-8和Unicode
13.宽字符

 

一面(问基础知识):
自我介绍;
介绍完开始问基础
排序算法有哪些,复杂度
复杂度相同,快排的优势
讲一下STLvector list 等的底层实现
存放数据量比较大的时候选择vector还是list,数据量比较小的时候呢
栈和队列的区别
死锁的条件
进程线程优缺点
进程通信方式
类成员访问控制方式有哪些(private和protected区别)
常用设计模式讲一下
malloc和new的区别
快排思想
二面:(一面完10分钟左右继续)
进程的状态
死锁的条件,解决死锁的方法
问了三个算法没听过,直接回答不会
讲一下内存管理,自由存储区是什么
malloc内存分配底层操作,用malloc分配内存1k和100M有什么区别
TCP三次握手和四次挥手
三次握手过程中做了哪些准备(没答好)
为什么有TIME_WAIT
设计抢红包算法(一直问问了很多)

1.局部变量,全局变量,分别存在内存哪个位置
2.程序内存的分布,五个部分
3.new,malloc区别
4.数据结构相关问题,闲聊
5.C STL了解,说说vector,list,map区别
6.分析他们的性能
7.TCP三次握手,两次为什么不行
8.TCP,UDP区别
9.进程通信的几种方式(管道,有名管道,信号,信号量,共享内存,消息队列,套接字)
10.分析他们的区别,用于那些场景
11.链表倒数第k个数,程序思路
12.快排思路
没有手撕代码
等了一会然后通知二面
二面技术面,首先自我介绍,然后介绍项目
项目里面有多线程然后一直追问细节,二面一点紧张,答得不好。
1.项目里面用到了C 什么新特性(太抽象,答得很差)
2.堆栈的区别
3.TCP,UDP了解多少
4.B-树,B 树区别和原理,效率,应用场景,写过代码没,项目里面有没有用到(不会,没有用到)
5.项目里面除了vector还用到那些数据结构
6.红黑树

作者:从0开始学c
链接:https://www.nowcoder.com/discuss/128236
来源:牛客网

然后问算法,问了反转链表,要求空间复杂度o1,我在循环内用了一个局部指针变量,虽然不优雅,但是局部变量每次循环完都会被析构,他硬说我的空间复杂度是on。

然后问了虚函数,这是唯一问的c++,我感觉他也就会个虚函数了。

然后问找前k大的数。

我: 如果内存放得下的话,用类似快排的思想,partition把大的放左边,小的放右边,调用partition之后,如果分界元素等于k,则返回最左边的k个值;否则对k所在的半边递归调用parition,平均时间复杂度是on。

面试官(惊讶): 时间复杂度是on?

我: 是啊

面试官: 真的是么?

我: 是啊,假如每次分界完,平均下次要处理的元素占总元素数的a/b,那么时间近似是(1+a/b+(a/b)^2+…)n= b/a*n

面试官: 那我的k要是很大,接近n,你这个不就是n平方了么

我: a/b是平均下次要处理的元素占本次处理的总元素的比值,跟k无关

面试官: 那最坏时间复杂度是多少

我: on^2 当数组已经有序,每次处理完规模减少1。 如果你觉得这个方法不好,在内存放得下的情况下,那我们用堆做,建一个最大堆,建堆的时间复杂度是on,调整k次,调整一次的时间复杂度是ologn,一共是o(n+klogn)

面试官: 建堆的时间复杂度是on?

我: 有什么疑问么

面试官: 你确定?

我: 确定!

面试官: 你再想想?

我: 建堆是从最后一个非叶结点开始调整,倒数第二层最多有n/2个需要调整的元素,最多需要调整1次,倒数第三层最多有n/4个需要调整的元素,每个最多需要调整2次,以此类推,最后累加起来接近线性时间复杂度。

面试官: 额…

我: 换一种方法,如果数据比较大,内存放不下,可以用优先队列,实现也是堆。优先队列是用一个最大堆,我们求前k大要用最小堆,所以要重载小于号运算符,优先队列重载时候要指定底层容器,我一般指定的是vector。执行时候如果队列里面的元素少于k个,则直接插入;否则将该元素与top()比较,如果大则删掉top把这个元素放到队列中。

面试官:额..

我: 如果重复元素算一个,就用set,set是默认从小到大排列的,所以不需要重载运算符。

然后面试官没有回话,思考了一会,用“你会数据库么”结束了对算法的问询。在得知我不会数据库之后,面试官开始了他的主导,一直问数据库。我说,我不会数据库,要不你问问别的吧。然后他问我会网络么,我说曾经会一些,很久没用了,于是就问我tcp连接的终止,在我答完四次握手之后,问我服务器单方面终止链接之后,客户端继续发送数据会怎么样; 双方都终止了之后,客户端继续向服务器发送数据会怎么样。
如何处理get和post
tcp接收窗口和拥塞窗口
什么时候会向对端传窗口大小
extern C的意义
假设rtt(数据从两端一来一回) 100ms,那么从输入一个http://url到得到网页要多少时间
https呢?
连续发送两次http请求,会得到两次结果吗?可能第二次比第一次快吗?
是否了解TCP包头阻塞?
服务器状态502 503 504什么问题,怎么排查
netstat具体查看什么问题
写题:多路归并(用了堆,在细节上有一些问题)
看代码中的问题:
class Foo
{
public:
Foo(){_p = new int();}
~Foo() {delete _p; _p = nullptr;}
private:
int* _p;
}
sql:三句查询,要求建立索引来优化查询
一些linux语句的作用:less more sed awk du df dd at tee crotab xargs
最近看了什么技术书籍

二面
linuxIO模型,区别在哪
线程独立拥有哪些资源
协程和线程有什么差别,优势呢?
get和post有什么差别
sendfile的优势在哪?
代码:随机播放100首歌(洗牌算法/这个我把自己绕进去了,洗一次直接输出就完了,我当时脑子短路了,洗一次播一首非要再洗一次来手动提升复杂度,最后没绕出去,然后换题了)
两个倒序数组找最第k大的(框架差不多,最后发现漏了一种情况,感觉还在想洗牌的事情)

因为二面代码花了很久,最后没写完,当时心态有点崩,但给了三面

三面
三面没有写代码,问了一个小时,面试官全程半启发半追问,感觉有点懵,我把上下文相关的问题空格分段了

C/C++内存问题有哪些,尽量说
free和delete在具体实现上的差异
free之后的指针使用有什么问题
缓冲区溢出如何避免,有哪些场景
如何检查/处理越界
野指针和悬空指针分别是什么
试图使用野指针有什么问题
内存上还有别的问题吗?

C++11用过什么特性

之前讲的内存问题有什么好的方法吗?
智能指针讲一下
shared_ptr讲一下,怎么实现的,unique_ptr呢?
是不是所有要用指针的地方都应该用智能指针,有什么问题和不足?(我答了两次寻址和额外空间)
这些缺陷,在不用shared_ptr的前提下有减少成本的策略吗?(跳过了)

include,头文件里面一般放了些什么
声明和实现要写在一起吗?是不是一定要分开写?
写在一起和分开对最后的代码有什么影响,怎么确认(这个我不会,面试官让我试着分析一下,结合include的行为来谈)
gdb怎么查看一个函数的地址?
你在Linux使用经常哪些指令
如何探查CPU负载情况
在什么时候CPU被认为是繁忙/空闲的?

看过哪些比较大的代码?(后面很多问题是从这来的)

服务器:
多线程服务器和nginx在工作方式有什么不一样的地方
nginx怎么处理请求
进程唤醒(惊群问题)的额外成本主要在哪?
nginx的负载均衡(我只答了那个worker的负载均衡)
为什么它要用多进程,优势在哪,劣势在哪
多线程怎么应付同样的问题,能够解决吗,讲一讲方案
你的方案有什么问题?

http了解多少?
http缓存机制了解吗?
长连接讲一下
如何实现长连接(保活)
带外数据如何使用?
你的这个方法有什么问题,可以直接兼容不同的浏览器吗?
了解nginx的解决方案吗?

redis
你对redis怎么理解的?
redis的总体结构
单线程的优势和缺点
redis的事件分发
讲一讲文件事件有哪些
client功能是怎么实现的
时间事件(serverCron函数)
serverCron做了什么
redis所有事情都只有一个单线程吗?
bgsave讲一下,为什么要fork一个进程来做

interrupt与signal有什么差别
interrupt的发起和接受者是谁
操作系统在interrupt中发挥了什么作用
signal呢,发起者又是谁,接收者呢?(这里答得有点混乱)

TCP
ack什么时候发送,丢失了会怎么样?
sack了解吗?
重传ack的时机只有ack超时吗?
重复报文被接收会发生什么?
拥塞窗口要不要把自己的大小发给接收方,意义何在?(这个问题一面也问了,没有答出来)
延迟ACK的意义在哪?
为什么不能每次都直接发大的窗口?

进程地址空间布局讲一下
BSS为什么要叫这个名字?(后来查了,block started by symbol)
static关键字有什么作用,如果用来修饰函数呢?
多个线程使用static数据会开启多个副本吗?

C++OO
多重继承怎么实现
虚拟继承怎么实现
对于函数寻址在时间成本上有什么差异?
对于继承体系很复杂的情况这个成本会被拉高吗?

 

算法:
1. 两个相交的单链表,找出交点
2. 给一棵树,找出路径和为n的路径
基础:
1. static关键字
2. 在一个函数内定义一个static对象,什么时候构造和析构。如果这个函数从没被调用,会怎么被析构
3. tcp连接和断开
4. 服务器大量close_wait状态,可能是什么原因,怎么解决
一面还有很多问题的,忘了。。。
一面感觉:那个两个相加的单链表的算法,我提出的算法他没见过,然后我证明,然后balabala说的不好,然后跳了。。。
这也是一面唯一一个感觉面的不好的地方
二面:
1. 设计LRU cache,查找复杂的O(1), 过期淘汰
数据库:
2. 联合索引, 最左匹配
3. 假如有联合索引<a,b>,查询where a=xx and c == yy,会用到联合索引么 为什么
4. 如果数据库主键是单调严格递增的,有一个图片,通过url带上id访问,然后查询数据库,会有什么影响
5. 上面那个问题,引出一个情景题,如何设计一个序列生成器,能够单调递增,但是不是严格递增的 ?保存在内存中,宕机怎么办?多个进程怎么办?
这个问题和面试官聊了很久,因为我在微信这边不久前看到过序列生成器
6. 解决并发情况下,使序列生成器生成的id唯一。还有就是在分布式系统,多机服务器怎么办?
7.
long multiply(int m,int n) {
long score;
score = m * n;
return score;
}
这段代码会有什么问题? 然后就说了一下m*n溢出
8.
请问下面的程序一共输出多少个 “-”?,执行一次下面的程序,总共生成了多少个进程?
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main(void) {
int i;
for(i=0; i<2; i ) {
fork();
write(1, “-“, 1);
}
wait(NULL);
wait(NULL);
return 0;
}
我说了6次,然后解释了一遍
9. 然后说把write换成printf会多少个’-‘, 我算了一下,说8次,原因是printf是有缓存的
10. c语言程序的内存模型
11. 聊redis , 如果内存已经很多键了,会怎么样?然后说了一下cow 还有balabala
还有一些小问题完了
二面总结:最后的redis因为时间不够,然后面试官说结束了。感觉二面面的挺好的,和面试官聊的也很多
三面:
三面一看就是大佬,他一直在看我的简历,开始那7分钟,大家一句话都没说,很尴尬
1. 写sql
Sid:学号
Cid:课程编号
score:成绩
查询平均成绩大于 60 分的同学的学号和平均成绩
2.
void pass(){
}
int main( ) {
int x;
x = 123;
printf(“%d \n”,x);
pass();
printf(“%d \n”,x);
return 0;
}
// 123
// 456
他问在pass里面添加代码,使输出123和456
因为都在栈里面,有返回地址,占四个字节
void pass(){
int y;
int *addr = &y;
addr 加加  ;
addr加加   ;
*addr = 456;
}
大概思路是这样, 细节有待斟酌
算法题:
3.
随机数生成器:
float rand(); [0,1)
int rand5();
int rand7();
这个通过rand,然后写出rand5,最后写出rand7。面试官刚开始说rand返回[0,1),然后让我写代码验证,
我心里一凉,是不是写错了。果然跑的结果不对,然后现场debug,rand返回的是一个unsigned int,根本不是[0,1),
然后改好了
4. 写一个函数,N 个数字,找到其中第 K 大的数,要求平均时间复杂度尽量低。
我写出来后他让我算时间复杂度,时间复杂度一直没算对,还用了主定理。 作为一个理科生,最后时间复杂度要数列求和,没求出来,很惭愧
5.http状态码
tcp的连接,怎么用udp模拟tcp
数据库索引了解吗(b 树)
那为什么用b 树,有什么优点呢

多态,虚表虚指针,虚基类以及内存分布

函数重载
构造函数和复制构造函数能否为虚,为什么
一个对象的内存分布,多个虚函数占多大空间
shared_ptr介绍原理,weak_ptr如何解决引用传递
右值引用
编译器如何处理模版
编译中的导出符号表和未决符号表
反汇编时符号表的状态
比较c++和java
介绍一下stl的list,查找list复杂度
unorder_map插入复杂度
stl迭代器重载
遍历vector的几种写法
数据库常用数据结构,b+树的好处
图的bfs和dfs
快排,复杂度,最坏情况以及设计算法解决
tcp和udp
如何用udp封装实现tcp
进程和线程
如何保证线程安全
互斥锁原理和使用

1、inline的用法?

2、class A

{

int a;

short b;

int c;

}

sizeof(A)的大小?类中加上double d;呢?

3、你知道什么排序算法?它们的平均复杂度各是多少?其中稳定的排序有哪些?

4、说一下快排。它的最坏复杂度是多少?什么情况下最坏?

5、说一下归并?

6、哈希是什么?哈希如何存储数据?什么情况下用到哈希?

7、说一下static的作用?

8、虚函数你知道吗?它是如何实现的?

9、如何让一个类被有限次数的实例化?

10、纯虚函数是什么?如何定义?

11、一个类如何被称为抽象类?抽象类可以实例化吗?为什么?

12、如何比较两个对象?

13、跳台阶,一次跳1阶或2阶,n阶有多少种跳法?(最多能跳n阶呢?)(动态规划,递归)

14、一个链表,实现它的翻转。(当时定义了三个指针, = =反正挺简单的)

15、有一个数组,所有数据都可以是负数、0、正数,求和最大的连续序列。如果是一个矩阵呢?(矩阵的没答上)

16、stl库懂吗?你常用的有什么?

17、vector的底层是什么?它是如何实现动态分配空间的?如果将其中一个元素删除,那么它的地址空间是怎么样的?

18、map、set知道吗?(知道,底层红黑树。既然你说到红黑树,那说一下红黑树是什么?它的实质是什么?如何实现的?)说一下它们的区别?

19、线程和进程的区别?线程间如何通信?线程共享的资源有什么?

20、TCP和UDP的区别?TCP如何实现可靠传输?它们的传输方式?

21、socket懂吗?如何实现?

22、堆和栈的区别?
二面(可能有一些在上面,具体也记不清了):

23、给你一串字符串,压缩它有几种方法?

24、vector赋值n个数,它需要拷贝几次?

25、基类A,派生类B继承于A,A *a = new B[10]是否正确?会发生什么错误?a[5]能正确的取到对象吗?

26、两个链表,判断他们是否有相交部分?如果他们相交部分有环呢?

27、一副扑克,如何等概率洗牌?不消耗额外空间呢?

一面:
似乎是个不太厉害的面试官,只会问一些套路问题,一开始在纸上写好了一堆考察C++的笔试题,然后让你现场答。
有点印象的记得问了一些指向函数指针的数组怎么写?
char a[] = “test” char b[] = “test”
char *p = “test” char *t = “test”
a==b ?
p==t ?
然后基本一直考察算法:
二叉树非递归中序遍历。
讲一下因为保密协议不能说的笔试题(我觉得巨简单,然而一面面试官似乎并不能轻松看懂我的代码,现在回想起来感觉对网易的技术印象有点降低了)
一个ip地址段(由首地址ip和尾地址ip组成,保证连续)表,怎么找到一个ip属于其中哪一个地址段? (因为ip段不重合,根据首地址排序后二分找就可以了,感觉这题有点迷之简单。)
然后面试官就问ip段重合怎么办?然后当时没想出来,问题转化成查询覆盖一个点的所有线段。
二面:
这次还是有点分量的面试官。
一边充当hr一边充当面试官。
一致性哈希。
手撕智能指针。
给一个情景题,设想产生很多要求保序的请求从多个机器上发到一个多线程的代理上,再由代理调用分布式的数据库,怎么保证这个过程中的顺序不乱。
然后开始继续怼算法:
求一个数组左边之和最接近右边之和的节点。我想的是用前缀和来搞。
求中位数。
求一个流动数组的中位数,每次加入元素都要返回中位数,两个堆解决。

1,c++多态的实现。讲了c++虚函数表,单继承,多继承,虚继承以及为什么虚继承,调用过程
2,智能指针。
3,熟悉stl的什么结构。我说的是看过sgi 的stl源码。就问了什么情况用vector什么情况用list,
以及vector的insert,erase,remove的实现还有重新申请内存的情况

1.Base类有test方法,Base的不同对象调用test方法,内部是怎样的呢?(我答的指向同一个预先分配好的地方)

2.有一个AnotherBase类(与Base无关系)里面也有一个test方法,用其强制转换Base的对象,再调用这个对象的test方法,请问调用的是哪个类的方法?
3.在方法func()后面加const意味着什么?
4.给一个六面骰子,如何做出一个1~10的等概率随机方法?
5.用过什么设计模式?

  • C 和 C++ 的区别
  • new 和 malloc的区别
  • 对虚函数的理解
  • 多线程的理解(多线程同步的途径)
  • 多进程(继承什么, 不继承什么)
  • 进程间通信
  • gdb的使用, 编译器的使用
  • MySQL 查询前 100 条数据, 以及如何分组
  • 常见的Linux的命令
  • TCP和UDP的区别
  • socket的流程
  • 五种IO模型
  • linux基本操作
    • 拷贝文件 、查看ip、vim的基本操作(查找字符串、替换字符串)、gdb的调试;
    • 查看硬盘大小等等操作
    • 总结需要详细的看看linux的基本操作命令等(这部分很尴尬都不会)
  • STL
    • vector与list的区别
      • 怎么查找倒数第二位数字;
      • 二者的区别;
    • map怎么插入数据 有几种方式
      • 每种方式的优缺点;
  • 多线程多进程
    • 线程间同步的方式 :我答了 信号量、互斥量;问我还有没有 我说我记得就这几个了
    • 然后问我进程间同步的方式 答了一个临界区 ;忘了信号量和互斥量和事件了;
    • 然后我自己抢答了 进程间通信的方式:说了之后然后问我几个问题
      • 怎么创建管道 pipe()
      • 怎么创建共享内存shmget();
        1.自我介绍
        2.用过linux系统吗,哪种linux系统,版本呢?
        3.linux基本命令。怎么查看IP;怎么给文件改名;怎么查看文件的权限;修改权限;怎么加执行权限;怎么查看当前系统的版本;怎么查看当前系统硬盘空间的总量与使用情况;怎么查看系统内存多少;怎么查看某个命令执行的时候需要链接哪些系统库;怎么给一个文件做一个软链接;说一下gdb;怎么把一个test.cpp编译成一个test.so;
        4.vector与list的区别
        5.怎么找某vector或者list的倒数第二个元素
        6.说一下map和set的区别
        7.红黑树的原理
        8.map怎么插入数据,有几种方式
        9.c++11在原来的版本上都加了哪些东西。
        10.智能指针,三种指针都介绍一下其特性,作用。
        11.进程怎么同步,线程怎么同步,要说全。
        12.tcp与udp的区别,udp怎么实现多对多通信,问的很细,包括tcp的各种机制。
        13.说一下快排
        14.QT的信号槽是什么原理。

        C++基础

        • 自我介绍
        • 平时有用C++写过项目吗?(这里没让我展开说项目)
        • 对C++的特性有什么了解
        • 对封装、继承、多态的具体理解
        • public/protected/private的区别
        • 说一下三种方式继承对基类的访问权限
        • 说说构造函数的执行顺序,析构函数呢
        • 说一下构造函数内部干了什么
        • 如何实现多态
        • 构造函数和析构函数可以调用虚函数吗,为什么
        • 析构函数一定要是虚函数吗,为什么
        • 怎么理解C++的面向对象和C的面向过程
        • 可以介绍一下new的实现原理吗
        • new和malloc的异同处
        • C++怎么为各种变量分配内存空间的
        • 引用了解吧,介绍一下
        • 拷贝构造函数内部做了什么,什么时候需要重写
        • 初始化列表了解吗(以为是那个C11特性,没敢说)
        • 平时用什么编程环境(Windows+MFC+Qt)
        • 用过Qt是吧,说一下信号和槽的机制,绑定的方式
        • 你觉得MFC和QT比各自有什么优缺点
        • MFC的消息机制和Qt消息机制的对比

        进程线程相关

        • 了解过线程吗,谈一下进程和线程的联系和区别吧
        • 对于共享的区域多个进程或线程一起访问会不会出问题,要怎么解决(同步和互斥)
        • 进程通信有哪几种方式,介绍一下

        网络(项目里有)

        • Socket的流程是什么样的(服务端和客户端两个)
        • 项目里用的什么协议(TCP)
        • TCP和UDP的区别,优缺点

        数据库

        • 你这项目的数据库自己设计的吗,简单介绍一下你的设计流程
        • 了解数据库范式吗,介绍一下
        • 用过索引是吧,说一下索引的优缺点,选取条件
        • 数据库里多对多关系怎么处理设计

        数据结构

        • 说说vector和list的不同,优缺点
        • 平衡二叉树了解吗,说说它的特点,时间复杂度(logN)
        • 说说二叉树的三种遍历(想让我写来着,没带纸笔,口述了算法思想和区别,递归和非递归)
        • 图了解吗,说一说它的遍历(广度和深度)

        回到C++

        • 说说宏定义和const的区别
        • 宏定义和内联函数的区别
        • 内联函数的作用,和普通函数有什么区别
        • C++有几种转换方法,简单介绍一下
        • 重载是什么,和重写有什么区别

1.自我介绍
2.讲一下C new和malloc的区别

3.malloc内存分配机制是怎么样的,在哪里分配内存,最大可以申请多大的内存(三连击😂)

4.讲一下new运算符的原理(底层使用了operator new(),最终调用了malloc),new运算符重载用过吗,怎么写重载函数,重载的定义

5.memset函数的作用,有哪些参数

6.linux系统应用程序的内存空间是怎么分配的(内核空间和进程空间),一般进程空间多大,内核空间多大,进程空间分布是什么样的,堆区最大空间是多少

7.c   模板机制了解吗,讲一下原理,类模板和函数模板在定义时有什么区别

8.开始问数据结构,你了解二叉树吗,讲一下原理,平衡二叉树的原理讲一下,二叉树的遍历方式,二叉树的最大节点数,二叉树插入删除的时间复杂度,二叉树插入的时间复杂度与树的节点数和树深度的关系,二叉树的优点(二叉树这部分问了10几分钟😂)

9.数组和链表的区别讲一下,它们的应用场景

10.c 继承机制讲一下,虚继承了解吗,说一下原理

11.虚函数机制,一个类有虚函数,有成员变量,求所占的内存大小(这里一开始我没有考虑内存对齐,就直接按虚指针和成员变量的大小说,后面面试官提醒了一下才改过来)

12.看到简历上写了网络编程这块,就问了一下tcp和udp的区别,它们的应用场景(面试官拿王者荣耀来举例子,问像王者荣耀这样的游戏,服务器与客户端通信应该用什么机制),怎么实现服务器高并发,多连接

13. socket编程,问了connect函数和accept函数的作用和参数,epoll的原理大概讲一下