2021年百度公司 C语言开发工程师面试题

 用 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

#include

#include

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

        {

            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与堆顶比较，大于堆顶的话，将其加入，同时删除堆顶元素，加入后重新调整堆的位置。