笔试真题刷题平台
精选近几年名企笔试真题，笔试之前刷刷真题，有备无患
用 C 语言写一个函数来执行一串任务。任务是互相依赖的。比如 B 任务依赖 A 任 务，则 A 完成 B 才能执行。不考虑并发限制，假设所有的任务都能一次执行成功， 所有的任务执行时间都相等。任务数据结构原型为：
typedef struct {
//该任务的 ID
int id;
//该任务依赖的任务的 ID
int *child;
//该任务依赖的任务个数
int child_num;
} task;
// 函数原型：
bool doschedule(task*pask，inttask_num);
//以下函数可以直接调用：
void dotask(int id); //执行一个进程
//等待 timeout 时间，并返回一个执行成功的任务的 id，如果没有任务在时间片内完成，则返回-1
int waittask(int timeout);
bool killtask(int id); //杀掉一个进程
阐述栈和堆在生命周期、速度、内存性能等方面的不同点。假如现在有一个缓冲 区域绝大多数只需要 1KB 空间，极少数极端情况下需要 100MB，怎么样合理分配内 存？
栈：栈存在于RAM中。栈是动态的，它的存储速度是第二快的。stack
堆：堆位于RAM中，是一个通用的内存池。所有的对象都存储在堆中。heap
2 申请方式
stack【栈】: 由系统自动分配。 例如，声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 。
heap【堆】: 需要程序员自己申请，并指明大小，在c中malloc函数 如p1 = (char *)malloc(10); 在C++中用new运算符 如p2 = (char *)malloc(10); 但是注意：p1、p2本身是在栈中的。
3 申请后系统的响应
栈【stack】：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆【heap】：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序；另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部分重新放入空闲链表中。
4 申请大小的限制
栈【stack】：在Windows下，栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。
堆【heap】：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
5 申请效率的比较
栈【stack】：由系统自动分配，速度较快。但程序员是无法控制的。
堆【heap】：是由new分配的内存，一般速度比较慢，而且容易产生内存碎片，不过用起来最方便. 另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活。
6 堆和栈中的存储内容
栈【stack】：在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。
堆【heap】：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容有程序员安排。 7 存取效率的比较 char s1[] = "aaaaaaaaaaaaaaa"; char *s2 = "bbbbbbbbbbbbbbbbb"; aaaaaaaaaaa是在运行时刻赋值的； 而bbbbbbbbbbb是在编译时就确定的； 但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
说明以下包含 const 修饰符的语句的意义
a). double * ptr=&value；
b). const double * ptr=&value;
c). double *constptr =&value;
d).const double *const ptr=&value;
const在前内容不能变,const在指针后则指针不能变
请问 c 语言中怎么去除 const 修饰？ 比如：
const double value=0.2f； double *ptr；
ptr 怎么样获取 value 的值？
Ptr=(int *)&value;
在一维坐标轴上存在许多条线段， 用最简单的算法找出重合长度最长得两条线段。 比如线段 A（1,5）、B（2,8）、C（3,9），则 B 和 C 的重合长度最长，为 5。
这个问题可以转换成一个动态规划问题：
比如我们想求Sn(Sn表示从求从第一个segment开始，总共有n个元素的子问题，求这个子问题的最大重合线段。)，首先我们要证明这是一个动态规划问题：
我们要求Sn问题的最大重合线段，那么它只有可能有两种来源：
（1）Sn-1问题的最大重合线段，即Sn的最大重合线段出自前n-1个线段；
（2）第n个线段Segment[n-1](注意：我是从0开始计数的，所以下标为n-1的就是第n个线段)和前n-1个线段的重合线段中最长的那一个。
所以，问题的解法如下：
（1）首先按照所有线段的end值对所有线段进行排序；
（2）递归的从后往前求解，比如求Sn的最大重合线段，先通过递归求出Sn-1的最大重合线段(tmpMaxSeg)，再求出Segment[n-1]和前n-1个线段的重合线段中最长的那一个(currMaxSeg)，比较tmpMaxSeg和currMaxSeg的长度，选出最长的作为Sn的返回值。
（3）注意：递归出口：size==2时，只有两个线段，通过简单比较就可以得出最大覆盖线段；
至于这块儿：是为了应对原本传入的线段数组的大小小于等于1的情况，算是边界条件处理了，不是递归的出口。
假如传入数组大小为3，递归执行到数组大小为2时就可以返回了。
#include <iostream>
#include <cstdlib>
#include <algorithm>
const int LEN = 3;
using namespace std;
struct segment
{
int start;
int end;
};
// assume a.end < b.end
segment commonSeg(const segment & a, const segment & b)
{
segment CommonSeg;
if(a.end < b.start)
{
CommonSeg.end = 0;
CommonSeg.start = 0;
}
else
{
CommonSeg.end = a.end;
CommonSeg.start = b.start;
}
return CommonSeg;
}
int findMaxSegment(int size, segment * Segment, segment & maxSeg)
{
if(NULL == Segment)
{
cerr << "the segment array is NULL" << endl;
return -1;
}
else if(1 == size)
{
maxSeg = Segment[0];
return maxSeg.end-maxSeg.start;
}
else if(2 == size)
{
if(Segment[0].end <= Segment[1].start)
{
maxSeg.start = 0;
maxSeg.end = 0;
return maxSeg.end-maxSeg.start;
}
else
{
maxSeg.end = Segment[0].end;
maxSeg.start = Segment[1].start;
return maxSeg.end-maxSeg.start;
}
}
else
{
segment tmpMaxSeg, tmpSeg,currMaxSeg;
int currMaxLen = 0;
findMaxSegment(size-1, Segment, tmpMaxSeg);
for(int i=0; i<size-1; i++)
{
tmpSeg=commonSeg(Segment[i], Segment[size-1]);
if(tmpSeg.end - tmpSeg.start > currMaxLen)
{
currMaxLen = tmpSeg.end - tmpSeg.start;
currMaxSeg = tmpSeg;
}
}
if(tmpMaxSeg.end - tmpMaxSeg.start > currMaxLen )
{
maxSeg = tmpMaxSeg;
}
else
{
maxSeg = currMaxSeg;
}
return maxSeg.end - maxSeg.start;
}
}
bool isShorter(const segment & s1, const segment & s2)
{
return s1.end < s2.end;
}
int main()
{
segment * Segment = new segment[LEN];
Segment[0].start = 1;
Segment[0].end = 5;
Segment[1].start = 2;
Segment[1].end = 8;
Segment[2].start = 3;
Segment[2].end = 9;
sort(Segment, Segment + LEN, isShorter);
segment maxSeg;
findMaxSegment(LEN, Segment, maxSeg);
cout << maxSeg.start << endl;
cout << maxSeg.end << endl;
delete [] Segment;
return 0;
}
百度的某服务机制类似于 CS（customer-server），有时候大量用户访问服务器 S， 导致 S 运行效率缓慢。 为了提升效率， 拟在 C 上利用一些空余的结果空间作为缓存。 已知在 C 的一台客户机上，每天接收 1000w query，其中 500w uniq query，每个 query 5KB，客户机内存 3GB，硬盘 500GB。做出一个方案，说明系统结构、存储结 构、性能优化等方面的设计。
1.所有的query结果都放在硬盘
2.所有query到query结果的映射存储在内存
3.多余内存作为缓存,缓存淘汰机制为查询次数和LRU
判断一个括号字符串是否匹配正确，如果括号有多种，怎么做？如（（[]））正确，[[(()错误。
用栈来出现，凡是左括号就压栈，凡是右括号就出栈，最后如果栈为空就匹配正确
搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
要统计最热门的10条查询串. 内存<1G. 字符串长 0-255
(1) 主要解决思路
(2) 算法及其复杂度分析
分俩部门，第一部分建立 索引树，数据遍历索引树，数据在树中存在的话，count++,数据不存在 就加到索引树上，第二部分建立个含有十个数据的最小堆，将数据的count与堆顶比较，大于堆顶的话，将其加入，同时删除堆顶元素，加入后重新调整堆的位置。
