一面：1.C++11你了解吗？2.说一下右值引用？3.你了解引用折叠吗？4.你知道LRU吗，时间复杂度O（1）实现需要用到那些数据结构？5.你能设计一个通用符匹配的算法吗？6.虚函数有什么作用？7.你知道网络编程吗？8.你写过进程间的通信代码吗？9.你能说一个你打ACM时印象最深的一个题目吗？10.你知道无锁编程吗？11.你了解死锁产生的条件吗？12.有什么方法可以避免死锁吗？13.你了解IO多路复用吗？14.epoll的底层是红黑树，你了解吗？ 二面：纯聊天 暂时只记得这么多了，想到再加。

1.介绍一下大学中学过的课程？2.C，C++,java之间有什么区别？3.进程和线程的区别？4.你写过多线程的代码吗？5.用什么保证多线程在你的代码上正常运行？6.多进程通信的方式？7.消息队列解决了什么问题？8.如何让计算机只运行一个进程？9.数据库的三范式？10.数据库的索引是什么？11.类的封装遵守什么原则？12.给你一个学生上不同的课，你会怎么去封装？13.分布式存储redis?14.介绍了下实习？15.我反问技术栈是什么？面试官人很好的，看我这么菜也有耐心引导我。

1.static的作用：①：首先static的最主要功能是隐藏，其次因为static变量存放在静态存储区，所以它具备持久性和默认值0. ②：定义全局静态变量和局部静态变量：在变量前面加上static关键字。初始化的静态变量会在数据段分配内存，未初始化的静态变量会在BSS段分配内存。直到程序结束，静态变量始终会维持前值。只不过全局静态变量和局部静态变量的作用域不一样； ③定义静态函数：在函数返回类型前加上static关键字，函数即被定义为静态函数。静态函数只能在本源文件中使用； ④在变量类型前加上static关键字，变量即被定义为静态变量。静态变量只能在本源文件中使用； ⑤在c++中，stat...

首先跟我介绍了下，然后问了一下实习经历，最后就只问了三个题目第一题：a+b不用四则运算实现 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=1e9+7; const int N=1e6+5; int main() { int a, b; cin >> a >> b; int sum=a^b; b=(a&b)<<1; while(b) { int tmp=su...

基础题：1.数据在计算机上的存储形式是什么？答：数据和程序是以二进制形式存放的. 2.补码是什么？答：数值X的补码记作[x]补，如果机器字长为n，则最高位是符号位，0表示正号，1表示负号，正数的补码与原码反码都相同，负数的补码则等于其反码的末尾加1。数值0的补码表示有唯一的编码：[+0]补=0000 0000 ,[-0]补=0000 0000. 3.0X81+0X82的结果答：0x03 4.浮点数在计算机中如何存储？答：对于float型数据，其长度是4个字节，右边23位用来表示小数点后面的数字，中间8位用来表示e，左边一位用来表示正负。对于double型数据，其长度是8个字节，右边52位用...

题意：给与两个长度为n的a,b数组，你可以交换a数组中两个元素位置，你恰好进行k次操作后 的最大值？ 思路：首先我们思考一下什么样的两个数交换后的结果会大：假如有两对数:（a1,b1），（a2,b2）原结果为abs(a1-b1)+abs(a2-b2)如果a1>b1&&a2>b2&&b1>a2:那么原结果为abs(a1-b1)+abs(a2-b2)=a1+a2-b1-b2交换后结果为：abs(a1-b2)+abs(a2-b1)=a1-b2+b1-a2=a1+b1-a2-b2结果之差为2 * b1 - 2 * a2=2*min(a1,b1)-2 *...

题意：有一个n个节点的环，每一个节点有一个权值Ai,求两个节点i,j之间的Ai+Aj+dis(i,j)(i到j的距离)最大为多少？ 思路：单调队列首先将环转换成链，即加一段（n+1）~ (2*n),a[n+i]=a[i] (n>=i>=0)。在环上两点的距离小于等于n/2。设Ai+Aj+dis(i,j)=Ai+Aj+(i-j) (i>j)=(Ai+i)+(Aj-j) (i>j且i-j<=n/2)因为Ai+i是确定的，所以只需要求i的前（n/2）个节点的（Aj-j）的最大值，可以用单调递减队列维护,结果为i+Ai+（Aj-j）的最大值。 代码： #include&l...

题意：有一个n个节点，m条有向边的图，如果从1到n的最短路为d，请你求从1到n的路线长度小于d+k的数目，答案对p取模。 思路：最短路+记忆化搜索反向建图求每一个节点到n节点的最短距离。定义状态dp[i][j]为从节点i，还可以额外多走j的长度的状态到目标状态( dp[n][ji] (k>=ji>=0) )的路线数目.如何判断在到目标状态过程中有零环：如果他从dp[i][j]状态又回到了dp[i][j]状态则说明存在零环，此时就会有无数条路线。 代码： #include<bits/stdc++.h> #define ll long long #define eps 1...

题意：有n个站点，m条路线，每条路线使用一次要交1块钱，给出每条路线的信息，从一个站点到下一个站点的时间为1，让你求从一个站点到另一个站点的最小花费是多少，此时花费时间最大为多少？ 思路：最短路+拓扑+dp一看就是图论题，第一问求最小花费，如何用最短路求呢，对于每一条路线我们要创建两个虚点，一个虚点记录从起点到终点，另一个记录从终点到起点，从起点到终点使虚点对该路线的每一个节点连一条花费为0，时间为从该节点到起点的距离，每一个点连接一条到虚点的边，花费为1，时间为从该节点到起点的距离的相反数，从终点到起点使虚点对该路线的每一个节点连一条花费为0，时间为从该节点到终点的距离，每一个点连接一条到虚...

题意：有一颗n个节点的树，有k次操作，每次操作给出二个节点，然后将二个节点及二个节点之间的节点权值都加一，然后求最后树中权值最大的节点的权值为多少？ 思路：lca+差分：用lca求出二个节点u、v的最近公共祖先k，k的父亲节点为kp；要使u、v路经上节点权值加一则val[u]、val[v]进行加一，表示经过u、v节点时值加一，然后k位置此时相当与加了二，所以val[k]要减一，最后val[kp]减一表示经过kp节点时值减一。求点的权值时从叶子节点开始向根节点计算,取最大值当结果即可。 代码： #include<bits/stdc++.h> #define ll long long...

题意：有一个歌手要唱n首歌，每首歌在唱之前可以调节ci的音量,上调或者下调，但不能低于0或者高于maxLevel，初始音量为beginLevel，求最后一首歌音量最大为多少，如果不能满足规则，则输出-1. 思路：首先观察数据范围，我们发现n和maxLevel都不是很大，所有我们可以使用dp来写. 定义状态：dp[i][j]表示第i首歌是否可以达到j的音量，值为1表示可以，为0表示不可以。 转移方程：dp[i][j]=dp[i][j] || dp[i-1][j+ci] (上调) || dp[i-1][j-ci]（下调）; 初始化：dp[0][beginLevel]=1; 代码： #include...

题意：给你一个长度为n的序列，让你求序列的最大公约数为1的子序列数目为多少？ 思路：莫比乌斯反演首先统计一下该序列有什么数，个数为多少。然后求莫比乌斯函数。统计有i为因子的数有x。根据x求都有该因子的序列有 ( )个根据莫比乌斯函数判断该序列数是加上还是减去.最后得出结果. 代码： #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=1e9+7; const int N=2e5+5; ll x,mu[N], ma[N]; ll dp[N], prime[N], ji...

题意：给你一个n个点m条边的图，其中有k个节点是特殊的，起点s一定是特殊的，现在让你从s到t，每个特殊点可以加q点能量，经过一条边需要花费1点能量，求能从s到t时q最小为多少？（如果不能到达，输出-1） 思路：求最小值，然后这值又具有单调性，所以可以二分枚举答案。然后判断这个答案行不行可以用bfs（最好加优先队列优化）判断。 代码： #include<iostream> #include<cmath> #include<cstdio> #include<queue> #include<cstring> #define ll long ...